Optimization of Multi-Trip Vehicle Routing Problem Considering Multiple Delivery Locations

This paper addresses the challenges of improving last-mile logistics delivery satisfaction in urban areas by studying a multi-trip vehicle routing problem with multiple delivery locations (MTVRPMDL). The MTVRPMDL simultaneously decides the visiting order of customers for each vehicle and selects an appropriate delivery location for every customer. The problem exhibits intrinsic spatial and decision symmetries, arising from interchangeable vehicle trips, alternative delivery locations for each customer, and symmetric route permutations that lead to equivalent operational outcomes. A mixed-integer programming model is proposed, aiming to minimize the total vehicle travel time. Within an iterated local search framework, a modified Solomon greedy insertion heuristic suitable for multi-delivery address and multi-trip settings is developed to generate initial solutions. During the iterative search phase, Or-opt and Relocate local search operators are employed, together with random swap perturbations, to enhance solution exploration. Computational experiments confirm the efficiency of the proposed model and algorithm, showing that allowing customers to have multiple delivery locations can significantly reduce overall travel time and improve the flexibility of vehicle routing decisions.