Sponsor
This research is partially supported by the National Science and Technology Council of Taiwan under grant NSTC 112-2410-H-011-004-MY3 and the National Taiwan University of Science and Technology under grant NTUST-ITB-111-05.
Published In
Applied Soft Computing
Document Type
Pre-Print
Publication Date
5-1-2024
Subjects
Delivery systems -- Linear Programming, Linear programming -- Mathematical models, Linear programming -- Software
Abstract
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.
Rights
© Copyright the author(s) 2024
Locate the Document
DOI
10.1016/j.asoc.2024.111482
Persistent Identifier
https://archives.pdx.edu/ds/psu/41848
Citation Details
Published as: Yu, V. F., Salsabila, N. Y., Gunawan, A., & Handoko, A. N. (2024). An adaptive large neighborhood search for the multi-vehicle profitable tour problem with flexible compartments and mandatory customers. Applied Soft Computing, 156, 111482.
Description
This is the author’s version of a work that was accepted for publication. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published as: An adaptive large neighborhood search for the multi-vehicle profitable tour problem with flexible compartments and mandatory customers. Applied Soft Computing, 156, 111482.