An adaptive large neighborhood search for the multi-vehicle profitable tour problem with flexible compartments and mandatory customers

• Main Authors: YU, Vincent F., SALSABILA, Nabila Yuraisyah, GUNAWAN, Aldy, HANDOKO, Anggun Nurfitriani
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Flexible compartment; Home-refill; Mandatory customer; Multi-compartment; Multi-trip; Numerical Analysis and Scientific Computing; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/8713; https://ink.library.smu.edu.sg/context/sis_research/article/9716/viewcontent/AdaptiveLNS_multi_vehicle_av.pdf
• Institution: Singapore Management University

The home-refill delivery system is a business model that addresses the concerns of plastic waste and its impact on the environment. It allows customers to pick up their household goods at their doorsteps and refill them into their own containers. However, the difficulty in accessing customers’ locations and product consolidations are undeniable challenges. To overcome these issues, we introduce a new variant of the Profitable Tour Problem, named the multi-vehicle profitable tour problem with flexible compartments and mandatory customers (MVPTPFC-MC). The objective is to maximize the difference between the total collected profit and the traveling cost. We model the proposed problem as Mixed Integer Linear Programming and present an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it. Our ALNS outperforms the commercial solver, Gurobi, and Large Neighborhood Search (LNS), as proven by giving better solutions within reasonable computational times. Both ALNS and LNS can obtain optimal solutions for all small instances and three better solutions than Gurobi for medium problems. Furthermore, ALNS is also robust and effective in solving large MVPTPFC-MC, as proven by resulting in better solutions within less CPU time than LNS. Finally, more analyses are conducted to justify the utilization of flexible compartment sizes by comparing it with fixed compartment sizes and to evaluate the robustness of MVPTPFC-MC. The results show that utilizing flexible compartment sizes can yield more benefits than fixed compartment sizes, particularly when the fleet size is limited, and there are fewer mandatory customers to serve.