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

被引：0

作者：

Yu, Vincent F. ^{[1
,2
]}

Salsabila, Nabila Yuraisyah ^{[1
]}

Gunawan, Aldy ^{[3
]}

Handoko, Anggun Nurfitriani ^{[1
]}

机构：

[1] Department of Industrial Management, National Taiwan University of Science and Technology, Taipei, Taiwan

[2] Department of Civil and Environmental Engineering, Portland State University, Portland,OR,97201, United States

[3] School of Computing and Information Systems, Singapore Management University, Singapore

来源：

Applied Soft Computing | 2024年 / 156卷

关键词：

Integer programming - Sales;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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. © 2024 Elsevier B.V.

引用