Аннотация:

We consider the classical Pickup and Delivery Problem with Time Windows (PDPTW). To tackle the problem, we present a heuristic scheme that is based on a memetic algorithm. The algorithm uses EAX and SREX crossovers, a large neighborhood search and a local search with  multiple neighborhoods as an improvement step, and a special population management mechanism. Additionally, we implement several auxiliary procedures to diversify the search and also an iterated local search algorithm that helps the memetic algorithm. We compare the scheme to the best-known solutions for two benchmark libraries with up to 5000 clients and 148 vehicles. The proposed algorithm demonstrates good final results and is able to improve best-known solutions for 53 instances.