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

arXiv: https://arxiv.org/abs/2011.06331 · HTML: https://mlsanity.com/paper/2011.06331/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2020.

## Built on by (most cited first, 4 of 4)

- [Effective and Imperceptible Adversarial Textual Attack via Multi-objectivization](https://mlsanity.com/paper/2111.01528/) (2021)
- [Training Quantized Deep Neural Networks via Cooperative Coevolution](https://mlsanity.com/paper/2112.14834/) (2021)
- [Memory efficient location recommendation through proximity-aware representation](https://mlsanity.com/paper/2310.06484/) (2023)
- [Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration](https://mlsanity.com/paper/2506.17357/) (2025)

## Abstract (arXiv)

The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) has attracted much research interest in the last decade, due to its wide application in modern logistics. Since VRPSPDTW is NP-hard and exact methods are only applicable to small-scale instances, heuristics and meta-heuristics are commonly adopted. In this paper we propose a novel Memetic Algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. Compared to existing algorithms, the advantages of MATE lie in two aspects. First, it is capable of more effectively exploring the search space, due to its novel initialization procedure, crossover and large-step-size operators. Second, it is also more efficient in local exploitation, due to its sophisticated constant-time-complexity move evaluation mechanism. 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). Moreover, a comprehensive ablation study is also conducted to show the effectiveness of the novel components integrated in MATE. Finally, a new benchmark of large-scale instances, derived from a real-world application of the JD logistics, is introduced, which can serve as a new and more challenging test set for future research.