A Memetic Algorithm for Large-Scale Real-World Vehicle Routing Problems with Simultaneous Pickup and Delivery with Time Windows

The vehicle routing problem with simultaneous pickup and delivery with time windows (VRPSPDTW) is an important variant of the vehicle routing problem which has received considerable attention among researchers in the last decade. The vast majority of solution methodologies for the VRPSPDTW have been applied to synthetic problem instances that bear little resemblance to routing problems found in the real world. Recently, 20 large-scale VRPSPDTW instances based on real customer data from the transportation company known as JD Logistics became publicly available as a new benchmark VRPSPDTW problem set. In this paper, a memetic algorithm (MA), referred to as MA-BCRCD, is proposed for use on these real-world instances. The MA prioritizes efficient search and utilizes a crossover method which is shown to be more effective than that of the previous MA approach (known as MATE) applied to this set. MA-BCRCD finds new best known solutions for all 20 instances. It also performs better on average for all instances in comparison to the performance of MATE. The results and analysis provided in this study suggest that further improvements on this problem set are possible both in terms of solution quality and search efficiency.