PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2312.08224v2cs.AIcs.LG

TL;DR

Existing neural routing solvers struggle to scale to large problems in real time. GLOP hierarchically combines non-autoregressive global partitioning with autoregressive local route construction, achieving competitive or state-of-the-art real-time performance across large-scale routing tasks.

  • Problem

    Existing neural combinatorial optimization methods struggle to solve routing problems with thousands or tens of thousands of nodes in seconds, despite industry demand for massive, expeditious routing.

    Source: §1 · p. 1

  • Method

    GLOP partitions large routing problems into TSPs and then SHPPs, using non-autoregressive policies for global partitioning and autoregressive policies for local construction.

    Source: §1 · p. 1

  • Results

    Across TSP, ATSP, CVRP, and PCTSP, GLOP delivers competitive or SOTA real-time performance; on TSP100K it achieves a 5.1% optimality gap and 174× speedup versus 1-run 1-trial LKH-3.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    GLOP provides a one-size-fits-all real-time (A)TSP solver that performs across scales and distributions using the same local policies.

    Source: §1 · p. 1

    GLOP might be less competitive when prolonged execution time is allowed and might trade off solution quality less effectively than iterative-refinement methods.

    Source: §7 · pp. 7–8

Abstract

from arXiv · show

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

1 Introduction

Existing neural routing solvers struggle to scale to thousands or tens of thousands of nodes in seconds. GLOP combines global partitioning with local route construction and reports competitive or state-of-the-art real-time results across several routing problems.

1 Introduction

  • Traditional mathematical-programming and iterative-heuristic solvers struggle to meet the growing complexity and real-time demands of routing applications.Most existing neural combinatorial optimization methods also struggle to solve instances with thousands or tens of thousands of nodes in seconds.Source: §1 · p. 1
  • GLOP partitions large routing problems into sub-TSPs, then divides potentially large sub-TSPs into smaller Shortest Hamiltonian Path Problems (SHPPs).Its non-autoregressive global policy learns the first partition, while its autoregressive local policy solves SHPPs.Source: §1 · p. 1
  • The paper presents GLOP as a versatile framework extending neural solvers to large-scale problems and as a one-size-fits-all real-time (A)TSP solver using small-SHPP construction.The authors also report that GLOP achieves better performance than approaches that learn upper-level TSP policies.Source: §1 · p. 1
  • GLOP delivers competitive scaling and cross-distribution performance on (A)TSP and state-of-the-art real-time performance on CVRP and PCTSP.It reports a 5.1% optimality gap and 174× speedup over 1-run 1-trial LKH-3 on TSP100K, and uses 10× less execution time than prior SOTA real-time CVRP solvers.Source: §1 · pp. 1–2

2 Background and related work

The background distinguishes autoregressive construction from non-autoregressive heatmap generation and decoding. Related neural divide-and-conquer solvers often rely on iterative refinement, while prior TSP reconstruction approaches face scaling or runtime trade-offs.

2.1 Neural Combinatorial Optimization (NCO)

  • End-to-end neural routing solvers are categorized as autoregressive solution construction or non-autoregressive heatmap generation followed by decoding.The paper situates these approaches within recent neural combinatorial optimization work (Berto et al. 2023).Source: §2.1 · p. 2

2.2 Divide and conquer for VRP

  • L2D and RBG use iterative refinement, while TAM autoregressively partitions large-scale CVRP into sub-TSPs for sub-solvers.GLOP is compared with TAM as a real-time large-scale CVRP method and is reported to outperform it and handle routing problems TAM does not address.Source: §2.2 · p. 2

2.3 Local construction for TSP

  • LCP repeatedly decomposes and reconstructs seeded tours but has difficulty scaling to TSPs with hundreds of nodes; H-TSP uses upper-level policies that GLOP dispenses with while outperforming it.Select-and-optimize uses a similar pipeline but relies on TSP-specific heuristics and takes longer; GLOP is reported to achieve competitive solutions hundreds of times more efficiently.Source: §2.3 · p. 2

3 Methodology overview

GLOP uses local policies to improve (sub-)TSP solutions and global policies to partition general routing problems. Its overview covers large-scale TSP, CVRP, and PCTSP settings.

3 Methodology overview

  • GLOP targets large-scale TSP alone, CVRP partitioned into multiple small sub-TSPs, and PCTSP partitioned into one large sub-TSP.The framework is intended to provide a unified, scalable approach to heterogeneous vehicle-routing problems.Source: §3 · p. 2
  • The local solver starts from a Random Insertion tour, decomposes it into subtours, and reconstructs them for improvement.The general routing solver additionally learns node clustering or subsetting to generate sub-TSPs.Source: §3 · p. 2
  • GLOP assigns local policies to (sub-)TSP solving and global policies to partitioning general routing problems into sub-TSPs.Source: §3 · p. 2

4 (Sub-)TSP solver

GLOP improves tours by repeatedly decomposing them into SHPPs and reconstructing subtours with autoregressive revisers. It trains these local policies on SHPP solution length and uses a two-stage curriculum.

4.1 Inference pipeline

  • GLOP initializes the tour with Random Insertion, which greedily chooses each node's insertion place to minimize insertion cost.A revision is the paper's term for a round of improvement to that initial tour.Source: §4.1 · p. 2
  • An inference revision decomposes a tour into disjoint n-node subtours, transforms and augments the resulting SHPP graphs, reconstructs them with revisers, and composes the subtours back into a tour.Reconstructed SHPP solutions worse than the current ones are discarded; GLOP can apply multiple revisers or repeat revisions, and use one set of small-SHPP-trained models for arbitrarily large TSPs.Source: §4.1 · pp. 2–3

4.2 Solving SHPP with local policy

  • The local policy solves an SHPP, or open-loop TSP with fixed start and end nodes, by autoregressively constructing forward- and backward-decoded solutions.At inference, GLOP accepts the better solution; the paper describes the local policy as a neural Attention Model adapted for SHPP and using solution symmetries.Source: §4.2 · p. 3

4.3 Training algorithm

  • The reviser is trained to minimize expected SHPP solution length, using REINFORCE and the average path length of two greedy rollouts as a baseline.The two-stage curriculum first trains on multi-distribution SHPPs with varied y-axis upper bounds, then collaboratively fine-tunes revisers following the inference pipeline.Source: §4.3 · p. 3, Two-stage curriculum learning · p. 4

5 General routing solver

GLOP adds a global partition policy to a unified formulation for hierarchical routing problems. It trains partitions against the final performance of locally solved subproblems and supports anticipated constraints through masking.

5.1 Global policy as partition heatmap

  • Its partition heatmap assigns unnormalized probabilities to node pairs belonging to the same subset, which the policy partitions under problem-specific constraints.Source: §5.1 · p. 4
  • For clustering, the policy forms multiple sub-TSPs; for subsetting, it separates to-visit nodes from the others, with heatmap decoding performed greedily or by sampling.Source: §5.1 · p. 4

5.2 Training algorithm

  • Training samples partitions in parallel, solves their sub-TSPs with local policies, and optimizes expected final performance using REINFORCE with an averaged-reward baseline.Source: §5.2 · p. 4

5 General routing solver

  • GLOP unifies node clustering and node subsetting for routing problems that require multiple routes, a single route over a subset, or both.Source: §5.3 · p. 4, §5 · p. 4

5.3 Applicability

  • Anticipated constraints can be handled by masking; more complex constraints may use penalties for infeasible solutions or post-processing.Source: §5.3 · p. 4

6 Experimentation

Experiments evaluate GLOP across TSP, ATSP, CVRP, and PCTSP, including large-scale and real-world benchmarks. Results report strong real-time performance, with task-specific comparisons and evaluation settings detailed below.

6.1 Experimental Setup

  • Evaluation spans generated routing benchmarks and real-world TSPLIB and CVRPLIB instances, with adjustable-runtime baselines and specified CPU/GPU hardware.The TSP tests include scales up to TSP100K; CVRP and PCTSP tests also include large-scale instances.Source: §6.1 · pp. 4–5

6.2 Travelling Salesman Problem

  • At TSP100K, GLOP obtains a 5.1% optimality gap and a 174× speed-up compared with LKH-3.The paper reports this as the first neural solver to effectively scale to TSP100K.Source: Table 2 · p. 5, §6.2 · p. 6
  • On most out-of-distribution TSP datasets, GLOP obtains smaller gaps and less Det; its local SHPP inputs are described as insensitive to overall TSP distribution.GLOP also performs favorably on real-world TSPLIB instances across scales and distributions.Source: Table 3 · p. 5, §6.2 · p. 6, Table 5 · p. 6
  • GLOP extends MatNet to large ATSP instances without MatNet’s 256-node initialization limit.The ATSP evaluation uses a MatNet50 checkpoint as GLOP’s reviser without retraining.Source: Table 4 · p. 5, §6.2 · pp. 6–7

6.3 Capacitated Vehicle Routing Problem

  • On large-scale CVRP, GLOP outperforms TAM in quality and efficiency, and retains this superiority on large CVRPLIB instances, especially very large ones.The CVRP5K and CVRP7K evaluations use a global policy trained on CVRP2K.Source: Table 6 · p. 6, §6.3 · p. 7, Table 7 · p. 7

6.4 Prize Collecting Travelling Salesman Problem

  • On large-scale PCTSP, GLOP surpasses recent neural and conventional solvers in solution quality and efficiency.The evaluation compares greedy and sampling decoding for the global policy.Source: §6.4 · p. 7, Table 8 · p. 7

7 Conclusion and limitation

GLOP combines global partitioning with local route construction and reports competitive, state-of-the-art real-time performance, while noting a trade-off when execution time is less constrained. The appendix details its revision process, coordinate normalization, curriculum, and global-policy constraints.

7 Conclusion and limitation

  • GLOP reports competitive and state-of-the-art real-time performance, but may be less competitive when prolonged execution time allows iterative-refinement methods to improve solution quality.The authors identify addressing this limitation and exploring unified AR/NAR methods as future work.Source: §7 · pp. 7–8

A.1 Pseudo code of solving (sub-)TSP

  • The (sub-)TSP procedure can start from multiple tours, retain the best after revisions, and shift decomposition points to minimize overlap between revisions.Source: §A.1 · p. 11

A.2 Coordinate transformation

  • Coordinate transformation scales the longer-axis coordinates using the SHPP bounds, while an optional graph rotation and min-max normalization leave the shorter axis with a variable upper bound.That variation motivates the multi-distribution curriculum.Source: §A.2 · p. 11

A.3 Curriculum learning

  • The first curriculum stage trains revisers on SHPPs with varied y-axis upper bounds; the second fine-tunes them on SHPPs decomposed from insertion-generated TSP tours.Source: §A.3 · p. 11

A.4 Details of our global policy

  • For CVRP, the global policy limits route length by vehicle count and prevents repeated visits or capacity violations; for PCTSP, it uses one route and enforces node uniqueness and minimum prize.The input graph features and sparsification choices differ between CVRP and PCTSP.Source: §A.4 · p. 11

A.5 Model architecture and training settings

The appendix specifies training and inference settings, reviews AR and NAR trade-offs and related work, defines the routing problems, and compares GLOP with MCTS baselines. These details frame GLOP as a real-time approach rather than a solution-quality competitor to prolonged iterative refinement.

A.5 Model architecture and training settings

  • Revisers use Adam with six encoder layers and staged training, while global policies use AdamW and cosine annealing with problem-specific learning rates.The first curriculum trains Reviser-10 for 100 epochs and other revisers for 200; the second trains all revisers for 300 epochs.Source: §A.5 · p. 11

A.6 Inference settings

  • Inference settings vary by problem: TSP uses a direct SHPP100 treatment for one cross-distribution case, CVRP uses greedy global decoding, and PCTSP uses greedy or sampled decoding.PCTSP samples 10 partitions and uses Reviser-100, 50, and 20 with 10, 10, and 5 revisions, respectively.Source: §A.6 · p. 11

B Discussing two paradigms

  • The (sub-)TSP procedure initializes tours, iteratively decomposes and revises subtours, composes them, shifts decomposition points, and selects the best resulting tour.Source: B Discussing two paradigms · p. 12
  • NAR heuristics generate coarse construction heatmaps in one shot but can lack decoding context, whereas AR heuristics use richer stepwise context at the cost of slower, less scalable decoding.Source: B Discussing two paradigms · pp. 11–12

C Additional related work

  • Prior neural routing work includes AR construction and NAR heatmaps, while GLOP is presented as an effective AR/NAR integration and a real-time complement to methods such as MCTS and LKH-3.The authors report state-of-the-art consistency across TSP scales and distributions.Source: C Additional related work · pp. 12–13

D Problem definitions

  • The appendix defines TSP as a shortest closed tour, SHPP as a shortest Hamiltonian path with fixed endpoints, CVRP as capacity-constrained depot routing, and PCTSP as tour length plus unvisited-node penalties subject to a prize minimum.Source: D Problem definitions · p. 13

E.1 Further comparison with baselines using MCTS

  • On TSP10K, GLOP can produce reasonable solutions before MCTS baselines finish heatmap generation, although continued MCTS iterations can eventually outperform it.Figure 2 marks the baselines' curves from completion of heatmap generation and their first MCTS iteration.Source: §E.1 · p. 13, Figure 2 · p. 13

E.2 Ablation study

The ablations examine local-policy solver and pipeline components, global partitioning, and training choices. They attribute cross-distribution performance primarily to the overall divide-and-conquer process, with different curriculum stages favoring different settings.

E.2 Ablation study

  • Neural heuristics offer a clear solution-efficiency advantage over LKH-3 as SHPP solvers, while enabling thousands of SHPPs to be solved simultaneously on GPUs.Source: §E.2 · p. 13
  • Ablations of bidirectional decoding, coordinate transformation, and two-stage curriculum learning validate these local-policy components.The study uses more revisions to realize the local policies' potential.Source: §E.2 · p. 13, Table 12 · p. 14
  • The global-policy comparisons test its advantage over an AR dividing policy on CVRP and over random partitioning on PCTSP.Source: §E.2 · p. 14, Table 13 · p. 14

E.3 Discussing cross-distribution performance of local policies

  • GLOP has lower Det. than the cross-distribution baseline under all tested training schemes; the first curriculum stage improves cross-distribution performance, while the second specializes GLOP for uniform TSP.More revisers or revisions reduce Gap but have less impact on Det.; the holistic divide-and-conquer process, rather than these additions, is identified as the main contributor to cross-distribution performance.Source: §E.3 · p. 14

E.4 Stability analysis of GLOP

More revisions improve the reported stability of GLOP, and its revision process has favorable empirical scaling under the tested settings. The paper describes near-constant empirical time for smaller TSPs and lower-than-linear empirical complexity for CVRP and PCTSP.

E.4 Stability analysis of GLOP

  • With more revisions, GLOP's objective-value box-plot ranges on TSP500 and TSP1K are within 0.02, indicating desirable stability across 10 independent runs.Source: §E.4 · p. 14

E.5 Discussing time complexity

  • Each revision solves a batch of constant-scale SHPPs simultaneously, giving linear time complexity; empirically, execution time is near-constant below 10K nodes when revision time dominates.The comparison uses identical settings with 50 and 20 revisions for Reviser-50 and Reviser-20, respectively.Source: §E.5 · p. 14
  • CVRP and PCTSP show lower-than-linear empirical complexity, attributed to linear-time graph sparsification and near-constant empirical complexity for solving sub-TSPs.Source: §E.5 · p. 14

F Implementation details of baselines

The section lists neural baselines for TSP, CVRP, and PCTSP, and describes how implementations were reproduced, tuned, or adapted for evaluation.

F Implementation details of baselines

  • TSP, CVRP, and PCTSP evaluations compare GLOP with the neural baselines listed for each problem type.The lists include 12 TSP baselines, six CVRP baselines, and two PCTSP baselines.Source: F Implementation details of baselines · p. 14
  • Most neural baselines follow their open-source implementations, while some are tuned or adapted for comparable evaluation.Source: F Implementation details of baselines · p. 14
  • The reported results include GLOP objective-value box plots from 10 independent runs across 128 test instances, comparisons of training schemes and revisions, and single-instance solving times across scales.For LKH-3 on TSP100K, the number of trials was set to 1 to reduce runtime. AM uses sampling decoding (Kool, van Hoof, and Welling 2019).Source: Figure 3 · p. 15, Table 14 · p. 15, Table 15 · p. 15
  • GCN+MCTS and DIMES use adjusted MCTS execution times; DIMES also generalizes its TSP10K model to TSP100K.For GCN+MCTS, the time limit is derived from reported total runtime; DIMES follows original implementations at several scales.Source: F Implementation details of baselines · p. 15
  • AM+HAC uses 100 HAC epochs and M = 1280, while AMDKD+EAS uses 100 EAS iterations.Source: F Implementation details of baselines · p. 16
  • CVRP evaluations fix vehicle capacity at 50; RBG also fixes the depot at the unit-square center, while NLNS and MDAM use specified trained checkpoints.NLNS uses the XE 17 checkpoint; MDAM generalizes its PCTSP100 checkpoint.Source: F Implementation details of baselines · p. 16

G Discussing connections with non-learning OR methods

GLOP’s hierarchical approach shares an ideology with POPMUSIC, while the paper describes neural optimization and POPMUSIC as complementary. The discussion identifies possible benefits from combining their respective strengths.

G Discussing connections with non-learning OR methods

  • GLOP extends small neural solvers to larger problems and can benefit from developments in NCO models and increases in GPU power.Source: G Discussing connections with… · p. 16
  • NCO solvers and POPMUSIC are described as complementary: POPMUSIC initialization can improve NCO performance, while NCO can add parallelizability to POPMUSIC with little solution-quality cost when small problems are solved near-optimally.Source: G Discussing connections with… · p. 16
  • GLOP’s Sub-TSP solver shares the hierarchical ideology of POPMUSIC and other hierarchical TSP solvers.Source: G Discussing connections with… · p. 16
Loading 2312.08224v2…