Hybrid Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery-Pickup

Abstract

In order to provide reasonable and effective decision support for logistics enterprises in vehicle distribu-tion path planning, this paper studies the vehicle routing problem with simultaneous delivery-pickup and time windows (VRPSDPTW) for single distribution center distribution mode, and establishes a mathematical model with the objective of minimizing the total distribution cost. According to the characteristics of the model, a hybrid optimization algorithm (SA-ALNS) based on the combination of simulated annealing (SA) and adaptive large-scale neighborhood search (ALNS) is proposed. An insertion heuristic algorithm based on time and distance weighting is used to construct the initial solution of the problem. A variety of delete and insert operators are introduced to optimize the path with adaptive selection strategy. Through the feedback mechanism, the probability of each operator being selected is gradually adjusted to make the algorithm more inclined to choose the operator with better optimization effect. The Metropolis criterion of simulated annealing mechanism is used to control the solution updating. In the simulation experiment, 56 large-scale examples are tested, and other intelligent optimization algori-thms such as p-SA algorithm, DCS algorithm and VNS-BSTS are compared and statistically analyzed. The results show that the algorithm is feasible and superior in solving the vehicle routing problem with simultaneous delivery-pickup and time windows. The research results greatly enrich the related research of vehicle routing problem (VRP).

Keywords

• |vehicle routing problem (vrp)|simultaneous delivery-pickup|simulated annealing (sa)|adaptive large-scale neighborhood search (alns)|time windows