Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows

The vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW) has attracted much attention in the last decade, due to its wide application in modern logistics involving bi-directional flow of goods. In this paper, we propose a memetic algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. The novelty of MATE lies in three aspects: 1) an initialization procedure which intelligently integrates a construction heuristic into the population-based search framework; 2) a new crossover operator involving route inheritance and regret-based node insertion; 3) a highly effective local search procedure which can flexibly search in a large neighborhood by switching between move operators with different step sizes, while keeping low computational complexity. Experimental results on public benchmarks show that MATE outperforms all the state-of-the-art algorithms, and notably, finds new best-known solutions on 12 instances (65 instances in total). A new benchmark of large-scale instances, derived from a real-world application of the JD logistics, is also introduced, which could serve as a new and more challenging test set for future research.