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

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