An Improved Ant Colony Optimization Based on Candidate Strategy and Grid Search for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

This paper studies a vehicle routing problem with simultaneous pickup and delivery (VRPSPD), which has an important application in logistics and other areas. The problem is that the depot provides both forward supply service and reverse recovery service to customers, and determines the lowest-cost vehicle distribution routes that satisfy the needs of all customers on the basis of considering constraints. To solve this problem, we develop an improved ant colony optimization algorithm based on candidate strategy and grid search (ACO-CS). The candidate strategy of ACO-CS reduces the running cost and speeds up the convergence rate by limiting and reducing the number of unvisited nodes. At the same time, we propose to use the grid search method to tune the parameters to enhance the algorithm’s optimization capability and improve its performance. Three benchmark test problems are selected to verify the effectiveness of the proposed algorithm for solving different types and sizes of instances. The computational results show that the proposed algorithm is competitive in solving the Dethloff (2001) and Montane & Galveo (2006) test problems, and its solution quality, calculation time and algorithm stability are better than the variant algorithms in the literature. Finally, a practical case of logistics distribution is introduced to verify the reliability of the algorithm, and the results show that the ACO-CS can provide a more reasonable and economical solution.