An Improved Genetic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service

摘要

The vehicle routing problem with simultaneous deliver)' 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 (he vehicle capacity and traveling distance constraints.In this paper, VRP-SDP was introduced and described from the point of view that combines the logistics and reverse logistics (bidirectional logistics), we constructed a universal integer programming mathemattc model of VRP-SDP in detail, which can transform into other classical vehicle routing problems by setting different parameters. Meantime, an improved genetic algorithm (IGA) was proposed to overcome the shortcomings of premature convergence and slow convergence of conventional genetic algorithm (GA). The novel crossover-operator, swapping operator and inversion operator as the core of IGA were constructed to solve VRP-SDP. We compared the performance of the proposed IGA with GA. The experiment results show that the performance of IGA is better than GA.