Learning to delegate for large-scale vehicle routing
Authors: Sirui Li
Zhongxia Yan
Cathy Wu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: machine learning
combinatorial optimization
vehicle routing
decomposition

Abstract: 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, 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 $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.

Learning to Delegate for Large-scale Vehicle Routing
Sirui Li" MIT siruil@m memiil@mitteeeee
Zhongxia Yan
MIT zxyanCmit.eet edu
Cathy Wu MIT
cathyru@mit. edu
Abstract
Vehicle routing problems (VRPs) form class of combinatorial problems with wide practical applications. While previous heuristic or learning-basee works achieve decent solutions on small problem instances, their performance deteriorates in large problems. This article presents a novel leariin--augmente local search framework to solve large-scale VRP. The method iteratively improves the solution by identifying appropriate subproblems and 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 Transformer on a generated training set of problem instances. Our method accelerates state-of-the-arr VRP solvers by 10x to 100x while achieving competitive solution qualities for VRPs with sizes ranging from 500 to 3000. Learned subproblem selection offers 1.5x to 2x speedup over heuristic or random selection. Our results generalize to a variety of VRP distributions, variants, and solvers.
Introduction
Vehicle routing problems (VRPs) have enjoyed ample applications in logistics and ride-hailing services around the world for decades. While determining the optimal solution to a VRP
NP-hard 251 there have been numerous attempts to solve VRPs both exactly and approximately: provable algorithms have been designed for specific problem instances up to size 130
(28], and find good solutions in practice for problems of size more than 1000. However, heuristics methods often suffer from inflexibility due to extensive hand-crafting and the heavy computational burden from lengthy iterative procedures, as in the case LKH-3. For example, LKH-3 takes more than an hour to solve a size 2000 CVRP instance (Table D. which is impractical for applications such large-scale courier municipal services.
powerful heuristic solvers such as L.H-3 13 and HGS
49 4
More recently, machine learning methods inspired by the Pointer Network [50] provide alternatives to traditional solvers: the learning-based methods greatly reduce computation time while maintaining decent solution quality on small problem instances (less than 100 cities), by training on diverse sets of problem distributions either via supervised [50] or reinforcement learning [29] 20 However, these methods remain difficult to scale, and few report results on problems of size more than 200.
Our work aims to address scalability by learning to identify smaller subproblems which can readily solved by existing methods. Our learned subproblem selector guides the problem-solving process to focus local improvement on promising subregions. While there exists combinatorial number
Equal Contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of subproblems that can be selected at each step, we leverage spatial locality commonly found in combinatorial optimization problems to restrict the selection space size be linear in the problem size. Intuitively, objects far away from each other generally have very small influence on each other's s solution and are likely to be in different routes, so they should not be part of the same subproblem. The greatly reduced search space enables us to feasibly train an attention- based subproblem selector.
Our framework combines the advantages of learning and heuristics: our network identifies promising subproblems to improve upon, dramatically speeding up solution times. Using a competitive subsolver on subproblems, we achieve good solution quality without the high computational costs of running the subsolver on large problem instances. In summary, our contributions are:
We propose learning-to- terninggtt--eeleen te-deaeate, a learning- based framework for solving large-scale VRPs by iteratively identifying and solving smaller subproblems.
Despite the high dimensionality and NP-hardness of subproblems, we design a Transformer architecture that effectively predicts the subsolver's solution quality for subproblem.
With extensive validation, we show that and/or objective improvements over both its base subsolver and random (or heuristic) subproblem selection, for variety of VRP variants, distributions, and solvers.
offers significant speedups
2 Preliminary: Capacitated Vehicle Routing Problems (CVRP)
In CVRP, there is a depot node O and city nodes {1...., NY. Each city node i has demand de to fulfill. A vehicle with capacity C' starts and ends at the depot and visits route of city nodes such that the sum of city demands along the route does not exceed C, after which the vehicle starts a new route again. The objective is to find valid solution minimizing the solution cost. We define the following:
Route: a sequence of nodes, where the first and last node are the depot 0, and the rest are city nodes. In valid route, the sum of demands of the city nodes does not exceed C.
Route cost: the sum of edge costs for the sequence of nodes. For an edge from node to node j, the edge cost is the Euclidean distance between node and j.
Solution: a feasibbee solution consists of set of valid routes visiting each city exactly once.
Solution cost: the sum of route costs for all routes in the solution. An optimal solution is feasible solution with the minimum solution cost.
Subproblem: a CVRP consisting of the depot, a subset of cities, and corresponding demands.
3 Related Work
Classical methods. Heuristics for solving combinatorial optimization problems have been studied for decades. The most powerful methods, such as local search M. genetic algorithms Rd. and ant colony methods [IO), involve iteratively improving the solution in hand-designed neighborhood. For example, move, swap (52). and 2-opt [9] are well-known heuristics for the traveling salesman and vehicle routing problems. The competitive VRP solver LKH-3 [ uses the Lin-Khanighan heuristic [26] as a backbone, which involves swapping pairs of sub-routes to create new routes, whereas the CVRP solver HGS 4y 48) uses hybrid genetic and local search procedure achieve ofate-of-the-art solution qualities on problems up to size 1000. While LKH- ttckklss
tackless a variety of
VRP variants, the publicly available implementation of HGS only solves CVRP.
For large problems, low-level heuristics are combined with meta-heuristics, including Tabu Search with Adaptive Memory 40. guided local search [51), and Large Neighborhood Search 35 The inspiration for our work derives from Partial OPtimization Metaheuristic Under Special Intensification Conditions (POPMUSIC), which iteratively optimizes problem subparts and has been used to solve problems as diverse as map labeling 24], berth allocation 22). and p-median clustering [3
Despite the promise of the POPMUSIC framework for large-scale combinatorial optimization, the impact of certain design choices is not well understood, such as the subproblem selection ordering
2 We refer to the IKH-3 code at attp:://gghhuu.com////a/////////
We refer the HGS code

---

depot city node route segment route centroid
(a) step
Subssoiver
step
(e)
Figure I: Our iterative framework for VRPs. (a) At each time step, we start with a current solution X. Circles are city nodes, blue lines are route segments, and the red star is the depot. (b) We aggregate each route by taking the centroid of all city nodes in the route. (c) For each route, we define a corresponding subproblem as the k-nearest neighbors of the route. Two such subproblems with k = 3 are shown. (d) Our subproblem selector selects subproblem S' (yellow). (e) We feed S into the subsolver to get new subsolution X's. The red edges are updated by the subsolver. (f) We update X to new solution X' with X's, then repeat (b)-(f).
and size 4 For example, it is not clear how meaningfully order the subproblems. One early work in this direction demonstrated that a last-in-first-our stack order performs better than random B Our work provides natural approach order the subproblems based predicted improvement.
Deep learning methods. Recently, there has been a surge of interest training deep neural networks (DNN) to solve combinatorial problems. As observed by Kwon et al. [21, most methods
fall into one the following two categories: 1) construction methods 29 20) where an autoregressive model such the Pointer Network [50] directly outputs solution, and 2) improvement methods [
13,, where the DNN iteratively performs local updates to the solution, resembling local search.
These methods are approaching the solution quality of L.HH3 13 on small problem instances. For example, Kwon et al. [21] extends a construction approach 20 to encourage more diverse output samples on N < 100 VRPs. Among improvement methods, Lu et al. [7 learn a meta-controller to select among set of local search heuristics, marking the first learning- brreiing--asedd approach to outperform LKH-3 on N < 100 VRPs. Despite these successes, learning- baase based approaches for large-scale VRPs are poorly understood. addition, all of the aforemeenioned methods are trained using deep reinforcement learning; for large problems, trajectory collection becomes prohibitively expensive.
Scaling up learning methods. A few recent works have begun investigate scaling learned networks for NP-hard graph problems. For example, Ahn et al. [2] propose an iterative scheme called learning srenninng-hht--ee what-to-defer for maximum independent set. At each stage, for each node in the graph, the network either outputs the solution for the node or defers the determination to later stages. Song et al. [S]] proposes an neniation-learning--
pipeline for Integer Linear Programs (ILP), where each stage they partition all variables into disjoint subsets, and use the Gurobi [2] ILP solver to solve the partitions. Due to differences graph structure, our work presents a more natural scheme to handle VRP constraints and structures. A few works attempt incorporate learning to decompose large-scale VRPs 47 B1 However, the decomposition approaches proposed appear to be experimentally less effective than ours.
4 An Iterative Framework for VRPs
While CVRPs are NP-hard and thus require worst-case exponential time the problem size to solve optimally, typical CVRPs exhibit structure that practical solvers may exploit. We hypothesize that in

---

such situations, the larger problem can be efficiently approximately solved as sequence of smaller subproblems, which can be delegated to efficient subsolvers. To test this hypothesis, we propose learning-based, iterative framework with two components: 1) subsolver capable of solving small problem instance (exactly or approximately), and learned model for identifying suitable subproblems within larger problem to delegate to the subsolver.
Algorithm 1: Learning Delegate
Input: Problem instance P, initialized solution X, subproblem selector So. subsolver Subsolver, number of steps T, parameter & denoting the size of subproblems
for Step 1 I: 7 do
2
Local f- ConstuceSubroobemssPX.X
S f fo fo
X f Subsolver(S))
X + X's U Xp,s
end for
We illustrate our iterative framework in Figure which takes in a problem instance P with a feasible initial solution Xo. At each step, given the current solution X. we select smaller subproblem C with our learned model ʃa then apply the subsolver to solve S; we then update with the new solution for S. To maintain feasibility after an update, cities a subset of routes from X. Since routes with citics in P \ S remain valid routes, we obtain new feasible solution X' X XP,s. where X's is the subsolution for S and X mms consists of unselected routes from X. Intuitively, a strong fo should identify a subproblem S such that the subsolver solution X's results in large improvement in objective from X to X".
restrict S to be the set S of visited
4.1 The Restricted Subproblem Selection Space
As the number of routes in = O(N), the cardinality of the selection space O(2 which is exponential in the problem size N and difficult for learned models to consider. If we restrict each subproblem to cities from exactly & routes, there are still (x) O(R*) subproblems to consider. Therefore we further restrict selection to subproblems with spatial locality. As shown Figure dd), we only consider subproblems from So.lo where each subproblem is centered around particular route r and contains the & routes whose centroids have the smallest Euclidean distance to the centroid of r. In this way, we reduce the selection space to |Sk, = R O(N) from [S] O(2~). ). In Algorithm 1, we refer to this restriction as ConstructSubproblenn Our restriction to a local selection space is motivated by the fact that many combinatorial optimizations problems have inherent spatial locality, i.c. problem entities are more strongly affected by nearby entities than faraway entitics. Earlier heuristical methods such as POPMUSIC 42 leverage similar spatial locality.
5 Learning to Delegate
In this section, we discuss criteria for selecting subproblems, and how to train the subproblem selector.
Improvement the criteria for subproblem selection. Given selected subproblem S with current solution Xs on the subproblem, we obtain from LKH-3 a new solution X's on the same We then define the immediate improvement
subproblem (step (d) to (e) in Figure I
8(S) = el (Xs) o(X's
where o(Xs) is the total cost of subsolution Xs and 8(S) is the improvement in the solution cost. In this way, the sum of improvements along 7' steps is the total improvement in solution quality. As we empirically find that providing the previous subsolution X to the subsolver may trap the subsolver in local optimum, we withhold Xs from the solver and thus may see non non-positive improvement 6(S) < O, especially after many steps of subproblem selection. At test time, to avoid worsening the objective, we adopt a hill-climbing procedure such that when 5(S) S we keep Xs instead of X's (Figure [ step (e)). With proper masking, we avoid selecting the same non-improving subproblem again. The hill-climbing and masking procedures are applied to both our subproblem-selectinn network fe and the three heuristic selection rules, described in 6.1 to maintain fair comparisons.

---

Transformer Encoder
Linear
Mean-Pool
Subsolution cost
Transtormer Encoder
Linear
Mean-Pool
Subsolution cost
x6 layers
Multi-head attention
Linear
Cache
Subsolution
cost
Figure 2: Our Transformer architecture. At each step of our framework (Figure 1 (c), featurize subproblem S E Soolocal into a column vector of unordered cities. We apply the Transformer encoder with multiple multi-head attention layers and final linear layer, before mean-pooling over the cities to generate the predictions fS)),, which we fit to the subsolution cost c(X's). When possible, we retrieve previously predicted subproblem from a cache to minimize computation.
Subproblem selection. The goal of our subproblem selector is to select the subproblem leading to the best immediate improvement. While subproblem selection does not directly optimize for the total improvement, we observe that (1) our subsolver may perform many low-level operations internally, high-level problem selection may still benefit greatly from maximizing the immediate
improvement, and (2) numerous reinforcement learning approaches to VRP (53
[X] choose a
small discount factor such as = 0.25 when optimizing a multi-step objective
Σ 7/ as doing
encourage faster convergence. Moreover, our subproblem selector may instead be trained multi-step search data to select subproblems offering the best multi-step improvement.
Ground-trun truth labels. Our restricted selection space allows us enumerate all possible subprob- lems at each step. In typical large scale CVRP instance with N = 2000 cities, a solution consists of roughly R 200 routes, the size of the selection space is 200. We obtain the immediate improvement 8(S) by rumning the subsolver on each subproblem S E Sg. Although our enumer- ation strategy is feasible for generating training data, it is much too slow execute on test CVRP instance. However, our subproblem selector can predict the best immediate improvement at test time (that is, without running the subsolver on multiple subproblems), then of both worlds to obtain a fast and accurate selection strategy.
combine the best.
Selection strategies: regression classification. Given labeled dataset, may treat the task of identifying the best subproblem as either regression or classification. In the context imitation learning with greedy expert, the former learns value function while the latter learns a policy. Due to space limitation, we focus discussion on regression and reserve comparison with classification for Appendix A.5.1. The regression-basee subproblem selector uses trained fo to predict the subsolution cost c( ((X)); ) we then simply compute arg max c(Xs) - (S) to select the hest subproblem.
Network architecture. We define fe with Transformer encoder architecture 451 The input representing each subproblem S is the unordered set of featurized cities in S. The features for each city consist of the demand d and the location of the city (x, y) relative the depot. As do not feed the existing subsolution Xs to the subsolver, the dense multi-head attention mechanism does need to be modified take the routes in X into account. The output of the Transformer encoder fed into a linear layer then meolep to obtain the scalar prediction fo()). In Appendix A.5.5, we perform ablation study with simpler architectures.
Loss function. We empirically find mean squared error to be less stable than Huber loss set our loss function
16 which
-(())) ([f((S) c(X'))
if ff((S) c(x')) < otherwise
L(0; S)
5

---

Figure 3: Instances from N = 2000 CVRP distributions. From left to right: instance from uniform, mixed (n. cluster centers), clustered (n. 3 cluster centers), and real-world. The red star is the location of the depot, while blue dots are cities sized proportional to demand.
Experiments and Analysis
We illustrate the CVRP distributions considered in our work in Figure G We perform extensive experiments to evaluate our learning framework, aiming to answer the following questions:
1. Uniform distribution. How does our method compare with baselines, terms of solution time and quality, on problems with uniformly distributed cities?
2. Clustered distributions. How does our method perform on problems with clustered cities?
3. Out-of-distribution. Can our model generalize, such as to larger or real-world instances?
4. VRP variants. Can our method address more sophisticated VRPs? E.g., CVRP with Time
Windows (CVRPTW) 37 or VRP with Mixed Pickup and Delivery (VRPMPD)
B3
5. VRP solvers. Can our method be adapted to leverage other VRP subsolvers?
We reserve additional ablations on subproblem selection classification, effect of subproblem size k and discussion of asymptotic behavior, subproblem selection with the HGS subsolver, effect of weaker initialization methods, and comparison with simpler architectures for Appendix A.5.
6.1
Setup
We briefly describe experimental setup in the main text and defer full details to Appendix A. Given a particular distribution of VRP, we generate separate sets of training, validation, and test problem instances. Unless otherwise stated, our validation and test sets contain 40 instances each. For each problem instance, we generate a rough initial solution by partitioning it into disjoint subsets cities and briefly running the subsolver each subset. Due to its compatibility with many VRP variants, we use LKH-3
as the subsolver for all VRP distributions unless otherwise stated.
We generate the training set by running our iterative framework and selecting subproblems by enumerating the subsolver on all S E Sg. As many subproblems remain unchanged from to X', we use previously cached subsolutions when possible instead of re-running the subsolver. While generation times differ depending on several factors, typically takes less than hours with 200 Intel Xeon Platinum 8260 CPUs to generate training set of 2000 instances.
To avoid training multiple models for different problem sizes N, we train single model for each VRP distribution with combined data from multiple N E {500, 1000, 2000}. Training takes at most 8 hours on a single NVIDIA V100 GPU. To exploit symmetry in problem instances, we apply rotation and flip augmentation at training time. To evaluate trained selectors on a problem instance, we run the iterative selection framework on single CPU, with disabled multithreading and no GPU.
We select the best hyperparameters via manual search based on validation set performance. We record final results the test set as the mean and standard error 5 runs with different random seeds.
Baselines. By default, we use LKH-3 as the subsolver, we run LKH-3 on the full problem instances with our initialization for 30000 local update steps, which takes 2-3 hours on average for N = 2000. If using HGS as the subsolver, we also run HGS on the full problem instances for the same amount of time as our LKH-3 baseline. These baselines allow us to compute the speedup of our framework over the subsolver alone. We also compare against OR Tools (30, another open source

---

Table 1: Performance and computation time for uniform CVRP. For problem instance sizes N E {500, 1000, 2000), we report the objective values (lower is better) of our method and baseline methods, averaged across all instances in the test set. Note that the cost is the total distance of routes in the solution. LKHH3 (30k) runs I.KH-3 for 30k steps to near convergence, while LKH-3 (95%) the 95% solution quality. Random, Count-based, Max Min Distance, and Ours (Short) run until matching LKH-3 (95%) in solution quality, with the speedup reported in parentheses, while Ours (long) runs for twice amount time as Ours (Short).
N 500
N 1000
N 2000
Method
Cost
Time
Cost
Time
Cost
Time
LKH-3 (95%)
62.00
4.4min
120.02
18min
234.89
52min
IKK-3 (30k)
61.87
30min
119.88
77min
234.65
149min
OR Tools
65.59
15min
126.52
15min
244.65
15min
AM sampling
69.08
4.70s
151.01
17.40s
356.69
32.29s
AM greedy 68.58
25ms
142.84
56ms
307.86
147ms
NeuRewriter 73.60
58s
136.29
2.3min
257.61
8. 8.im
Random 61.99
71s (3.8x)
120.02
3.2min (5.5x)
234.88
6.4min (8.0x)
Count-based 61.99
59s (4.5x)
120.02
1.im (8.2x)
234.88
5.3min (10x)
Max Min 61.99
59s (4.5x)
120.02
2.5min (7.0x)
234.89
5.2min (10x)
Ours (Short) 61.99
38s (7.0x)
119.87
1.5min (I2x)
234.89
3.4min (15x)
Ours (Long) 61.70
76s
119.55
3.0min
233.86
6.8min
heuristic VRP solver employing iterative search, terminating runs at 15 minutes, as OR Tools stops improving the solution within this time for all instances.
We include results for previous learning methods AM 120 and NeuRewriter 7 These do not outperform LKH-3 even small problem sizes, and learning methods have had more difficulty generalizing to larger instances. In fact, these methods are trained on problems of size N < 100, and find that they yield poor solutions N 2 500 without architecture modifications and extensive re-training. The AM and NeuRewriter results demonstrate the difficulty of scaling up previous learning methods. We do not initialize OR-Tools, AM, and NeuRewriter because we empirically find that these methods have limited solution capability and do not improve our decent initialization.
To validate our subproblem selector's ability identify promising subproblems, design three additional baselines that employ our iterative framework using hand-crafted heuristics to select subproblems. The three heuristics that we use are: (1) Random, selecting subproblem S from Sy.tocal uniformly: (2) Count-based, which avoids repetitive selections by selecting the subproblem centered the route whose city nodes have been selected cumulatively the least often in previous steps; and (3) Max Min Distance, which encourages coverage of the entire problem instance by selecting subproblems with the maximum distance from the nearest centroid of previously selected subproblems, We run the heuristic baselines with the same setup as our learned subproblem selector.
Metrics. We refer to two metrics to compare our method against baseline methods.
1. Improvement over method X: at specified computation time, the improvement of method Y over method X is the total improvement of method Y minus that of method X.
2. Speedup over method X: at specified solution quality that method X attains, the speedup of method Y over method X is the computation time required for method X to attain the solution quality divided by the time for method Y to attain the solution quality.
We define 95% solution quality of running a method X over a computation time as the solution quality with 95% of the total improvement. We report speedup at 95% solution quality of a method because X may take a disproportionate amount of time on the last 5% of improvement; reporting speedup at 100% solution quality inflates the speedup.
7

---

Stupo Imprommmmmmn
UR0- 10h 34 Immo meaa
Ironvvemet over L013
35
Impotman tree
20
Se
0.5
Random Hin Count
-1.0
307
101
107
10'
10" 12"
10"
10
10"
10"
30"
20'
10'
Time 00
Time 1st
Thmre 03)
Figure 4: Improvement over LKH-3 for uniform CVRP. The x-axis is the computation time and extends until LKH-3 has completed 30k steps. The vertical lines represent the computation times of Ours (Short) and Ours (Long) from Table The three subplots correspond to N 500 (left), N 1000 (middle), and 2000 (right).
Speedtip Over 001-3
Random
107
Max Min Dist
Count
Ours
10
50
60
70
80
90
100
20
40
60
80
100
20
40
60
80
100
16 LUCH- 30K Steps improvement.
LKH-3 30k Steps Improvement
LK-K 30k Steps Improvement
Figure 5: Speedup over LKH-3 for uniform CVRP. The x-axis is the solution quality attained, measured percentage of the LKH-3's maximum improvement. The dashed vertical line represents the 95% solution quality used to compute the speedup, as mentioned in Table | The three subplots correspond to N 500 (left), N 1000 (middle), and N 2000 (right).
6.2 Uniform CVRP Distribution
As in Table our method achieves the best performance for all problem sizes, matching LKH-3's solution quality with more than 7x to 15x less computation time and offering even more improvements with longer computation time. Although we need evaluate all R ( subproblems of the initial solution with our subproblem selector, subsequent per-step computation time of our method is mostly independent of the problem size N since we only evaluate changed subproblems.
Running LKH-3 for 30k local update steps achieves superior performance to all previous other heuristic and learning-basee based baselines. Its solution quality scales well to large problem sizes, yet the solution time is significantly longer. Previous learning-based methods, though fast, result in much worse solution qualities. Our heuristic baselines Random, Count-based, and Max Min Distance demonstrate that our iterative framework, even without the learned subproblem selector, may achieve over 5x 10x speedup over LKH-3. Nevertheless, results demonstrate that learning the subproblem selector may offer an additional 1.5x speedup over non-learning heuristics.
In Figure 4 demonstrate the solution quality of our method and basclines compared LKH-3. We see that, compared to baseline methods, the learned subproblem selector obtains the best solution quality when run for reasonable amount of time. The improvement of most methods based our iterative framework converge when run for an excessive amount of time; this is unsurprising, as Random and other baselines eventually able to select all subproblems offering improvements.
In Figure we demonstrate the speedup of our method over LKH-3, comparing to baseline methods. The speedup is often significant even at low levels of solution quality, and improves with higher solution quality. The speedup is not as meaningful beyond 95% LKH-3 solution quality, as LKH-3 takes disproportionate amount of time to attain the last 5% of improvement.
6.3 Clustered and Mixed CVRP Distributions
We further examine the framework's performance on CVRP distributions with clusters of cities, such as studied in 8 4 centroids then sampling the cities around the centroids. The mixed distribution samples 50% of the cities from uniform distribution and the rest from around cluster centers. We generate dataset
We generate a clustered instance by first sampling (x,y) locations of cluster

---

Speocup Over L333
Ours (Urifor)) Ours (Clustured)
107
103
10-4
60
80
100
20
60
80
100
% UGH 3 50k Stops improvement
LS04 30k Stops Improvement
Figure 6: Speedup in out-of-distributioo CVRPs. The speedup of our model the N 3000 uniform distribution (left) and N = 2000 real-world distribution (right) without finetuning. Ours (Uni- form) and Ours (Clustered) trained the uniform and clustered CVRP distributions, respectively. Note that LKH-3 is run for 50k steps for N 3000 instances.
of instances for every (N, ne, m) {500, 1000, 2000} {3, 5, 7) x {Clustered, Mixed} and train single model on the entire dataset. We evaluate the model on validation and test sets 10 instances per (N, ney m) combination (i.e. 60 instances per N). Due to space limitation, we provide more details about the data distribution and full results in Appendix A.2.
Table reports speedups of our method and the Random baseline over LKH-3. Our method sees at least 2x speedup over Ran- dom in all settings. We see larger speedups for clustered distributions than for mixed uniform distributions (Table D
Table Speedup for N 2000 clustered and mixed CVRPs at 95% LKH-3 30k solution quality.
Setting
The = 3
Th =
5
ne = 7
Ours
26x
18x
25x
Clustered
Random
11x
7.5x
9.0x
6.4 Out-of-distribution Generalization
Ours
13x
14x
14x
Mixed
Random
6.6x
6.4x
7.6x
We study how our subproblem selector gen- cralize to a uniform CVRP distribution with larger problem size N = 3000 and to real- world CVRP distributions, both unseen at training time. The real- world CVRP distribution derives from CVRP dataset 4 consisting of 10 very-large- large-sceell instances on Belgium regions with N ranging from 3000 to 30000 and randomly generated demand distribution. To generate instance, subsample the cities in region without replacement to N = 2000, while regenerating the demands to match our training distribution. For each original instance, we generate 5 subsampled instances form the test set of 50 total instances. We visualize the original and subsampled datasets in Appendix A.3.
We apply subproblem selectors trained uniform and clustered data without finetuning on the new data distributions and report the speedup comparison with the Random baseline Figure We see that when transferring to N 3000, subproblem selectors trained offer similar performance. However, the model trained on the clustered distribution generalizes well to the real-world distribution while the model trained the uniform distribution fails to generalize, with worse speedup than the Random baseline. These results suggest that the domain variability of the clustered distribution strongly improves generalization performance.
uniform and clustered data
6.5 Other VRP Variants
While our previous experiments vary the distribution of city locations in CVRP, here we consider two VRP variants with uniform city distribution but with additional constraints: CVRPTW (37] and VRPMPD 33 The former specifies hard time window constraint for visiting each city, while the latter specifies pick up and delivery constraints in addition to capacity constraint. A detailed description of the variants can be found in Appendix A.4.
Similar to CVRP, we observe significant speedup with our iterative framework alone, while learning offers additional speedup. For CVRPTW, our method offers a 8.2x speedup while our Random baseline offers a 5.9x speedup; for VRPMPD, our method offers 31x speedup while our Random baseline offers 20x speedup. We suspect that the time window constraint in CVRPTW imposes strict orderings the order of city visitations, increasing the difficulty for the subproblem selector.

---

Speedup Over L3W3
Ours
10'
1.0
10:1
20
40
80
100
60
80
100
%6 UGH 30k Stops improvement
LJ0 30k Stops Improvement
Figure 7: Speedup in other N 2000 VRP variants, CVRPTW (left) and VRPMPD (right).
Sposoup Over Subsoter
12
Rendom ILKI0
Rendem (LKi)
Rendom
Rendom (HGS)
Ours (HDS)
Durs (MGS)
Figure 8: Speedup with the HGS subsolver on uniform CVRP. We compare the speedup of our
method equipped with LKH-3 HGS as the subsolver for N 2000 (left) and N 3000 (right).
6.6 A State-of-the-Art CVRP Subsolver: HGS
While we focus our analysis on LKH-3 3 due to its applicability to many variants of VRPs, HGS 40 is a state-of-the art solver focused on CVRP. Thus, we apply our method to train subproblem selectors for the HGS subsolver. We discuss the full experimental setup and results in Appendix A.5.3.
With HGS as the subsolver, we observe a 103x speedup for our method on N = 2000, compared with 77x speedup for the Random baseline. Similarly, observe 198x speedup for method on N = 3000, compared with 152x speedup for our Random baseline. The large speedup may be due to the fact that HGS is designed and calibrated for medium-scale problems of 500 to 1000 cities, allowing it to function better as a subsolver for large-scale VRPs.
7 Conclusion
This paper presents learning-based framework which learns which subproblems to delegate to subsolver when solving large VRPs. Spatial locality allows learn the subproblem selector reduced selection space. The proposed method accelerates competitive VRP solvers on problems of sizes up 3000, requiring order of magnitude less computation time. We identify a 1.5x to 2x speedup over non-lcarning selection strategies. Our results generalize to variety of VRP distributions, variants, and solvers.
While most previous learning- baaningg-basedd combinatorial optimization methods forcement learning due to the unavailability of optimal solutions high-quality labels, work highlights the counterintuitive effectiveness of supervised learning with only canderate-qualinn labels achieve high-quality solutions with iterative subproblem selection. An interesting line of future work may explore other ways to effectively leverage moderate-quality labels for combinatorial opti- mization tasks. In partieular, discuss in Appendix A.6 the applicability of method other combinatorial optimization problems with spatial locality. We helieve that our learning framework can serve powerful technique for both the learning and operations research communities to scale up combinatorial optimization solvers.
2 rely on rein-
Our code is publicly available at http::///gttto..ccmaatt.aaaaaaaa
Negative Social Impact. Enabling more efficient solutions of large-scale VRPs may exhibit nega- tive externalities such inducing additional traffic from delivery vehicles and centralizing services that pose stronger competition to brick-and-moot mortar retail.
10

---

8 Acknowledgements
This research was supported by MIT Indonesia Seed Fund, US DOT DDETFP, and the MIT-IBM Watson AI Lab. The authors are grateful to the anonymous reviewers for detailed comments that substantially improved the article. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing (HPC, database, consultation) resources that have contributed the research results reported within this paper. We also thank Zongyi Li for helpful discussions and technical advice throughout the project.
References
[1] Aarts, E., Aarts, E. H., and Lenstra, J. K. (2003). Local search in combinatorial optimization. Princeton University Press.
[2] Ahn, S., Seo, Y., and Shin, J. (2020). Learning what to defer for maximum independent sets, In International Conference on Machine Learning, pages 134-144. PMLR.
[3] Alvim, A. C. and Taillard, E. D. (2013). Popmusic for the world location-routing problem. FURO Journal Transportation and Logistics, 2(3):231-254,
[4] Arnold, F., Gendreau, M., and Sörensen, K. (2019). Efficiently solving very large-scale routing problems. Computers & Operations Research, 107:32-42.
[5] Blažewicz, J., Domschke, W., and Pesch, E. (1996). The job shop scheduling problem: Conven- tional and new solution techniques. journaa of operational research, 93(1):1-33,
[6] Bosman, P. A. and La Poutré, H. (2006). Computationally intelligent online dynamic vehicle routing by explicit load prediction in an evolutionary algorithm. In Parallel Problem Solving from Nature-PPSN IX, pages 312-321. Springer.
[7] Chen, and Tian, Y. (2019). Learning to perform local rewriting for combinatorial optimization. In Wallach, H., Larochelle, H., Beygelzimer, A., d Alché-Bus Bathé-Bu..aa F., Fox, E., and Garnett, R., editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc.
[8] Christofides, N., Mingozzi, A., and Toth, (1979). Loading problems. N. Christofides and al., editors, Combinatorial Optimization, pages $39-369.
[9] Croes, G. A. (1958). A method for solving traveling-salesme problems. Operations research, 6(6):791-11..
[10] Dorigo, M., Birattari, M., and Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4):28-39.
[11] Gehring, H. and Homberger, J. (1999). A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. Proceedings of EUROGEN99, volume 2, pages 57-64. Citeseer.
[12] Gurobi Optimization, L. (2021). Gurobi optimizer reference manual.
[13] Helsgaun, K. (2017). An extension of the in-Keemighan-hellggum tsp solver for constrained traveling salesman and vehicle routing problems. httt://akira. http://kkrraar.ec.kkkkk/l/ll het..kk//keld//ssercchll
LKH-3/
[14] Helsgaun, K. (2018). Using popmusic for candidate set generation in the lin-kemighan-helsgan tsp solver. Roskilde Universitet, 7.
[15] Hottung, A. and Tierney, K. (2020). Neural large neighborhood search for the capacitated vehicle routing problem. In 24th Europeun Conference Artificial Intelligence (ECAI 2020).
[16] Huber, P. J. (1992). Robust estimation of a location parameter. In Breakthroughs in statistics, pages 492-518. Springer.
[17] Kallehauge, B., Larsen, J., Madsen, O. B., and Solomon, M. M. (2005). Vehicle routing problem with time windows. In Column generation, pages 67-98, Springer.

---

[18] Khalil, E. B., Dai, H., Zhang, Y., Dilkina, B., and Song, L. (2017). Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems.
[19] Kohl, N., Desrosiers, J., Madsen, O. B., Solomon, M. M., and Soumis, F. (1999). 2- 2-path cuts for the vehicle routing problem with time windows. Transportation Science, 33(1):001-116.
[20] Kool, W. van Hoof, H., and Welling, M. (2019). Attention, learn to solve routing problems! In International Conference on Learning Representations.
[21] Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y.. and Min, S. (2020). Pomo: Policy optimization with multiple optima for reinforcement learning. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 21 11188-20 28198.118 Curran Associates, Inc.
[22] Lalla-Ruiz, E. and Voss, S. (2016). Popmusic as a matheuristic for the berth allocation problem. Annals of Mathematics and Artificial Intelligence, 76(1-2):173-189.
[23] Laporte, (2009). Fifty years of vehicle routing. Transportation science, 43(4):408 416.
[24] Laurent, M., Taillard, É. D., Ertz, O., Grin, F., Rappo, D., and Roh, S. (2009). From point feature label placement to map labelling. In Proceedings, metaheuristic international conference (MIC'09), Hamburg. Citeseer.
[25] Lenstra, K. and Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2):22-2277.
[26] Lin, S. and Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2):498-51
[27] Lu, H., Zhang, X., and Yang. S. (2020). A learning- iterative method for solving vehicle routing problems. In International Conference on Learning Representations.
[28] Lysgaard, J., Letchford, N., and Eglese, W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2):423-445.
[29] Nazari, M., Oroojlooy, A., Snyder, I.., and Takac, M. (2018). Reinforcement learning for solving the vehicle routing problem. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc.
[30] Perron, L. and Furnon, V. (2019). Or-tools.
[31] Poullet, J. (2020). Leveraging machine learning solve The vehicle Routing Problem with Time Windows. Phl) thesis, Massachusetts Institute of Technology.
[32] Renaud, J. and Boctor, F. F. (2002). A sweep- based algorithm for the fleet size and mix vehicle routing problem. European Journal of Operational Research, 140(3):618 628.
[33] Salhi, and Nagy, G. (1999). cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the operational Research Society, 50(10): 1034 1042.
[34] Santini, A., Schneider, M., Vidal, T., and Vigo, D. (2021). Decomposition strategies for vehicle routing heuristics.
[35] Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In International conference on principles and practice of constraint programming, pages 417-431. Springer.
[36] Sivanandam, S. and Deepa, S. (2008). Genetic algorithms. In Introduction to genetic algorithmss, pages 15-37. Springer.
[37] Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):25
12

---

[38] Song, J., Lanka, R., Yue, Y., and Dilkina, B. (2020). A general large neighborhood search framework for solving integer linear programs. In Larochelle, H.,, Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 20012-20023. Curran Associates, Inc.
[39] Taillard, É. D. (2003). Heuristic methods for large centroid clustering problems. Journal of heuristics, 911:511-73.
[40] Taillard, É. D., Gambardella, L. M., Gendreau, M., and Potvin, J.-Y. (2001). Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 135(1):1-16.
[41] Taillard, É. D. and Helsgaun, K. (2019). Popmusic for the travelling salesman problem. European Journal of Operational Research, 272(2):420 429.
[42] Taillard, É. D. and Voss, S. (2002). Popmusic-pante optimization metaheuristic under special intensification conditions. In Essays and surveys in metaheuristics, pages 613-629, Springer.
[43] Taillard, É. D. and VoB, S. (2018). POPMUSIC, pages 687-701. Springer International Publishing, Cham.
[44] Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., and Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, (57(3):845-855)
[45] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. (2017). Attention is all you need. In Guyon, I,, Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
[46] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations.
[47] Ventresca, M., Ombuki-Berman B., and Runka, A. (2013). Predicting genetic algorithm performance on the vehicle routing problem using information theoretic landscape measures. European Conference on Evolutionary Computation Combinatorial Optimization, pages 215-225. Springer.
[48] Vidal, T. (2020). Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. arXiv preprint arXiv:2012. 10384.
[49] Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., and Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611- 624.
[50] Vinyals, O., Fortunato, M., and Jaitly, N. (2015). Pointer networks. In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.
[51] Voudouris, C. and Tsang, E. P. (2003). Guided local search. In Handbook of metaheuristics, pages 185-218. Springer.
[52] Wu, C., Shankari, K., Kamar, E., Katz, R., Culler, D., Papadimitriou, C., Horvitz, E., and Bayen, A. (2016). Optimizing the diamond lane: A more tractable carpool problem and algorithms. In 2016 IEEE 19th International Conference on Intelligent Transportation Systems (TTSC), pages 1389-1396. IEEE
[53] Yolcu, E. and Poczos, B. (2019). Learning local search heuristics for boolean satisfiability. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R.. editors, Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes] See Section 6.5. We discuss our method gets slightly less speedup on CVRPTW than CVRP or VRPMPD; section 6.2, we also discuss our learned subproblem-selecteee selection order at convergence are the same as Random and Min Count order, which can be seen as potential limitation, but we provide justification in the same Section (6.2) as well.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the negative social impact paragraph in Section 7 (Conclusion)
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] As stated in Section (Conclusion), our code is released at athhtps: // httg//gttttbbbt com wwtoommmittuu-tomm lab/
dearning-to-delegan
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We briefly mention the training details in Section 6.1 of the main paper, and we put the full details Appendix A.1.
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We plot error bars on all of our experiment figures in Section 6.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6.1.
4. If you using existing assets (e.g., code, data, models) or curating/releusing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use the LKH-3 and HGS VRP solvers as a part of our component. We cite the creator as [13] (LKH-33
and 49 4 (HGS) in our paper. We compare with existing learning and heuristic
bascline using their code. We cite the creators in our paper, and provide exerpeiment setup (including github links to the repos) in the supplementary material.
(b) Did you mention the license of the assets? [N/A] All the assets (code and data) use are open source.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A] We generate synthetic data for most of our experiments. The only real dataset in Section 6.4 is open source.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "m8p1ALihJPV", "reviewer": "Reviewer_oqMs", "summary": "This paper proposes an iterative framework to solve large-scale Vehicle Routing Problems. At each iteration, given the current feasible solution, a learned component selects subroutes that form a VRP subproblem. Then the subproblem is solved using a standard VRP solver (LKH-3) and the subsolution is used to update the current solution. The subproblem selector uses a Transformer encoder and predicts the subsolution cost; it is trained in a supervised way. Experimental results show that the method is able to reach the performance of the VRP solver LKH with significantly shorter computation times.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n---------------\n\nThe idea of this work is to decompose a large-scale VRP into a series of smaller subproblems that can be solved efficiently. This is a standard approach in Mixed Integer Linear Programming in general and for VRPs in particular (e.g. references [30] and [31] cited in the paper). The originality comes from learning the heuristic that is responsible for the subproblem definition. \n\nThe learning component itself is based on a standard Transformer encoder architecture. Using spatial information to guide the subproblems definition is also standard in decomposition techniques for the VRP (see e.g. [a, b]).\n\nI believe the general strategy and the components are not novel. However their combination here gives good experimental results. \n\n[a] É. Taillard, 1993, Parallel iterative search methods for vehicle routing problems.  \n[b] Santini et al, 2021, Decomposition strategies for vehicle routing heuristics.   \n\n\nQuality\n----------\nThe paper is of good quality. I have a couple of concerns regarding the experimental validation:\n\nIn general to give a more precise sense of the improvements, I think it’s important to look at and report the optimality gaps (average and standard deviation) w.r.t the best found solution i.e. (Method cost - Best sol cost)/best sol cost. It would also be useful to indicate the size of the test set in the main text. \n\nSince this paper proposes a decomposition framework for VRPS, I think it would be relevant to compare to other decomposition heuristics such as the cited POPMUSIC framework (or e.g. [c], the heuristics cited in [b]) that specifically target large-scale problems. \nWhile LKH-3 is known to be an efficient heuristic to solve a variety of TSP and VRP problems, I am not sure it is the state-of-the-art solver for large scale VRPs. Do the authors have a reference that claims that?\n\nAlso the authors observe that the random problem-selector baseline achieves a similar performance within the same computation time in the uniform distribution case and with more time in the clustered mixed datasets. Do the authors have an explanation/interpretation of this observation?\n\nIn Table 1, the AM greedy gives a lower cost than the AM sampling. This is surprising as it contradicts the results reported in the original paper (admittedly for smaller problems). Do the authors have an idea of why it’s the case? What was the sample size? Since the computation time is significantly shorter than all other methods, have the authors tried increasing the sample size?\n\nFinally, I wonder how the size of the subproblems is controlled. If the demands are very small w.r.t the vehicle capacity, the initial solution may contain only say 2 routes. Then there is only one subproblem that is the entire problem. Can this happen?\n\n[c] Vidal, 2020, Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood.  \n\n\nClarity\n---------\n\nThe paper is clear and well-written.  \nA suggestion: I did not get much from figures 6 and 7 whereas I would have liked to see more details in the main paper about how the proposed method was adapted to other variants of the VRP (Section 6.5).\n\nSome typos/details:  \nL49-52: this is more of a description of a heuristic solution of the VRP rather than the problem itself. The vehicle capacity may return to he depot before  exhausting its capacity if it leads to a better cost.   \nL61: Subproblem: the depot node… —> Subproblem: CVRP in the depot node….  \nL14: *The* vehicle routing problem  \nL54: *the* depot 0. \nL242: begets —> gets.  \n\n\nSignificance\n-----------------\n\nThe paper focuses on solving large-scale vehicle routing problems, using a decomposition strategy. I feel like the contribution is quite specific to VRPs. For example it's not clear how this can be adapted to the Traveling Salesman Problem (even though it is a closely related problem). \n\nThe usefulness to VRP practitioners depends on how the results of this method compare to strong decomposition heuristics for large-scale VRPs (see above Quality section).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "OtFzjMbft4U", "reviewer": "Reviewer_mEu5", "summary": "The paper proposes new ways to learn good decomposition steps in a heuristic search algorithm for the capacitated vehicle routing problem. The learning algorithm can select good seed points for the decomposition, often permitting significant speed-ups (1.5x) over other baseline decomposition algorithms (random and other simple variations). Additional experiments are conducted to evaluate the impact of the client distribution on the performance of the proposed approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and generally easy to follow. The application is interesting and the experimental results will be noteworthy for both the machine learning (ML) and operations research (OR) communities.\n\nI suggest being careful of some affirmations and statements, which can be quite misleading. The authors have a tendency to \"oversell\" the contribution. The CVRP literature already contains many decomposition algorithms based on geographic partitions (see, e.g., [1] for a review). Therefore it is incorrect to mention the decomposition or \"the use of spatial locality\" as a novelty in the contribution statement. Instead, the contribution should be focused on the learning part, the algorithm designed for it, and the numerical experiments. Similarly, the sentence \"We hypothesize that in such situations, the larger problem can be efficiently approximately solved as a sequence of smaller subproblems, which can be delegated to efficient sub-solvers.\" is misleading: this is a well-known fact, not an author's hypothesis.\n\nThe main contribution of the paper is the design of a learning algorithm that can select seed points during decomposition steps. However, this component is only very succinctly discussed. The authors employ a very heavy hammer (a transformer network with a dense multi-head attention mechanism) but do not provide experiments supporting the choice of this architecture. I am missing an ablation study and sensitivity analysis to deconstruct the design of this method, and a comparison with simpler regression models for this learning task.\n\nThe choice of the algorithm for the subproblems and for the experimental comparisons is not properly justified. The LKH-3 solver has never been (or even pretended to be) a state-of-the-art (SOTA) algorithm for the CVRP. The use of this method as well as OR-Tools in earlier papers on the CVRP in the ML domain (around 2017) was possibly a question of ease of integration and some herd effect (subsequent papers reproducing choices made in earlier works). Papers published at NeurIPS should follow rigorous experimental standards, and this includes i) accurately representing the application domain (the CVRP has been the subject of numerous studies in the OR domain over the last 60 years) and ii) drawing experimental comparisons with algorithms that are truly SOTA. As discussed in [1] and in a long stream of subsequent comparisons, ILS [2], HGS [3,4] and SISR [5] stand out as the current state-of-the-art for CVRP in terms of solution quality. Most notably, these methods can solve instances with around 100 customers to near-optimality within seconds. Therefore, we would expect to see experimental analyses or comparisons being built on these algorithms, especially given that source code is available for some of them.\n\nIn connection with my previous comment, the authors have used [6,7] as a principled way to generate training and test data, but they did neither report experimental results on the original instances, nor comparisons with SOTA algorithms on them. This seems necessary in such a study about new heuristic results for the CVRP. The CVRPLib website (http://vrp.atd-lab.inf.puc-rio.br/index.php/en/) gathers a lot of information on these instances, and it also includes regular updates of the best-known solutions. If the authors have found new best results during these studies, they could likewise report them.\n\nThe learning algorithm is focused on the choice of the seed points, but the number of routes $k$ is kept constant through each step of the decomposition. Yet, the number of clients per route heavily depends on the instance and application (e.g., long-haul transportation may involve only a few deliveries in each route, whereas parcel-delivery applications may involve up to 100-150 deliveries per route). Consequently, using a fixed number of routes in the decomposition may give sometimes small subproblems that are too trivial, or large subproblems that are solved inefficiently in other cases. In view of this, the parameter $k$ (or any parameter that determines the size of the subproblem, e.g., a maximum number of customers) appears to be an even more important choice than the seed point used for each decomposition. Given this critical importance, why not learning this parameter instead of expecting the user to do an extensive hyperparameter calibration to select it? This would also permit better transfer between different application contexts.\n\nMinor comment: \"exorbitant amount of a time\" => Quite excessive (and dependent on the termination criterion)\n\nOverall, this paper covers important research questions and reports very interesting experiments, but the issues related to baseline comparisons are a clear weak point that leads me to recommend a weak rejection at this stage. As suggested in this report, a more thorough experimental analysis and a better positioning in relation to the current SOTA algorithms could lead me to revise my evaluation.\n\n[1] Laporte, G., et al.  (2014). Heuristics for the vehicle routing problem. In P. Toth & D. Vigo (Eds.), Vehicle Routing: Problems, Methods, and Applications (pp. 87-116). Society for Industrial and Applied Mathematics.\n\n[2] Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519-2531.\n\n|3] Vidal, T., et al. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624. \n\n[4] Vidal, T. (2020). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. arXiv:2012.10384 \n\n[5] Christiaens, J., & Vanden Berghe, G. (2020). Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2), 299-564.\n\n[6] Uchoa, E., et al. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845-858.\n\n[7] Arnold, F., Gendreau, M., & Sörensen, K. (2019). Efficiently solving very large scale routing problems. Computers & Operations Research, 107(1), 32-42.\n\n=================================\n           After author's responses\n=================================\n\nThe authors have carefully considered my comments and conducted extensive numerical analyses, providing (i) new ablation experiments and (ii) tests with a SOTA algorithm for the CVRP. The results provide useful information and permit to fill the gaps and weaknesses mentioned in my previous review. Considering these changes, I am pleased to revise my score and recommend accepting the revised paper at NeurIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9ogre5KVwf8", "reviewer": "Reviewer_7sjD", "summary": "The paper proposes a decomposition method for large-scale vehicle routing problems (VRPs) that leverage supervised learning. Specifically, the proposed methodology uses regression to identify a smaller, more tractable subproblem from a given initial solution, which is then addressed by another solver and incorporated into a full solution. Numerical results compare different state-of-the-art heuristics (e.g., LKH-3) and exact approaches (e.g., OR Tool) on different variations of the VRP with up to 3,000 nodes.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nI did find the specific setup novel and interesting. There are, however, several related routing methods that incorporate learning when decide which cities to group together to solve them separately, which is a classical idea for large-scale VRPs. For example,\n\nPoullet, Julie. Leveraging machine learning to solve The vehicle Routing Problem with Time Windows. Diss. Massachusetts Institute of Technology, 2020.\n\nand references therein. Perhaps the key difference is that existing methods formulate the problem as either as a more traditional classification task or as a unsupervised learning problem, while in this paper the authors use a regression/classification to learn how to \"break\" an existing solution, which I found quite interesting. My suggestion is for authors to better relate with that associated VRP literature, as there are strong parallels between approaches.\n\n**Quality**\n\nThe numerical study is very thorough to the best of my analysis. All the parameters are explained and detailed clearly. I believe some details could be moved from the Appendix to the main text, or at least expanded, in particular those concerning the  training details and some comments concerning the ablation study.\n\nMy main questions are:\n\n(a) What is the impact of the initial solution to the overall approach? It seems that the initial routes could greatly modify the possible subproblems one uses both for training as well as for the actual runs. Furthermore, are the final gaps/times obtained robust with respect to the quality of the initial solution provided?\n\n(b) The number of subproblems is quite small. What are the gains if we relax or restrict the distance thresholds? That is, how one could determine the numbers to use? Any insights here would be extremely helpful, such as a sensitivity analysis on the solution time/quality impact. Moreover, is there a way to avoid enumerating all subproblems, possibly as a future work?\n\n**Clarity**\n\nThe paper is very well written and easy to follow. The source code is also provided and the supplemental material is excellent. \n\n**Significance**\n\nIn my view, the paper presents simple but effective ideas for large-scale VRPs that improve upon the state of the art heuristics under certain settings. The numerical study is thorough and insightful. I believe the technique can be of interest to a larger audience beyond routing as it is applicable to other large-scale combinatorial problems that are amenable to constructive approaches, such as the maximum stable set. I have some small concerns about the impact of the initial solution and the requirement to enumerate subproblems, but I believe they are easy to be clarified.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No specific concerns. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9R4OW9xJKMd", "reviewer": "Reviewer_t1Zw", "summary": "The paper introduces a local search technique for vehicle routing problems (VRP) that decomposes the general problem and delegates smaller subproblems to a subsolver, e.g. an exact VRP solver.\nHow to decompose the problem is learned from a generated training set using a transformer model and is the main contribution of the paper.\nExperiments results with a comparison to recent works in the area show the effectiveness of the proposed method.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is noticed that a VRP can be decomposed into smaller subproblems that are aware of spatial locality, i.e. that a locally optimal (or at least good) subroute in an area of the overall problem is commonly part of the overall optimal (or near-optimal) route.\nHow to pick a good region to make improvements and find locally good routes is the main question of this research and the proposed solution is to learn a model that identifies the subproblems.\n\nDecomposition is an important aspect for solving large combinatorial problems (such as VRP) and it is a common technique, e.g., in operations research for problem modeling. Identifying appropriate subproblems takes away a huge burden and is therefore a timely contribution in the area.\nMy concern is related to the generality of the method, since selecting locally connected areas in the VRP problem space is relatively easy compared to other combinatorial problems.\n\nFor the experiments presented in VRP, the same criticisms are for most (if not all) neural combinatorial optimization problems apply: The shift in training + testing effort vs. the exact solvers that only have testing effort (and there take longer), but can provide guarantees. I don't think that this problem has to be solved in this paper, but it will be a constant struggle for the time being.\n\nMy conclusion is that the presented method, when only limited to VRP, is good and interesting, but I'm missing the connection to the larger area of combinatorial optimization and solving NP-hard problems.\n\nQuestions:\n- OR-Tools is selected as a baseline. It is written \"We set 15 min as the time-out [..], which converges in all settings.\". What is meant by converging? It is clear that OR-Tools (an exact solver) does not find the optimal solution in that time and is limited by the timeout, as shown in the table. Does converge only mean that it finds _any_ solution?\n- Given my earlier criticism on generalization, what is your expectation how well other subsolvers would work in this or other problems?\n\nUpdate: I read the author responses and raise my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact are adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes and analyzes a learning augmented local search algorithm to solve large-scale VRPs. Overall, all reviewers found novelty and merit in the work that was presented, but a number of questions and potential concerns of the work were posed. In their rebuttal, the author(s) were very thorough and convincing in answering these questions/concerns, and in many cases additional experiments were performed to provide additional insights in response to specific reviewer questions.

As a result of these interactions, the unanimous decision of the reviewers was to accept the paper (with multiple reviewers raising their final scores), continent on the the author(s) commitment to revise the paper to incorporate the following: (1) the revised statement of contributions they provided in the rebuttal, (2) an expanded discussion of other related learning-based approaches to this problem, (3) the additional comparative results produced relative to HGS, which was suggested as a better SOTA approach to compare against than LKH-3 and (4)  the results of new ablation experiments that were performed in response to specific reviewer queries that further enhance the paper's conclusions. In response to a direct question regarding how the authors would accomplish all revisions during the rebuttal phase, the author(s) explicitly agreed to this set of changes, and we are taking them at their word.
Decision: Accept (Spotlight)