A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations

With the rapid development of e-commerce, the importance of logistics distribution is becoming increasingly prominent. In particular, the last-mile delivery is particularly important because it serves customers directly. Improving customer satisfaction is one of the important factors to ensure the quality of service in delivery and also an important guarantee for improving the market competitiveness of logistics enterprises. In the process of last-mile delivery, flexible delivery locations and variable delivery times are effective means to improve customer satisfaction. Therefore, this paper introduces a Vehicle Routing Problem with flexible time windows and delivery locations, considering customer satisfaction (VRP-CS), which considers customer satisfaction by using prospect theory from two aspects: the flexibility of delivery time and delivery locations. This VRP-CS is formally modeled as a bi-objective optimization problem, which is an NP-hard problem. To solve this problem, a Multi-Strategy Adaptive Large Neighborhood Search (MSALNS) method is proposed. Operators guided by strategies such as backtracking and correlation are introduced to create different neighborhoods for ALNS, thereby enriching search diversity. In addition, an acceptance criterion inspired by simulated annealing is designed to balance exploration and exploitation, helping the algorithm avoid being trapped in local optima. Extensive numerical experiments on generated benchmark instances demonstrate the effectiveness of the VRP-CS model and the efficiency of the proposed MSALNS algorithm. The experiment results on the generated benchmark instances show that the total cost of the VRP-CS is reduced by an average of 14.22% when optional delivery locations are utilized compared to scenarios with single delivery locations.