An Iterated Local Search Heuristic for the Multi-Trip Vehicle Routing Problem with Multiple Time Windows

Yinghui Wu (), Haoran Du and Huixin Song
Additional contact information
Yinghui Wu: School of Economics and Management, Jiangsu University of Science and Technology, Zhenjiang 212100, China
Haoran Du: School of Economics and Management, Jiangsu University of Science and Technology, Zhenjiang 212100, China
Huixin Song: School of Economics and Management, Jiangsu University of Science and Technology, Zhenjiang 212100, China

Mathematics, 2024, vol. 12, issue 11, 1-16

Abstract: This paper studies the multi-trip vehicle routing problem with multiple time windows, which extends the multi-trip vehicle routing problem by deciding not only the sequence of customers that each vehicle serves but also the service time window of each customer. It also requires that the delivery service time is within the selected time windows and that the total demand of the customers served by the vehicle on each trip does not exceed the maximum carrying capacity. For solving the studied problem, we develop a mixed integer linear programming model with the objective of minimizing the total travel distance of vehicles and design a tailored iterative local search heuristic. Within the framework of the iterative local search, an improved Solomon greedy insertion algorithm suitable for multiple time windows and multi-trip scenarios is designed to generate the initial solution, and local search operators such as Or-opt and Relocate, as well as Random Exchange perturbation operations, are also developed. The experiment results demonstrate the effectiveness of the proposed model and algorithm and confirm that by providing customers with multiple time windows option, carriers can flexibly plan vehicle routes and select appropriate service time windows, thereby reducing the number of vehicles used and the total distance travelled and improve delivery success.

Keywords: multi-trip vehicle routing problem; multiple time windows; mixed integer programming; iterated local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/11/1712/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/11/1712/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:11:p:1712-:d:1405907

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().