EUVIMEDEUVIMED entdecken
Crossref

GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time

Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, Fanzhang Li

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →