GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time
Proceedings of the AAAI Conference on Artificial Intelligence · 24.03.2024 · 38 (18) · 20284-20292
DOI: 10.1609/aaai.v38i18.30009 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 24.03.2024. Verfasst von Haoran Ye und 5 weiteren Autor:innen. Die Arbeit wurde bisher 41-mal zitiert (Crossref).
Abstract (Originalsprache)
The recent end-to-end neural solvers have shown promise for small-scale routing problems but suffered from limited real-time scaling-up performance. This paper proposes GLOP (Global and Local Optimization Policies), a unified hierarchical framework that efficiently scales toward large-scale routing problems. GLOP hierarchically partitions large routing problems into Travelling Salesman Problems (TSPs) and TSPs into Shortest Hamiltonian Path Problems. For the first time, we hybridize non-autoregressive neural heuristics for coarse-grained problem partitions and autoregressive neural heuristics for fine-grained route constructions, leveraging the scalability of the former and the meticulousness of the latter. Experimental results show that GLOP achieves competitive and state-of-the-art real-time performance on large-scale routing problems, including TSP, ATSP, CVRP, and PCTSP. Our code is available at: https://github.com/henry-yeh/GLOP.
Zitieren
APA
Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., & Li, F. (2024). GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18), 20284-20292. https://doi.org/10.1609/aaai.v38i18.30009
Vancouver
Ye H, Wang J, Liang H, Cao Z, Li Y, Li F. GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time. Proceedings of the AAAI Conference on Artificial Intelligence. 2024;38(18):20284-20292. doi:10.1609/aaai.v38i18.30009
BibTeX
@article{Ye2024,
author = {Ye, Haoran and Wang, Jiarui and Liang, Helan and Cao, Zhiguang and Li, Yong and Li, Fanzhang},
title = {GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2024},
volume = {38},
number = {18},
pages = {20284--20292},
doi = {10.1609/aaai.v38i18.30009}
}
EUVIMED