An Improved Differential Evolution Algorithm for the Vehicle Routing Problem With Simultaneous Delivery and Pick-up Service

The vehicle routing problem with simultaneous delivery and pick-up (VRP-SDP) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous delivery and pick-up. Deliveries are supplied from a single depot at the beginning of the vehicle´s service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle´s load in any given route is a mix of delivery and pick-up loads, at the same time in any route the vehicle can not violate some constraints for example the vehicle capacity and traveling distance constraints. In this paper, VRP-SDP is presented from the point of strategic view that combined the logistics and reverse logistics (bidirectional logistics). We constructed a universal mixed integer programming mathematic model of VRP-SDP in detail, it can transform into other classical vehicle routing problems by setting different parameters. An improved differential evolution algorithm (IDE) is proposed. In operation process, we firstly adopted the novel decimal coding to construct initial population, and then some improved differential evolution operators were adopted as the main optimizing scheme, such as adopted a real number coding method based on integer order criterion in mutation operation, a punishment function was designed to dispose constraints, and in crossover operation the crossover probability was self-updated with iteration. The computer simulations are used to compare the performance of the proposed method with genetic algorithm (GA), numerical results show that the performance of the proposed method is better than GA.