An improved genetic algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows

摘要

This paper studied the VRPSPDTW (Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time-Windows). An integer programming model is constructed, its objective is to minimize the delivery time. To further improve the convergence speed and optimization capability of the genetic algorithm, an improved genetic algorithm with local search (IGALS) is proposed, which is based on a hybrid crossover operation with elitist strategy and a local search using the thought of allowed delay time. The paper analyzed the advantages of heuristic algorithm to solve the problem by comparing the computation complexity between exact algorithm and heuristic algorithm. Testing by Solomon Benchmarks instances, the results show the IGALS has better performance than simple GA, which has better global optimization capability and faster convergence speed.