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

Authors

  • Haoran Ye Soochow University, China
  • Jiarui Wang Soochow University, China
  • Helan Liang Soochow University, China
  • Zhiguang Cao Singapore Management University, Singapore
  • Yong Li Tsinghua University, China
  • Fanzhang Li Soochow University, China

DOI:

https://doi.org/10.1609/aaai.v38i18.30009

Keywords:

PRS: Routing, SO: Combinatorial Optimization, SO: Learning to Search

Abstract

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.

Published

2024-03-24

How to Cite

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

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling