Efficient Neural Collaborative Search for Pickup and Delivery Problems
IEEE Transactions on Pattern Analysis and Machine Intelligence · 2024-12 · 46 (12) · 11019-11034
DOI: 10.1109/tpami.2024.3450850 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024-12. Verfasst von Detian Kong und 4 weiteren Autor:innen. Die Arbeit wurde bisher 26-mal zitiert (Crossref) und nennt 42 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Special Foundation for Philosophy and Social Science Laboratories of Ministry of Education of China, Asia Research Center, Nankai University.
Abstract (Originalsprache)
In this paper, we introduce Neural Collaborative Search (NCS), a novel learning-based framework for efficiently solving pickup and delivery problems (PDPs). NCS pioneers the collaboration between the latest prevalent neural construction and neural improvement models, establishing a collaborative framework where an improvement model iteratively refines solutions initiated by a construction model. Our NCS collaboratively trains the two models via reinforcement learning with an effective shared-critic mechanism. In addition, the construction model enhances the improvement model with high-quality initial solutions via curriculum learning, while the improvement model accelerates the convergence of the construction model through imitation learning. Besides the new framework design, we also propose the efficient Neural Neighborhood Search (N2S), an efficient improvement model employed within the NCS framework. N2S exploits a tailored Markov decision process formulation and two customized decoders for removing and then reinserting a pair of pickup-delivery nodes, thereby learning a ruin-repair search process for addressing the precedence constraints in PDPs efficiently. To balance the computation cost between encoders and decoders, N2S streamlines the existing encoder design through a light Synthesis Attention mechanism that allows the vanilla self-attention to synthesize various features regarding a route solution. Moreover, a diversity enhancement scheme is further leveraged to ameliorate the performance during the inference of N2S. Our NCS and N2S are both generic, and extensive experiments on two canonical PDP variants show that they can produce state-of-the-art results among existing neural methods. Remarkably, our NCS and N2S could surpass the well-known LKH3 solver especially on the more constrained PDP variant.
Förderung
- National Natural Science Foundation of China
- Special Foundation for Philosophy and Social Science Laboratories of Ministry of Education of China
- Asia Research Center, Nankai University
- National Research Foundation Singapore
- Singapore Ministry of Education (MOE) Academic Research Fund
Zitieren
APA
Kong, D., Ma, Y., Cao, Z., Yu, T., & Xiao, J. (2024). Efficient Neural Collaborative Search for Pickup and Delivery Problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12), 11019-11034. https://doi.org/10.1109/tpami.2024.3450850
Vancouver
Kong D, Ma Y, Cao Z, Yu T, Xiao J. Efficient Neural Collaborative Search for Pickup and Delivery Problems. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2024;46(12):11019-11034. doi:10.1109/tpami.2024.3450850
BibTeX
@article{Kong2024,
author = {Kong, Detian and Ma, Yining and Cao, Zhiguang and Yu, Tianshu and Xiao, Jianhua},
title = {Efficient Neural Collaborative Search for Pickup and Delivery Problems},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = {2024},
volume = {46},
number = {12},
pages = {11019--11034},
doi = {10.1109/tpami.2024.3450850}
}
EUVIMED