Efficient neural neighborhood search for pickup and delivery problems

• Main Authors: MA, Yining, LI, Jingwen, CAO, Zhiguang, SONG, Wen, GUO, Hongliang, GONG, Yuejiao, CHEE, Meng Chee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8137; https://ink.library.smu.edu.sg/context/sis_research/article/9140/viewcontent/pdp_n2s_update.pdf
• Institution: Singapore Management University

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.