A Metaheuristic approach for the vehicle routing problem with simultaneous pick-up and delivery (VRP-SPD)

Abstract

In the supply chain system, there are two types of logistic processes, those are forward and reverse logistics. One of the problems in the forward and reverse logistics process is to determine the optimal route of vehicles. The routing problem in forward and reverse logistics can be solved using vehicle routing problem with simultaneous pick-up and delivery (VRP-SPD). The VRP-SPD has an objective to make some routes that minimize total distance travelled by considering the vehicle capacity constraint because of pick-up and delivery activities. This paper uses a hybrid metaheuristic approach that combines the Simulated Annealing (SA) method with Variable Neighborhood Search (VNS) concept for generating neighbourhood solutions. Swap, insert, and reverse operations are used for the neighbourhood moves. The idea of systematically changing the neighbourhood moves helps the algorithm explore more diverse solution possibilities. The Simulated Annealing with Variable Neighborhood Search (SA-VNS) is then tested to the VRP-SPD benchmark instances that have 15 until 20 nodes for every case. The computational results show that the metaheuristic approach can obtain good enough solutions with an average-difference gap with the exact solution from CPLEX 6,23% and only five instances that have differences more than 10%. After that, the Simulated Annealing with VNS is used to solve larger instances by extending the benchmark instances up to 400 nodes. For the large instances, SA-VNS can obtain optimal solution efficiently, but it still needs some improvement in the quality of the optimal solution.