An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows

The vehicle routing problem with simultaneous pickups and deliveries and time windows (VRP-SPDTW) is the problem of optimally integrating forward (good distribution) and reverse logistics (returning materials) for cost saving and environmental protection. We constructed a general mixed integer programming model of VRP-SPDTW The model contained some classical vehicle routing problems as special cases. We proposed an improved differential evolution algorithm (IDE) for solving this problem In the algorithm, we firstly adopted the novel decimal coding to construct an initial population, then used some improved differential evolution operators unlike the existing algorithm, and in mutation operation, we used an integer order criterion based on natural number coding method. We introduced a penalty technical to publish the infeasible solution. In addition, in the crossover operation, we designed a self-adapting crossover probability that varied with iteration. We did some numerical experiments, and the results showed that the proposed method is effective for solving VRP-SPDTW. Crown Copyright (C) 2009 Published by Elsevier Ltd. All rights reserved.