Abstract—Thevehicle routing problem with simultaneous pickup and delivery (VRPSPD) is an extensionto the classical vehicle routing problem (VRP) where customers require pickupand delivery service simultaneously. The objective of this problem is todetermine the optimal set of routes to totally satisfy both the pickup anddelivery. We propose a modified particle swarm optimization to solve thisproblem. The solution representation for VRPSPD with m customers is several(m+1)-dimensional particles. In the decoding process, particles will betransformed to vehicle allocation matrices with the sweep algorithm, and thenthe priority matrices of customers served by the same vehicle are evaluated.Based on the two matrices, the vehicle routes are constructed. The proposedalgorithm is evaluated using some benchmark datasets which are publicly available,and the experimental results prove that our proposed method is effective andefficient.
I. INTRODUCTION
The vehicle routing problem with simultaneous pickup anddelivery (VRPSPD) is an extension to the vehicle routing problem (VRP), awell-known combinatorial optimization problem firstly proposed by Dantzig andRamser[1], in which vehicles are not only required to deliver goods tocustomers but also to simultaneously pick up goods from customers. Alldelivered goods are originated from the depot and all pickup goods aretransported back to the depot. The number of vehicles is usually not known inadvance. The objective of VRPSPD is to minimize the total routing cost for afleet of vehicles. Since cost is closely associated with distance, it is equalto minimize the total distance traveled by the vehicles.
The VRPSPD is common in practice. In the context ofdistribution process, customers may have both a delivery and a pickup demand. Forexample, in the soft drink industry, soft drinks are delivered to the grocerystores.Empty bottles andreusable pallets/containers are returned to the factory. During the lastdecades, environmental awareness has resulted into legislation, forcingcompanies to take responsibility for their products of whole lifecycle. Therefore,the distribution networks must be designedin a bi-directional way for the new and used products. These customers may not wantto be served separately for the delivery and pickup, because a handling effortis necessary for both activities and this effort may be considerably reduced bya simultaneous operation.