Research on multitrip vehicle routing problem with soft time window based on ALNS algorithm

Vehicle Routing Problem (VRP) is a classic combinatorial optimization problem. In urban last-mile delivery scenarios, this paper investigates the Multi-Trip Vehicle Routing Problem with Soft Time Windows and Delay Penalty (MTVRPSTW). Here, each vehicle can make multiple trips to serve customers before the depot closes. In practical logistics, companies often use overtime compensation to address delivery delays. Therefore, in this problem, if a customer receives service after the time window ends, a delay cost is incurred. MTVRPSTW aims to minimize vehicle usage costs, travel distance costs, and delay penalty costs. An Adaptive Large Neighborhood Search (ALNS) algorithm based on sequential insertion is designed. The effectiveness of the model and algorithm is verified through comparative analysis of solution results.