Vehicle Routing Problem with Simultaneous Pickup and Delivery

Abstract—This paper focuses on the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) issue. VRPSPD is one of the extended problems related to the usual Vehicle Routing Problem (VRP). VRPSPD consists of both linehaul customers and backhaul customers with known demand. In VPRSPD, only a single depot can receive and supply the loads. The vehicles can only visit each customer once and can serve all customers simultaneously by delivering or picking up the loads within a limited capacity. VPRSPD is an NP-hard problem. The considerable data size has increased the difficulty for it to be solved by using mathematical programming or combinatorial optimization. A heuristic approach based on the Variable Neighborhood Search (VNS) is proposed. Heuristic-based solutions offer feasible solutions that are approximately accurate to the exact solution. It is one of the most popular solutions to solve a complex problem. In this research, the algorithm solution consists of two main phases. A simple heuristic is used to generate the initial solution in the first phase. Then, the feasible solution obtained in the first phase will become the initial input for the improvement phase, which applied the VNS algorithm. The proposed algorithm is tested using a list of benchmark datasets. The result obtained is compared with the best solution that can be found in literature research. The comparison result shows that the heuristic algorithm is favorable to be used for this kind of vehicle routing problem