Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
7-2022
Abstract
We present an efficient Neural Neighborhood Search (N2S) approach for pickup and delivery problems (PDPs). In specific, we design a powerful Synthesis Attention that allows the vanilla self-attention to synthesize various types of features regarding a route solution. We also exploit two customized decoders that automatically learn to perform removal and reinsertion of a pickup-delivery node pair to tackle the precedence constraint. Additionally, a diversity enhancement scheme is leveraged to further ameliorate the performance. Our N2S is generic, and extensive experiments on two canonical PDP variants show that it can produce state-of-the-art results among existing neural methods. Moreover, it even outstrips the well-known LKH3 solver on the more constrained PDP variant.
Discipline
Databases and Information Systems
Research Areas
Data Science and Engineering; Software and Cyber-Physical Systems
Publication
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Vienna, Austria, 2022 Jul 23-29
First Page
4776
Last Page
4784
ISBN
9781956792003
Identifier
10.48550/arXiv.2204.11399
Publisher
International Joint Conferences on Artificial Intelligence
City or Country
California
Citation
MA, Yining; LI, Jingwen; CAO, Zhiguang; SONG, Wen; GUO, Hongliang; GONG, Yuejiao; and CHEE, Meng Chee.
Efficient neural neighborhood search for pickup and delivery problems. (2022). Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Vienna, Austria, 2022 Jul 23-29. 4776-4784.
Available at: https://ink.library.smu.edu.sg/sis_research/8137
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.48550/arXiv.2204.11399