PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Delegate for Large-scale Vehicle Routing

Sirui Li, Zhongxia Yan, Cathy Wu

arXiv:2107.04139v2cs.LGcs.AI

TL;DR

Large VRPs are difficult for existing heuristic and learning-based methods to solve efficiently at scale. The paper learns to select spatially local subproblems for delegation to a black-box subsolver, reporting faster competitive solving across large and varied VRP settings.

  • Problem

    Existing heuristic solvers can be computationally burdensome on large VRPs, while learning-based methods have mainly demonstrated scalability on small instances.

  • Method

    The framework uses a learned selector to identify spatially local subproblems and delegates their iterative improvement to an existing subsolver.

  • Results

    The method accelerates competitive VRP solvers on problems up to size 3000, requiring an order of magnitude less computation time, with 1.5x to 2x speedup over non-learning selection strategies.

  • Takeaways & Limitations

    Learning-to-delegate generalizes across VRP distributions, variants, and solvers while combining learned subproblem selection with competitive heuristic solving.

  • Takeaways & Limitations

    The framework relies on the hypothesis that typical CVRPs have exploitable structure and may have negative externalities when used to make large-scale vehicle routing more efficient.

Abstract

from arXiv · show

Vehicle routing problems (VRPs) form a class of combinatorial problems with wide practical applications. While previous heuristic or learning-based works achieve decent solutions on small problem instances of up to 100 cities, their performance deteriorates in large problems. This article presents a novel learning-augmented local search framework to solve large-scale VRP. The method iteratively improves the solution by identifying appropriate subproblems and $\textit{delegating}$ their improvement to a black box subsolver. At each step, we leverage spatial locality to consider only a linear number of subproblems, rather than exponential. We frame subproblem selection as regression and train a Transformer on a generated training set of problem instances. Our method accelerates state-of-the-art VRP solvers by 10x to 100x while achieving competitive solution qualities for VRPs with sizes ranging from 500 to 3000. Learned subproblem selection offers a 1.5x to 2x speedup over heuristic or random selection. Our results generalize to a variety of VRP distributions, variants, and solvers.

1 Introduction

Large-scale VRPs remain difficult for both traditional and learning-based solvers, motivating a framework that learns which smaller subproblems to delegate to existing methods. Spatial locality reduces the selection space, enabling learned subproblem selection while preserving solution quality and improving speed.

  • Motivation: Traditional heuristics can solve large VRPs but may require substantial computation, with LKH-3 taking more than an hour on a size 2000 CVRP instance.Heuristic methods also suffer from inflexibility caused by hand-crafting and lengthy iterative procedures.
  • Motivation: Learning-based VRP methods reduce computation time on instances below 100 cities but remain difficult to scale beyond small problems.Few such methods report results on problems larger than 200 cities.
  • Approach: The proposed framework learns to identify smaller subproblems that existing methods can solve, focusing local improvement on promising subregions.The method addresses scalability by delegating subproblem improvement to existing solvers.
  • Approach: Spatial locality restricts subproblem selection to a linear-sized space, making attention-based selector training feasible.Objects that are far apart generally have weaker influence on each other’s solutions and are less likely to share routes.
  • Contributions: The framework combines learned subproblem identification with heuristic subsolvers to accelerate solution times while maintaining good solution quality.It avoids applying the subsolver at full large-problem scale.
  • Contributions: Learning-to-delegate iteratively identifies and solves smaller subproblems, using a Transformer to predict subsolver solution quality and improving over baseline selection strategies across VRP settings.The reported validation covers multiple VRP variants, distributions, and solvers.

2 Preliminary: Capacitated Vehicle Routing Problems (CVRP)

CVRP assigns city demands to capacity-limited vehicle routes that start and end at a depot. The objective is to construct feasible routes visiting every city exactly once while minimizing total route cost.

  • Problem definition: A CVRP contains a depot node 0 and city nodes {1, ..., N}, each with demand d_i, while vehicles have capacity C.Vehicles start and end at the depot and serve routes whose total demand does not exceed C.
  • Problem definition: A feasible CVRP solution is a set of valid routes that visits every city exactly once and minimizes the sum of route costs.Route cost is the sum of Euclidean edge distances, and each route begins and ends at the depot.

3 Related Work

Prior work includes hand-designed local search, meta-heuristics, and neural construction or improvement methods for combinatorial optimization. These approaches motivate learning-based subproblem ordering for large VRPs, where the best selection order remains unclear.

  • Classical methods: Classical VRP methods use local search, genetic algorithms, ant colony methods, and meta-heuristics to iteratively improve solutions.Examples include move, swap, 2-opt, Tabu Search, guided local search, and Large Neighborhood Search.
  • Classical methods: POPMUSIC optimizes problem subparts iteratively and has been applied to map labeling, berth allocation, and p-median clustering.The paper draws inspiration from this large-scale combinatorial optimization framework.
  • Subproblem ordering: The impact of subproblem selection ordering in POPMUSIC-style methods is not well understood.Earlier work found that a last-in-first-out order can outperform random ordering, while this work orders subproblems using predicted improvement.
  • Deep learning methods: Deep learning approaches for combinatorial problems generally construct solutions autoregressively or iteratively perform local updates resembling local search.These categories include Pointer Network-based construction and learned improvement methods.
  • Deep learning methods: Learning-based VRP methods have approached LKH-3 solution quality on instances with N ≤100 but remain poorly understood at large scale.Reported successes include diverse sampling and learned selection among local search heuristics on small VRPs.
  • Scaling learned methods: Recent work also studies scaling learned methods for maximum independent set and integer linear programs through iterative deferral or imitation-learning pipelines.These examples broaden the context for learning decisions in large combinatorial problems.

4 An Iterative Framework for VRPs

The framework repeatedly selects a feasible local subproblem from the current VRP solution, delegates it to a subsolver, and incorporates the resulting subsolution. Spatial locality reduces an exponential selection space to a linear number of candidate subproblems.

  • Framework: Typical CVRPs may contain exploitable structure, motivating approximate solution as a sequence of smaller subproblems delegated to efficient subsolvers.The framework has a subsolver component and a learned model that identifies suitable subproblems.
  • Framework: At each iteration, the learned selector chooses a smaller subproblem from the current solution, the subsolver optimizes it, and the global solution is updated.Restricting subproblems to cities from selected routes preserves feasibility because unselected routes remain valid.
  • Framework: The selector should identify subproblems whose subsolver solutions produce large objective improvements.The framework evaluates selection quality through the resulting change from X to X′.
  • Restricted subproblem selection space: The unrestricted selection space contains O(2^R) route subsets, making direct learned consideration difficult.The framework therefore combines route-based subproblem construction with spatial restriction.
  • Restricted subproblem selection space: Restricting subproblems to exactly k routes leaves O(R^k) candidates, so spatial locality further selects k nearest route centroids around each route.This reduces the candidate set from exponential size to |S_k,local| = R = O(N).

5 Learning to Delegate

The framework learns to select promising local subproblems, delegates them to a subsolver, and iteratively updates the solution while preserving feasibility. It uses regression with a Transformer selector, spatially restricted candidates, and hill-climbing safeguards.

  • Iterative framework: The framework selects a smaller subproblem, applies a subsolver, and updates the current solution while preserving feasibility.Subproblems are restricted to cities visited by selected routes, leaving other routes valid.
  • Selection objective: The selector targets immediate improvement, defined as the current subsolution cost minus the subsolver’s new subsolution cost.The framework may accept non-positive improvements during selection, but test-time hill climbing retains the current subsolution when improvement is non-positive.
  • Search-space reduction: Spatial locality restricts the candidate search space from combinatorial growth to a linear-size set, making selector training feasible.The framework also caches previously predicted subproblems when possible to reduce computation.
  • Regression selector: Regression predicts subproblem quality, and the method selects the candidate maximizing current subsolution cost minus predicted new subsolution cost.This converts subproblem selection into value prediction rather than direct classification.
  • Network architecture: The selector uses a Transformer encoder over unordered city features, followed by a linear layer and mean pooling to produce fθ(S).City features include demand and location relative to the depot; the model is trained against subsolution cost.

6 Experiments and Analysis

The experiments evaluate the framework across distributions, scales, VRP variants, and subsolvers. The learned selector matches or improves solution quality while substantially reducing computation time, with benefits over random and heuristic selection and some limits in transfer.

  • Experimental scope: The evaluation covers uniform and clustered CVRPs, out-of-distribution instances, CVRPTW and VRPMPD variants, and alternative VRP subsolvers.Training, validation, and test instances are generated separately for each distribution; additional ablations are reported in the appendix.
  • Uniform CVRP: The method matches LKH-3’s solution quality with more than 7x to 15x less computation time across problem sizes N ∈ {500, 1000, 2000}.Longer runs can yield further improvements, while subsequent per-step computation is mostly independent of N after the initial subproblem evaluation.
  • Uniform CVRP: The learned selector achieves the best solution quality within reasonable time, while iterative baselines eventually converge after selecting all improving subproblems.Speedup is significant at low solution quality and improves toward the 95% LKH-3 target, but becomes less meaningful beyond that point.
  • Clustered and mixed CVRPs: The method achieves at least 2x speedup over Random in all clustered and mixed settings, with larger speedups on clustered distributions.This comparison uses the 95% LKH-3 solution-quality target.
  • Out-of-distribution generalization: Without finetuning, clustered-trained selectors generalize well to real-world CVRPs, whereas uniform-trained selectors perform worse than Random there.On N = 3000 uniform instances, the two selectors have similar performance; the real-world transfer differs substantially.
  • VRP variants: For CVRPTW and VRPMPD, the method achieves 8.2x and 31x speedups, compared with 5.9x and 20x for Random.The authors attribute the lower CVRPTW advantage to stricter visitation orderings imposed by time windows.
  • Alternative subsolver: With HGS as subsolver, speedups reach 103x for N = 2000 and 198x for N = 3000, versus 77x and 152x for Random.The authors suggest HGS’s calibration for medium-scale problems helps it function as a subsolver for larger VRPs.

7 Conclusion

The paper concludes that learning which subproblems to delegate enables efficient large-scale VRP improvement by combining spatially reduced selection with a competitive subsolver. It also highlights supervised learning with moderate-quality labels as effective and notes potential societal externalities.

  • Conclusion: The framework learns which subproblems to delegate, uses spatial locality to reduce the selection space, and accelerates competitive solvers on problems up to size 3000.The reported gains require an order of magnitude less computation time and include 1.5x to 2x over non-learning selection strategies.
  • Conclusion: Supervised learning with moderate-quality labels can achieve high-quality solutions through iterative subproblem selection.This contrasts with the reinforcement-learning emphasis of many earlier combinatorial-optimization methods.
  • Reproducibility: The implementation is publicly available through the authors’ code repository.The repository URL is provided in the paper.
  • Societal impact: The paper identifies potential negative externalities, including additional delivery traffic and stronger competition for brick-and-mortar retail.These concerns are presented as possible societal impacts of more efficient large-scale VRP solutions.

Checklist

The checklist records affirmative responses on scope, limitations, assets, data, experiments, and reproducibility. It also documents a potential limitation involving reduced CVRPTW speedup and convergence of learned selection order.

  • Scope and limitations: The authors state that the paper describes its contributions, scope, and limitations.The checklist refers readers to Section 6.5 for the limitations discussion.
  • Limitations: The authors identify slightly lower CVRPTW speedup and convergence of learned selection order to Random and Min Count as potential limitations.They state that the latter behavior is discussed and justified in Section 6.2.
  • Reproducibility: The experimental checklist records available training details, released code, plotted error bars, and reported compute resources.Full training details are placed in Appendix A.1, and the code is released through the repository cited in the paper.
  • Assets and data: The authors report that existing assets are open source and that the real-world dataset is open source, while most experiments use synthetic data.They state that no new assets were added and no consent process was needed for the data used.

A.1 Experiment Setup

The experiments evaluate learning-to-delegate on large uniform CVRP instances using a fixed initialization, generated subproblem-training data, and a Transformer selector. Training is limited to smaller instances, with transfer evaluated on larger problems and against learning baselines.

  • Data and baselines: Uniform CVRP instances use N = 500, 1000, 2000, and 3000, with uniformly sampled locations, demands from 1 to 9, and vehicle capacity C = 50.Each size has 2000 training, 40 validation, and 40 test instances.
  • Initialization: Initial solutions partition the space into 10 angular sectors and run LKH-3 for 100 steps on each partition.The same initialization scheme is used to compare methods fairly from rough starting solutions.
  • Training data: Training data selects the best-improving local subproblem over Dtrain = 30 iterative steps, using k = 10 nearest routes and a 500-step LKH-3 subsolver.The selector is trained on concatenated data from multiple problem sizes, while unchanged subproblems are not repeated.
  • Training data: Training-data collection is restricted to N = 500 and 1000 because transferred performance on N = 2000 and 3000 was satisfactory.This collection takes around 10 hours on 200 CPUs and is the most computationally intensive component.
  • Model and baselines: The selector represents each city with centered coordinates and rescaled demand, using a Transformer with six layers, eight heads, and model dimension 128.The model is trained with Adam for 40000 gradient steps, with hyperparameters selected on validation data.
  • Model and baselines: Comparisons include the Attention Model and NeuRewriter, with NeuRewriter retrained at size 100 because larger reruns encountered memory and fitting issues.The evaluation uses one NVIDIA V100 GPU and 20 CPUs.

A.2 Clustered and Mixed CVRP

The clustered and mixed CVRP experiments vary spatial structure, cluster count, and problem size to test generalization beyond uniform instances. A single model is trained across settings and evaluated separately, with reported improvements over Random.

  • Distributions: Clustered CVRP instances sample city locations around randomly generated centroids, while mixed instances combine uniform and clustered city locations.Cluster locations are sampled from U([0.2, 0.8]2), and city locations use standard deviation 0.07 before clipping.
  • Experimental design: Experiments cover N ∈ {500, 1000, 2000}, nc ∈ {3, 5, 7}, and both Clustered and Mixed distributions.Each combination uses 500 training, 10 validation, and 10 test instances.
  • Experimental design: Training excludes N = 2000 instances and concatenates the remaining combinations into a single set of 6000 problem instances.The model uses the same architecture and training hyperparameters as for uniform CVRP.
  • Results: A single trained model evaluated across all combinations demonstrates superior speedup and improvement over the Random baseline when run for a reasonable time period.Full test-set results are provided separately for the clustered and mixed settings.

A.3 Out-of-distribution CVRPs

The paper presents additional distribution descriptions and full results supporting out-of-distribution generalization for models trained on uniform and clustered CVRP data.

  • Generalization: The out-of-distribution evaluation reports CVRP distributions and full results for models trained on uniform and clustered CVRP.Training specifications are given in Appendices A.1 and A.2.

A.3.1 Uniform CVRP with N = 3000

For uniform CVRP at N = 3000, the clustered-trained model achieves slightly better improvement than the uniform-trained model, while their other performances are similar.

  • Results: The model trained on clustered CVRP shows slightly better improvement than the model trained on uniform CVRP at N = 3000.Otherwise, the reported model performances are similar.

A.3.2 Real-world CVRP

The framework generalizes across VRP distributions, variants, subsolvers, and initialization conditions by learning which local subproblems to delegate. Results show substantial speedups and competitive solution quality, with trade-offs depending on subproblem size and runtime.

  • Real-world CVRP: The learned selector generalizes to an unseen real-world CVRP distribution derived from a large-scale dataset.The clustered-CVRP model significantly outperforms the uniform-CVRP model and Random baseline, while the uniform model can perform worse than Random.
  • VRP variants: For CVRPTW and VRPMPD, the method provides significant speedup and improvement over LKH-3 within reasonable runtimes.The improvement over LKH-3 diminishes during very long runs.
  • Subproblem size: Using k = 10 tends to yield better eventual improvement than k = 5 in uniform CVRP, helping explain diminishing long-run gains in variant experiments.The paper partially attributes the effect to using k = 5 for CVRPTW and VRPMPD.
  • Subsolvers: With HGS, learned selection increasingly outperforms the solver as problem size grows, although HGS achieves better final quality at N = 500.For N = 2000 and 3000, full HGS convergence would require another order of magnitude more time.
  • Initialization: The learned selector outperforms Random across weaker initializations and achieves speedup above 1x for reaching 95% of the L = 100 LKH-3 solution quality.This indicates generalization from L = 100 training data to out-of-distribution initial solutions.
  • Architecture: The Transformer is important for maintaining performance over Random at higher solution qualities, while simpler summary-feature architectures remain effective.MLP performs best among the ablations, with Linear showing similar performance for N = 500 and 1000.
Loading 2107.04139v2…