Deep Policy Dynamic Programming for Vehicle Routing Problems
Authors: Wouter Kool
Herke van Hoof
Joaquim Gromicho
Max Welling
Venue: NeurIPS 2021 Submitted (2021)
Keywords: vehicle routing
travelling salesman problem
dynamic programming
neural
network
policy
time windows
constraints

Abstract: Routing problems are a class of combinatorial problems with many practical applications. Recently, end-to-end deep learning methods have been proposed to learn approximate solution heuristics for such problems. In contrast, classical dynamic programming (DP) algorithms guarantee optimal solutions, but scale badly with the problem size. We propose \emph{Deep Policy Dynamic Programming} (DPDP), which aims to combine the strengths of learned neural heuristics with those of DP algorithms.
DPDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP), the vehicle routing problem (VRP) and TSP with time windows (TSPTW) and show that the neural policy improves the performance of (restricted) DP algorithms, making them competitive to strong alternatives such as LKH, while also outperforming most other 'neural approaches' for solving TSPs, VRPs and TSPTWs with 100 nodes.

Deep Policy Dynamic Programming for Vehicle Routing Problems
Anonymous Author(s)
Affiliation Address email
Abstract
Routing problems are a class of combinatorial problems with many practical applications. Recently, end-to-end deep learning methods have been proposed to learn approximate solution heuristics for such problems. In contrast, classical dynamic programming (DP) algorithms guarantee optimal solutions, but scale badly with the problem size. We propose Deep Policy Dynamic CactmnicPrroggee Programmning (DPDP), which aims combine the strengths of learned neural heuristics with those of DP algorithms. DPDP prioritizes and restricts the DP state space using policy derived from deep neural network, which trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP), the vehicle routing problem (VRP) and TSP with time windows (TSPTW) and show that the neural policy improves the performance of (restricted) DP algorithms, making them competitive to strong alternatives such as LKH, while also outperforming most other 'neural approaches' for solving TSPs, VRPs and TSPTWs with 100 nodes.
10
11
12
14
Introduction
16
Dynamic programming (DP) is a powerful framework for solving optimization problems by solving smaller subproblems through the principle of optimality B Famous examples are Dijkstra's algorithm [14] for the shortest route between two locations, and the classic Kerd algorithm for the travelling salesman problem (TSP) [23] []. Despite their long history, dynamic programming algorithms for vehicle routing problems (VRPs) have seen limited use practice, primarily due to their bad scaling performance. More recently, line of research has attempted the use of machine learning (especially deep learning) to automatically learn heuristics for solving routing problems (yet) competitive to 'traditional" algorithms such as LKH 24 and lack (asymptotic) guarantees on their performance.
18
20
21
22
57
41 29 7 While the results promising, most learned heuristics
24
In this paper, we propose Deep Policy Dynamic Programming (DPDP) framework for solving vehicle routing problems. The key of DPDP is to combine the strengths deep learning and DP, by restricting the DP state space (the search space) using policy derived from neural network.
26
28 In Figure [ it can seen how the neural network indicates promising parts of the search space (through heatmap over the edges of the graph), which is then used by the DP algorithm to find
30 good solution. DPDP is more powerful than some related ideas 662 52 61
6 34] as it combines
supervised training of large neural network with just single model evaluation at test time, enable 32 running a large scale guided search using DP. The DP framework is flexible as it can model a variety of realistic routing problems with difficult practical constraints [20]. We illustrate this by testing DPDP on the TSP, the capacitated VRP and the TSP with (hard) time window constraints (TSPTW).
34
In more detail, the starting point of our proposed approach is restricted dynamic programming algorithm 20) Such an algorithm heuristically reduces the search space by retaining only the most
36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

(a) Travelling Salesman Problem
(b) Vehicle Routing Problem
(c) TSP with Time Windows
Figure Heatmap predictions (red) and solutions (colored) by DPDP (VRP depot edges omitted).
promising solutions per iteration. The selection process is very important as it defines the part of the
38 DP state space considered and, thus, the quality of the solution found (see Fig.2). Instead of manually
39 defining selection criterion, DPDP defines it using a (sparse) heatmap promising route segments obtained by pre-processing the problem instance using a (deep) graph neural network (GNN) [26]
40
41
This approach reminiscent of neural branching policies for branch-and-boum algorithms 19] 40
42 In this work, we thus aim for 'neural boost' of DP algorithms, by using a graph neural network for scoring partial solutions. Prior work 'neural' vehicle routing has focused auto auto-regressive
44 models [57 5 13 29], but they have high computational cost when combined with (any form of) search, the model needs be evaluated for each partial solution considered. Instead,
(for TSP) and adapt (for VRP and TSPTW) a model to predict a heatmap indicating promising edges (26). and define the score of partial solution the 'heat' of the edges contains (plus an estimate the "heat-to-oo" or potential of the solution). As the neural network only needs to be evaluated once for each instance, this enables much larger search (defined by B), making good trade-off between quality and computational cost. Additionally, we can apply a threshold to the heatmap to define sparse graph on which to run the DP algorithm, reducing the runtime by eliminating many solutions.
46
47
48
49
50
51
52
Figure illustrates the overall DPDP algorithm. Section we show that DPDP significantly show that
'classic" restricted DP algorithms (with the same B). Additionally, DPDP outperformes most other "neural' approaches for TSP, VRP and TSPTW and is competitive with the highly-optimized LKH solver 24 for VRP, while achieving similar results much faster for
improves
54
56 TSP and TSPTW. For TSPTW, DPDP also outperforms the best open-source solver we could find
57
illustrating the power of DPDP handle difficult hard constraints (time windows).
Sruph
DP O(2%)
DPDP O(Bm)
Instance
Neursl Netwnek
Heatmap
Dominated solution
Dominate
Figure Deep Policy Dynamic Programming for the TSP. GNN creates a (sparse) heatmap indicating promising edges, after which tour is constructed using forward dynamic programming. each step, at most solutions are expanded according to the heatmap policy, restricting the size of the search space. Partial solutions are dominated by shorter (lower cost) solutions with the same DP state: the same nodes visited (marked grey) and current node (indicated by dashed rectangles).

---

58
2
e.g. for the TSP with time windows [15] and precedence constraints [39, but typically limited to small problems only, due to the curse of dimensionality. Restricted DP (with heuristic policies) has been used to address, Related work
59
DP has long history as an exact solution method for routing problems 3T 500,
60
61
62 e.g., the time dependent TSP [37], and has been generalized into a flexible framework for VRPs with different types of practical constraints [20]. DP approaches have also been shown to be useful in settings with difficult practical issues such as time-dependent travel times and driving regulations (8 or stochastic demands [4]. For a thorough investigation of modelling choices DP for routing (and scheduling), see [53] For sparse graphs, alternative, but less flexible, formulations can be used [8].
63
64
65
66
67
Despite the flexibility, constructive DP methods have not gained much popularity compared to heuristic search approaches such as Ruin and Recreate [47]. Adaptive Large Neighborhood Search LKH [4 or FILO []. While highly effective, these methods are limited in their flexibility as special operators need to be engineered for different types of problems. While restricted DP was
68
69
46..
70
71
shown to have superior performance on realistic VRPs with many constraints (20. the performance
72
gap of around 10% for standard (benchmark) VRPs (with time windows) is too large to popularize the restricted dynamic programming approach. We argue that the missing ingredient for restricted dynamic programming is the availability of a strong but computationally cheap policy for selecting which solutions should be considered, which is the motivation behind DPDP.
75
75
78
In the machine learning community, recent ad have significantly improved deep neural networks (DNNs) to perform tasks such as image classification and machine translation [32]. After the first deep learning model was trained (using example solutions) to construct TSP tours [57], many
77
78
79
improvements have been proposed, e.g. different training strategies such as reinforcement learning and model architectures, which enabled the same idea to be used for other 60). Most constructive neural methods are auto-regressive, evaluating the model many times to predict one node at the time, but other works have considered predicting a 'heatmap' of promising edges al once [43 26 17 which allows tour to constructed (using sampling or beam search) without further evaluating the model. An alternative direction is 'learning to search', , where a neural network is used to guide a search procedure such as local search 18 (59 25). Some works have attempted scaling to larger instances beyond 100 nodes, which remains challenging 36 17]. The combination of machine learning with DP has been proposed in
80
(RL) 5 27
12
30
81
routing problems
29
13 45
16
85
84
85
7 35
87
88
limited settings 62 52 11 Most related to our approach, DP algorithm for TSPTW, guided by an
89
RL agent, was implemented using an existing solver 6 and a neural network predicting edges has been combined with tree search [34] and local search for maximum independent set (MIS). For wider view on machine learning for routing problems and combinatorial optimization, see 38 [4]
90
91
3
Deep Policy Dynamic Programming
92
93 DPDP uses an existing graph neural network 26 (which we modify for VRP and TSPTW) to predict a heatmap of promising edges, which is used to derive the policy for scoring partial solutions in the DP algorithm. The DP algorithm starts with a beam of a single initial (empty) solution. It then proceeds by iterating the following steps: (1) all solutions on the beam are expanded, (2) dominated solutions are removed for each DP state, (3) the best solutions according to the scoring policy define the beam for the next iteration. 'heee steps are illustrated in Fig. 2 The objective function is used to select the best solution from the final beam. The resulting algorithm is a beam search over the DP state space (which is not 'standard beam search' over the solution space!) and we call B the beam size. DPDP is asymptotically optimal as using B = n 2n for a TSP with n nodes guarantees optimal results, but choosing smaller B allows to trade performance for computational cost.
94
95
96
97
38
99
101
102
103
DPDP is generic framework that can be applied to different problems, by defining the following ingredients: (1) the state variables to track while constructing solutions, (2) the initial solution,
104
105
(3) feasible actions to expand solutions, (4) rules to define dominated solutions and (5) a scoring
106
policy for selecting the B solutions to keep. A solution is always (uniquely) defined as a sequence of actions, which allows the DP algorithm to construct the final solution by backtracking. In the next
107
sections, we define these ingredients for the TSP, VRP and TSPTW.
3

---

109
3.1 Travelling Salesman Problem
110
We implement DPDP for Euclidean TSPs with n nodes on a (sparse) graph, where the cost for edge (i is given by Cij. the Euclidean distance between the coordinates of nodes and j.
112
For each partial solution, defined by a sequence of actions a, the state variables are cost(a)), the total cost (distance), current((a), the current node, and visited(a). the set of visited nodes (including the start node). Without loss of generality, we let 0 be the start node, so we initialize the beam at step t ==0 O with the empty initial solution with cost (a) = 0, current(a) = O and visited(a) = {0}. At step i. the action a E {0, ...,, n - 1} indicates the next node visit, and a feasible action for a partial solution a = (ao,... ..... a111 ) if (a.-1, at) is an edge in the graph and de & (as) or, when all are visited, if a = 0 to return to the start node. When expanding the solution to a' (au..... Qz).
113
114
115
116
117
118
119
we can compute the state variables incrementally as:
cost(a') = cost(a) + Ccurrent(a) current(a') = at, visited(a') = vis U (ar). (I)
120 A (partial) solution a is a dominated solution if there exists (dominating) solution a" such that vas" ) visited(a), (), current (a") current (a) and cost(a*) < cast(a). The tuple (visited a), current(a)) we refer to as the DP state, so removing all dominated partial solutions, we keep exactly one minimum-cos solution for each unique DP statd" Since a solution can only dominate other solutions with the same set of visited nodes, we only need to remove dominated solutions from sets of solutions with the same number of actions. Therefore, we can efficiently execute the DP algorithm in iterations, where at step f all solutions have (after t actions) t +++ 1 visited nodes (including the start node), keeping the memory need at (B) states (with the beam size).
121
122
123
124
125
126
127
128
We define the scoring policy using pretrained model [26]. which takes as input node coordinates and edge distances to predict raw 'heatmap' value h. E (0, 1) for each edge (i,j), The model was trained to predict optimal solutions, so hig can be seen as the probability that edge (i, is in the optimal tour. We force the heatmap to be symmetric thus we define húj = max (hej. h.g The policy is defined using the heatmap values, in such way to select the (partial) solutions with the largest total heat, while also taking into account the (heat) potential for the unvisited nodes. The policy thus selects the B solutions which have the highest score, defined as score(a)
129
130
131
132
135
heat(a) + potential(a). with ha) E ha.- i.c. the sum of the heat of the edges, which can be computed incrementally when expanding a solution. The potential is added as an estimate of the "heat-to- go' (similar to the heuristic in A' search) for the remaining nodes, and avoids the 'greedy pitfall' of selecting the best edges while skipping over nearby nodes, which would prevent good edges from being used later. It defined as potential(a) = potential (a) + Eigvistted(a)) potential, (a)
135
136
137
138
139
140
with potential, (a) w; Σj LjEvisite((a) Σn her where w; is the node potential weight given by
hys
141
wi = (max, l4;a) (1 0.1( Czn 0.5)). By normalizing the heatmap values for incoming max, Cgo edges, the (remaining) potential for node is initially equal to wi but decreases as good edges become infeasible due to neighbours being visited. The node potential weight w; is equal to the maximum incoming edge heatmap value (an upper bound to the heat contributed by node i), which gets multiplied by factor 0.95 1.05 to give a higher weight nodes closer to the start node, which we found helps to encourage the algorithm to keep edges that enable to return to the start node. The overall heat- + potential function identifies promising partial solutions and is computationally cheap.
142
143
144
145
146
147
148
3.2
Vehicle Routing Problem
149
For the VRP, we add special depot node to the graph, indicated by DEP. Each node i has a demand d, and the goal is to find multiple routes, which have a limited capacity denoted by CAPACITY.
150
151
Additionally to the TSP state variables (as) current (a) and visited(a), we keep track of capacity(a), which is the remaining capacity in the current route/vehicle. A solution starts at the depot, so we initialize the beam at step t = 0 with the empty initial solution with cost(a a) = 0, current(a) (a) DEP, visited(()
152
153
154
0 and capacity(a) = CAPACITY. For the VRP, we do not consider visiting the depot as separate action. Instead, we define 2n actions, where a, E {0, .... 2n - 1}. The actions O...., n indicate a direct move from the current node to node ae, whereas the actions
155
156
If we have multiple partial solutions with the same state and cost, we can arbitrarily choose one to dominate the other(s), for example the one with the lowest index of the current node.

---

157
7. .... 2n 1 indicate a move to node a, n via the depot. Feasible actions are those that move to unvisited nodes via edges in the graph and obey the following constraints. For the first action
158
159
4g there is no choice and we constrain (for convenience of implementation) do E {n,.... 2n - 1). direct move (a, < n) is only feasible if da, S capacity(a) and updates the state similar to TSP but reduces remaining capacity by da.- A move via the depot is always feasible (respecting the graph edges and assuming d; S CAPACITY Vi) as it resets the vehicle CAPACITY before subtracting demand, but incurs the "via-depot cost' 2EF = Ci,DEr + CDEP.j- When all nodes are visited, we allow special action to return to the depot. This somewhat unusual way of representing a CVRP solution has desirable properties similar to the TSP formulation: at step t have exactly t nodes visited, and we can run the DP in iterations, removing dominated solutions at each step t.
160
161
162
164
165
186
187
For VRP, a partial solution a is dominated solution dominated by a' if visited(a") = visited(a) and current a*) = current(a) (a) (i.e. a" corresponds to the same DP state) and cost S. cost and capacity (a") ) 2 capacity(a)) (a), with at least one of the two inequalities being strict. This means that for each DP state, given by the set of visited nodes and the current node, we do not only keep the (single) solution with lowest cost (as in the TSP algorithm), but keep the complete set of pareto- efficient solutions in terms of cost and remaining vehicle capacity. This is because a higher cost partial solution may still be preferred if it has more remaining vehicle capacity, and vice versa.
168
169
170
172
174
For the VRP scoring policy, we modify the model 26 to include the depot node and demands. The special depot node gets a separate learned initial embedding parameter, and we add additional edge types for connections to the depot, to mark the depot as being special. Additionally, each node gets an extra input (next to its coordinates) corresponding to d d1/CAPACITY (where we set dDEP = 0). Apart from this, the model remains exactly the same The model trained on example solutions from LKH (24] (see Section 4.2), which are not optimal, but still provide useful training signal. Compared to TSP, the definition of the heat is slightly changed to accommodate for the 'via-depot actions' and is best defined incrementally using the 'via-depot heat' 1: = hi,DEr hOBP.s 0.1, where multiplication is used to keep heat values interpretable as probabilities and in the range (0. 1). The additional penalty factor of 0.1 for visiting the depot encourages the algorithm to minimize the number of vehicles/routes. The initial heat is 0 and when expanding a solution a to a' using action ag, the heat is incremented with either heurrent(a))aa (if a, < n) or DEP (a)reut(a)),a- (if ag 2 12). The
175
178
177
178
179
180
182
183
185
186
potential is defined similarly to TSP, replacing the start node 0 by DEP.
187
3.3
Travelling Salesman Problem with Time Windows
188
For the TSPTW, we also have a special depot start node 0, and each node i has time window defined by (4,, us) in which the node should be visited, assuming travel time is equal to cost/distance. It is allowed to wait if arrival at a node is before 4, but arrival cannot be after u; (i.e. the constraint is hard). We consider the objective to be minimizing total cost, but minimizing total time (or makespan) only requires training on different example solutions. Due to the hard constraints, TSPTW is typically considered more challenging to solve than plain TSP, for which every solution is feasible.
189
190
191
192
193
194
The state variables and initial solution are equal to TSP except that we add time(a) which is initially 0 (= lo). Feasible actions a₂ E {O.,... n - 1} are those that move to unvisited nodes via edges in the graph such that the arrival time is no later than Ue and do not directly climinate the possibility to visit other nodes in time Expanding solution a to a' using action at updates the time as time (a)) max (iim((a) + Ceurrent(a),a. l.,).
195
198
197
198
199
For each DP state, we keep all efficient solutions in terms of cost and time, so a partial solution a is a dominated solution dominated by a" if a" has the same DP state (visited(a")
200
visited(a) and current(a" = current(a) (a)) and is strictly better in terms of cost and time, i.e. cost(a") S cos and time( a < Lime(a), with at least one of the two inequalities being strict.
201
202
The model 266 for the scoring policy is adapted to include the time windows (l,, u.) node features (in the same unit as coordinates and costs), and we use a special embedding for the depot similar to
204
205
VRP. Due to the time dimension, TSPTW solution is directed, and edge (i, j) may be good whereas
206
(j. i) may be not, so we adapt the model to enable predictions hij o hyj (see details in Appendix
207
We generated example training solutions using (heuristic) DP with a large beam size, which was faster than using LKH. Given the heat predictions, the score (heat + potential) is exactly as for TSP.
208
2 Except that we do not use the K-nearest neighbour feature 26 as it contains no additional information.
E.g.. arriving at a node at t 10 (including waiting) is not feasible if node has u, 12 and ci 3.
5

---

209
3,4
Graph sparsity
210
As described, the DP algorithm can take into account a sparse graph to define feasible expansions. As our problems are defined on sets of nodes rather than graphs. the use of sparse graph is artificial design choice, which allows to significantly reduce the runtime but may sacrifice the possibility to find good optimal tours. We propose two different strategies for defining the sparse graph on which to run the DP: thresholding the heatmap values hi and using the K-nearest neighbour (KNN)
211
212
213
214
graph. By default, we use a (low) heatmap threshold of 10-5, which rules out most of the edges as the model confidently predicts (close to) for most edges. This is secondary way leverage the neural network (independent
215
217
the scoring policy), which can be seen as form learned problem reduction 49. For symmetric problems (TSP and VRP), we add KNN edges in both directions. For
218
219
the VRP, we additionally connect each node to the depot (and vice versa) to ensure feasibility.
220
3.5
Implementation & hyperparameters
221
We implement DPDP using Py PyTocch 44 to leverage batched computation on the GPU, For details, Appendix A Our code is publicly available DPDP has very few hyperparameters, but the heatmap threshold of 10 and details like the functional form of e.g. the scoring policy are 'educated guesses' manually tuned few validation instances and can likely be improved. The runtime is influenced by implementation choices which were manually selected using few validation instances.
223
225
Experiments
226
4.1
Travelling Salesman Problem
In Table I we report our main results for DPDP with beam sizes of 10K (10 thousand) and 100K, for the TSP with 100 nodes on a commonly used test set [29]. We report results using Concorde (2), LKH (4 and Gurobi [22]. as well as recent results of the strongest methods using neural networks (nuurall approaches') from literature. Running times for solving 10000 instances after training should different machines, typically with 1 GPU or many-core CPU (8- 32). The costs indicated with * are not directly comparable due to slight dataset differences Times for generating heatmaps (if applicable) is reported separately (as the first term) from the running time for MCTS [17] or DP. DPDP achieves close to optimal results, strictly outperforming the neural baselines achieving better results in less time (except POMO [30), see Section 4.2
229
231
be taken as rough indications as some
233
235
https://gitthu..com/rrr be disclosed after review
Table 1: Mean cost, gap and total time to solve 10000 TSP/VRP instances after training.
PROBLEM
TSP100
VRP100
METHOD
CoST
GAP
TIME
COST
GAP
TIME
CONCORDE 2
7.765
0.000 %
6M
HYBRID GENETIC SEARCH
65
15.563
0.000
GEL IM
GUROBI 22
7.776
0.151 %
31M
LKII
7.765
0.000
42M
15.647
0.536
12H57M
GNN HEATMAP BEAM SEARCH
26
7.87
1.39 %
40M
LEARNING 2-OPT HEURISTICS
9
7.83
0.87
41M
MERGED GNN HESTMAP MCTS
17
7.764*
0.04 %
4M
ATTENTION MODEL SAMPLING
29
7.94
2.26 %
1H
16.23
4.28 12
2H
STEP ATTENTION MODEL.
660
8.01
3,20
295
16.49
5.96 %
39%
LEARNING IMPROV, HEURISTICS
559
7.87
1.42
2H1
16.03
3.00 %
SH
MODEL- POMO
7.77
0.14
15.76
NEOREWRITER t7]
16.10
3.45 %
1H
DYNAMIC ATTN. MODEL 2-0PT
4b]
16.27
4.54 %
611
NEUR, LRG. NEIGHB. SEARCH
35
15.99
2.74 %
1H
LEARN TO IMPROVE 35
15.57*
4000H
DPDP 10K
7.765
0.009 %
10M 4 16M
15.830
1.713 %
10M 50M
DPDP 100K
7.765
0.004
10M + 2H35M
0.843
10M Sp48M
DPDP IM
15.627
0.409
48H27M

---

Table 2: Mean cost, gap and total time solve 10000 realistic [51
VRPI00 instances after training.
METHOD
COST
GAP
TIME (1 GPU DR 16 CGCS)
TIME (4 GPUS ou 32 CPUs)
HGS 56
53
18050
0.000 %
7H53M 25H32M
3H56M 12H46M
LKH 224
18133
0.507 %
DPDP 10K
18414
2.018
10M 50M
2M 1 13M
DPDP 100K
18253
1.127 %
10M + 5H48M
2M + 1H27M
DPDP IM
18168
0.659 %
10M + 48H27M
2M + 12H7M
237
4.2
Vehicle Routing Problem
238
For the VRP, we train the model using million instances of 100 nodes, generated according to the
distribution described by [41 and solved using one run of LKH [24]. We train using batch size of
48 and a learning rate of 10-3 33 (selected as the result of manual trials to best use our GPUs), for (at
240
most) 1500 epochs of 500 training steps (following (26)) from which we select the saved checkpoint with the lowest validation loss. We use the validation and test sets by [29].
242
Table I shows the results compared to a recent implementation of Hybrid Genetic Search (HGS)) [
244 a SOTA heuristic VRP solver [56] (55) HGS is faster and improves around 0.5% over I.KH, which is typically considered the baseline in related work. We present the results for LKH, as well as the
246
strongest neural approaches and DPDP with beam sizes up to million. Some results used 2000 (different) instances (35] and cannot be directly compared DPDP outperforms all other neural baselines, except POMO [30,, which delivers good results very quickly by exploiting symmetries in the problem. However, it cannot (easily) improve further with additional runtime, we consider this contribution orthogonal to DPDP. DPDP is competitive to LKH (see also Section
248
250
More realistic instances We also train the model and run experiments with instances with 100 nodes from a more realistic and challenging data distribution [51]. This distribution, commonly used the routing community, has greater variability, in terms of node clustering and demand distributions. LKH failed to solve two of the test instances, which we found out is because LKH by default uses Σ>= d;
252
253
254
255
a fixed number of routes equal to a lower bound, given by
CAPACITY . which may be infeasible"
256
Therefore we solve these instances by rerunning LKH with unlimited number of allowed routes (which in general gives worse results, see Section 4.4).
257
machine with 4 GPUs, but also report (estimated) runtimes for 1 GPU ( (1080TI), and we compare against 16 or 32 CPUs for HGS and LKH. In Tab can be seen that the difference with LKH is, expected, slightly larger than for the simpler dataset, but still below
DPDP run
259
261
1 % for beam sizes of 100K-1M. We also observed a higher validation loss, so it may be possible to
262
improve results using more training data. Nevertheless, finding solutions within 1 1% of the specialized
263
SOTA HGS algorithm, and even closer to LKH, is impressive for these challenging instances, and we consider the runtime (for solving 10K instances) acceptable, especially when using multiple GPUs.
264
285
4.3
TSP with Time Windows
For the TSP with hard time window constraints, we use the data distribution by [6] and use their set of 100 test instances with 100 nodes. These were generated with small time windows, resulting in small feasible search space, such that even with very small beam sizes, our DP implementation
287
268
289
solves these instances optimally, eliminating the need for policy. Therefore, we also consider a
270
more difficult distribution similar to [T], which has larger time windows which are more difficult
271
as the feasible search space is larger") [15] For details, see Appendix B For both distributions, we generate training data and train the model exactly as we did for the VRP.
272
battps://githan wttp://aaa//t/soo/OO///
Thee running time of 4000 hours (167 days) for 10K instances is estimated from 24min/instance [35 7 For example, three nodes with a demand two cannot he assigned to two routes with capacity of three. Up to limit, as making the time windows infinite size reduces the problem to plain TSP.
7

---

Table 3: Mean cost, gap and total time to solve TSPTW 100 instances after training.
PROBLEM METHOD
SMALL TIME WINDOWS
INST.)
LARGE TIME WINDOWS
10
[10K INST.)
COST
GAP
FAIL
TIME
COST
GAP
FAIL
TIME
GVNS 30X 10
5129.58
0.000 %
75
2432.112
0.000 %
37M158
GVNS IX (0]
5129.58
0.000 %
<Is
2457 974
1.063 %
1M4S
LKH IX 24
5130.32
0.014
1.00
5M48S
2431.404
-0,029 %
341188M
BAB-DQN i
5130.51
0.018
2511
ILDS DQN' 6
5130.45
0.017
25H
DFDP 10K
5129.58
0.000
2431.143
-0.040 %
10M + SM7S
DPDP 100K
5129.58
0.000 %
6s
2430.880
00.051 %
10M 11166
273
Table shows the results for both data distributions, which are reported in terms of the difference to General Variable Neighbourhood Search (GVNS) [T0), the best open-source solver for TSPTW we could find" using 30 runs. For the small time window setting, both GVNS and DPDP find optimal solutions for all 100 instances in just 7 seconds (in total, either on 16 CPUs or a single GPU).
274
275
276
277
LKH fails to solve one instance, but finds close to optimal solutions, but around 50 times slower.
278
BaB-DQN* and ILDS-DQN 66, methods combining an existing solver with an RL trained neural policy, take around 15 minutes per instance (orders of magnitudes slower) to solve most instances to optimality. Due to complex set-up, we were unable to run BaB-DQN* and ILDS- DQN* ourselves for
279
280
281
the setting with larger time windows. In this setting, we find DPDP outperforms both LKH (where
282
DPDP orders of magnitude faster) and GVNS, in both speed and solution quality. This illustrates that DPDP, due to its nature, is especially well suited to handle constrained problems.
4.4
Ablations
Scoring policy To evaluate the value of different components of DPDP's GNN Heat Potential scoring policy, we compare against other variants. GNN Heat is the version without the potential, whereas Cost Heat + Potential and Cost Heat are variants that use a 'heuristic' hig = Ctj instead of the GNN. Cost directly uses the current cost of the solution, and can be seen as 'classic' restricted DP. Finally, BS GNN Heat + Potential uses beam search without dynamic programming. i.e. without removing dominated solutions. To evaluate only the scoring policy, each variant uses 1). Figure 3a shows the value of DPDP's potential function, although even without it results are still sigmificantly better than "classic' heuristic DP variants using cost- scoring policies. Also, is clear that using DP significantly improves over a standard beam search (by removing dominated solutions). Lastly, the figure illustrates how the time for generating
286
287
cua
288
289
290
281
the fully connected graph (knn
292
293
294
295
the heatmap using the neural network, despite its significant value, only makes up small portion of the total runtime.
296
110002 bumsuu 1- ER0C SUSKIng PO
115300 bEaT SID IIK 25ML TRSTGL 1-10 1010
educancy
CUR hestrr
1479
5.2%
1330
07 INE Focers
23.5%
0379
03 0.5 1.
200 35
16
25
3.5 2.5
2.0
(a) Different scoring policies, as (b) Beam sizes 10K, 25K, 50K. well as 'pure" beam search, for beam sizes 1, 10, 100, 1000, 10K, pared against LKH(U) with 1, 2, 5 10 10 and knn = 5, 10, 20, and 10 runs
(c) Sparsities with heatmap thresh- olds 0.9, 0.5, 0.2, 0.1, 10 1.100
100K, 250K, 500K, IM, 2.5M com-
100K.
50, 99. Beam size 100K.
Figure 3: DPDP ablations on 100 validation instances of VRP with 100 nodes.
8

---

297
Beam size DPDP allows to trade off the performance vs. the rumtime using the beam size B (and to some extent the graph sparsity, see Section 4.4). We illustrate this trade-off in Figure [b] where we evaluate DPDP on 100 validation instances for VRP, with different beam sizes from TOK to 2.5M.
296
300
We also report the trade-off eurve for the IKHHUU, which is the strongest baseline that can also solve different problems. We vary the runtime using 1, 2, 5 and 10 runs (returning the best solution). (KHUmniimtte) is the version which allows an unlimited number of routes (see Section 4.2). is hard to compare GPU vs CPU, so we report (estimated) runtimes for different hardware, i.e. 1 or 4 GPUs (with 3 CPUs per GPU) and 16 or 32 CPUs. We report the difference (i.e. the gap) with HGS, analog to how results are reported in Table I We emphasize that in most related work (e.g. (29)). the strongest baseline considered is one run of LKH. so we compare against a much stronger baseline.
302
304
306
Also, our goal is not outperform HGS (which is SOTA and specific to VRP) LKH, but to show DPDP has reasonable performance, while being a flexible framework for other (routing) problems.
308
Graph sparsity We test the two graph sparsification strategies described in Section 3.4 another way to trade off performance and runtime of DPDP. In Figure [e we experiment with different heatmap thresholds from 10-5 to 0.9 and different values for KNN from 5 to 99 (fully connected).
310
312
The heatmap threshold strategy clearly outperforms the KNN strategy as it yields the same results using sparser graphs (and lower runtimes). This illustrates that the heatmap threshold strategy is more informed than the KNN strategy, confirming the value of the neural network predictions.
313
314
Discussion
315
316
In this paper we introduced Deep Policy Dynamic Programming, which combines machine learning and dynamic programming for solving vehicle routing problems. The method yields close to optimal results for TSPs with 100 nodes and competitive to the highly optimized LKK (2 solver for VRPs with 100 nodes. On the TSP with time windows, DPDP also outperforms LKH, being significanlty faster, as well as GVNS [IO), the best open source solver we could find. Given that DPDP was not specifically designed for TSPTW, and still has possibilities for improvement, we consider this an impressive and promising achievement.
317
318
319
320
322
323
The constructive nature of DPDP (combined with search) allows to efficiently address hard constraints such as time windows, which are typically considered challenging in neural combinatorial optimiza- tion [5] [29 and are also difficult for local search heuristics (as they need to maintain feasibility while adapting solution). Given our results on TSP, VRP and TSPTW, and the flexibility of DP as a framework, we think DPDP has great potential for solving many more variants of routing problems, and possibly even other problems that can be formulated using DP (e-g- job shop scheduling (I]).
324
325
326
327
328
329
We hope that our work brings machine learning research for combinatorial optimization closer to the operations research (especially vehicle routing) community, by combining machine learning with DP and evaluating the resulting new framework on different data distributions used by different 10].
330
332
communities
41
Scope, limitations & future work Deep learning for combinatorial optimization is recent re- search direction, which could significantly impact the way practical optimization problems get solved in the future. Currently, however, it is still hard to beat most SOTA problem specific solvers from the
334
336 OR community. Despite our success for TSPTW, DPDP is not yet a practical alternative in general, but do consider our results as highly encouraging for further research. We belief such research could yield significant further improvement by addressing key current limitations: (1) the scalability to larger instances, (2) the dependency on example solutions and (3) the heuristic nature of the scoring function. First, while 100 nodes is not far from the size of common benchmarks (100- - 1000 for VRP 51 and 200 for TSPTW (10), scaling is a challenge, mainly due to the 'fully-connected" Onn²) graph neural network. Future work could reduce this complexity following e.g. 33 The dependency on example solutions from an existing solver also becomes more prominent for larger instances, but could potentially be removed by "bootstrapping" using DP itself as we, in some sense, have done for TSPTW (see Section 3.3p. Future work could iterate this process to train the model 'tabula rasa' (without example solutions), where DP could be seen analogous to MCTS in AlphaZero [48). Lastly, the heat + potential score function is a well- motivated but heuristic function that was manually designed as function of the predicted heatmap. While it worked well for the three problems we considered, may need suitable adaption for other problems. Training this function end-to-end while keeping a low computational footprint, would be an interesting topic for future work.
338
340
342
3/3
344
345
346
347
348
349
11 58

---

References
351
352
[1] Luca Accorsi and Daniele Vigo. fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems. Technical report, Tech. rep.. University of Bologna, 2020.
354
[2] David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006.
355
[3] Richard Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Sciences of the United States of America, 38(8):716, 1952.
356
[4]
Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), (1):61663, 1962.
358
359
[5] Irwan Bello, Hieu Pham, Quoe Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint S..ivv66111099900 2016.
381
[6] Quentin Cappart, Thierry Moisan, Louis-Martin Rousseau, Isabeau Trémont-Schward and Andre Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. arXiv preprint arXiv:2006.01610, 2020.
362
363
364
77] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 6281-6292, 2019.
365
388
367
[8] William Cook and Paul Seymour. Tour merging via branch-decomposstion. INFORMS Journal on Computing, 15(3):233 248, 2003.
[9] Paulo Roberto de O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2- opt heuristics for the traveling salesman problem via deep reinforcement learning. Proceedings of Machine Learning Research, 1:17, 2020.
370
[10] Rodrigo Ferreira Da Silva and Sebastián Urrutia. A general vns heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4):203-211, 2010.
373
374
[1]] Hal Daumé III and Daniel Marcu. Learning as search optimization: Approximate large margin methods for structured prediction. In Proceedings of the 22nd international conference on Machine learning. pages 169 176, 2005.
375
378
122 Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combinatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems, 33, 2020.
378
379
[13] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Martin Rousseau. Learning heuristics for the TSP by policy gradient. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 170-181. Springer, 2018.
381
382
383
[14] Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 384
1(1):269-277 27119-7111111 1959.
386
[15]
Yvan Dumas, Jacques Desrosiers, Eric Gelinas, and Marius M Solomon. An optimal algorithm for the traveling salesman problem with time windows. Operations research, 43(2):367-371, 1995.
387
389
[16] Jonas K Falkner and Lars Schmidt- Thieme. Learning to solve vehicle routing problems with time windows through joint attention. arXiv preprint arXiv:2006.0m 09100, 2020.
390
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. arXiv preprini arXiv:2012.1066 2020.
392
393
[18] Lei Gao, Mingxiang Chen, Qichang Chen, Ganzhong Luo, Nuoyi Zhu, and Zhixin Liu. Learn to design the heuristics for vehicle routing problem. arXiv preprint arXiv:2002.0855 2020.
[19] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems.
396
10

---

398
[20]
Joaquim Gromicho, Jelke J van Hoorn, Adrianus Leendert Kok, and Johannes MJ Schutten. Restricted dynamic programming: flexible framework for solving realistic vips. Computers & operations research, 39(5):902-909 2012.
399
[21] Joaquim AS Gromicho, Jelke J Van Hoorn, Francisco Saldanha-da Gama, and Gerrit T Timmer. Solving the job-shop scheduling problem optimally by dynamic programming. Computers & Operations Research, (9(1))29968 2977, 2012.
402
403
404
[22] Gurobi Optimization, LLC. Gurobi, 2018.
[23]
Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematiiss 10(1):196 210, 1962.
406
407
[24]
Keld Helsgaun. An extension of the Lin Kernighan-Helsse TSP solver for constrained traveling salesman and vehicle routing problems: Technical report. 2017.
408
409
[25] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle
410
routing problem. arXiv preprint ar1iv: 1911911111999..11111 2019.
411
[26]
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.0122 2019.
412
413
[27] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the travelling salesman problem. arXiv preprint arXiv: 1900.07110 2019.
415
[28] AL Kok, Elias W Hans, Johannes MJ Schutten, and Willem HM Zijm. dynamic programming heuristic for vehicle routing with time-dependent travel times and required breaks. Flexible services and manufacturing journal, 22(1-2)883-108 2010.
417
[29] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
419
420
[30] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
422
[31] Gilbert Laporte. The vehicle routing problem: An overview of exact and approximate algorithms.
424
European journal of operational research, 59(3):345-33 1992.
[32]
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436. 2015.
426
427
[33]
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: framework for attention-based permutation-invariant neural networks. In International Conference Machine Learning, pages 3744-3753, PMLR, 2019.
428
430
[34] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances in Neural Information Processing Systems, page 539, 2018
432
433
[35] Hao Lu. Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
434
435
[36] Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint 1rXiv:19/i.04996. 2019.
437
[37] Chryssi Malandraki and Robert B Dial. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 90(1):45-55 1996.
439
441
[38] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey, arXiv preprint arXiv:2003.03600 2020.
11

---

443
[39] Aristide Mingozzi, Lucio Bianco, and Salvatore Ricciardelli. Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Operations research, 45(3):365-377 1997.
444
446
[40] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.
447
448
449
[41] MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pages 9860-98688 9870,997,2200 2018.
450
451
452
[42] Clara Novoa and Robert Storer. An approximate dynamic programming approach for the vehiele routing problem with stochastic demands. European Journal of Operational Research, 196(2):009-515, 2009.
453
454
455
[43] Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note on learning algorithms for quadratic assignment with graph neural networks. arXiv preprint arXiv: urXiv:1706.077 776.074500 2017.
456
[44] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary De Vitoo Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
458
[45] Bo Peng. Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dy- namic attention model for vehicle routing problems. In International Symposium on Intelligence Computation and Applications, pages 636-650. Springer, 2019.
461
462
[46] Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455 472555---222455 2006.
484
465
[47] Gerhard Schrimpf, Johannes Schneider, Hermann Stamm-Willrande Wilbrandt, and Gunter Dueck. Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics, 159-2):13-1171, 2000.
467
468
[48] David Silver, Thomas Hubert, Julian Schritwieserr, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 962(6419):1140-11 2018
469
470
472
[49]
Yuan Sun, Andreas Ernst, Xiaodong Li, and Jake Weiner. Generalization of machine learning for problem reduction: case study on travelling salesman problems. OR Spectrum, pages 1-27, 2020.
473
474
475
[50]
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
478
477
[51] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subrama- nian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845 858, 2017.
478
479
480
[22] Wouter van Heeswijk and Han La Poutré. Approximate dynamic programming with neural networks in linear discrete action spaces. arXiv preprint arXiv:1902.09855 2019.
481
482
[53] Jelke J. van Hoorn. Dynamic Programming for Routing and Scheduling. PhD thesis, 2016.
483
[54] Natalia Vesselinova, Rebecca Steinert, Daniel F Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization graphs: A survey with applications to networking. IEEE Access, 1112388--20441 2020.
485
486
[55] Thibaut Vidal. Hybrid genetic search for the evrp: Open Open-source implementation and swap* neighborhood. arXiv preprint arXiv:2012. 10384, 2020.
[56] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):61 1-624, 2012.
489
12

---

[57] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692-2700, 2015.
492
[58] Sam Wiseman and Alexander M Rush. Sequence-to-seuuence learning as beam-search opti- mization. In Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, pages 1996, 2016.
493
495
496
[59] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang. and Andrew Lim. Learning improvement heuristics for solving routing problems. arXiv preprint arXiv:1912.0578. 2019.
498
[60] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 2020.
499
500
[61] Shenghe Xu, Shivendra S Panwar. Murali Kodialam, and TV Lakshman. Deep neural network approximated dynamic programming for combinatorial optimization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1684-1691, 2020.
501
502
[62]
Feidiao Yang, Tiancheng Jin, Tie- Yan Liu, Xiaoming Sun, and Jialin Zhang. Boosting dynamic programming with neural networks for solving np-hard problems. In Asian Conference on Machine Learning, pages 726-739. PMLR, 2018.
504
13

---

Checklist
506
1. For all authors...
508
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
509
510
(b) Did you describe the limitations of your work? [Yes] Scaling and scoring policy, see discussion
512
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not see any issues
513
514
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
515
516
2. If you are including theoretical results...
517
(a) Did you state the full set of assumptions of all theoretical results? [Yes] For claim that DPDP asymptotically optimal, the DP description defines the set of assumptions and we note the beam size for which this holds.
518
519
(b) Did you include complete proofs of all theoretical results? [No] Optimality and complexity of full DP for TSP is already known [2 4 (we do not claim this is a new result, we just mention it)
521
522
3. If you ran experiments..
524
(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] Code will be available upon release
525
526
527
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We did a fair job to include all the information necessary to reproduce the experiments
528
529
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No] For training the model, we used a standard supervised learning setup and we found training to be stable across different problems and data distributions. Due to high computational costs, we did not do multiple runs, which consider conservative likely results can be improved by further experiments and training with multiple seeds. As for evaluation of the algorithms on random instances, we use a large test set of 10.000 instances. As we use the same instances for our own implemented baselines, the statistical significance in such a 'paired' setting is much higher than would be suggested by error bars. For results directly reported from other papers, the margin is large enough with 10000 instances or we avoid strong claims. With our code, we plan to release all solutions for all test instances for the methods we evaluated ourselves.
531
539
535
536
537
538
539
540
541
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] While not explicitly, the total computational requirement for generating training data, which requires the most compute, can be derived from solving 1M instances and the time reported for solving 10K instances in Table I This is a number of days (around 4) a cluster with 10 32-core machines, per problem.
543
545
547
548
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
550
(b) Did you mention the license of the assets? [No] This can be found in the original
551
repositories
552
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Will be provided with the released code as URI.
553
554
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No] Data is public or provided in personal communication, consent for publication was given
556
557
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
558
5. If you used crowdsourcing conducted research with human subjects...
14

---

580
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
562
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount
585
spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "wiGbjgOFEH", "reviewer": "Reviewer_3Pkg", "summary": "This paper proposes a framework for solving vehicle routing problems by combining the strength of deep learning and dynamic programming. The basic idea is to use a graph neural network to restrict the search space and then boost the DP algorithm. The experiment results for the traveling salesman problem (TSP), the vehicle routing problem (VRP), and TSP with time windows (TSPTW) show that the proposed method can achieve similar performance as LKH and outperform most other neural nets-based algorithms.", "questions": "", "limitations": "", "rating": 6, "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: This work employs a framework of using learned neural heuristics to guide dynamic programming algorithms. The model consists of a GNN [3] and a beam search. I think this framework is not completely novel but solid enough.\n\nQuality: The paper is solid. Authors provide experiments with detailed analysis.\n\nClarity: The paper is clearly written and easy to follow.\n\nSignificance: The proposed framework exhibits good generalization towards different vehicle routing problems, as it can efficiently handle hard constraints. Meanwhile, the experiment results demonstrate that the model outperforms the state-of-art algorithm to solve TSPTW, which is impressive. However, it still does not beat some other algorithms [1, 2] for CVRP.\n\n[1] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611–624, 2012.\n\n[2] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.\n\n[3] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some comments:\n\n1)  I think this framework has very good generalizability and is very promising for solving other problems. I encourage the authors to apply this framework to other graph-related combinatorial optimization problems (for example, job scheduling).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "ezHfvgJN9m", "reviewer": "Reviewer_jZhT", "summary": "The paper investigates dynamic programming techniques for routing that relies on auxiliary neural network models. The idea is to predict a \"heatmap\" of edges indicating whether they are promising or not for good-quality solutions, which needs to be generated only once per instance. The problem is then solved by a (forward) dynamic program that expands states based on scores extracted by the heatmap. The methodology is applied to the vehicle routing problem (VRP), the traveling salesperson problem (TSP), and the TSP with time windows (TSPTW).", "questions": "", "limitations": "", "rating": 5, "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 believe the key ideas underlying the paper are somewhat incremental, albeit nicely combined together. More specifically, the methodology is conceptually close to a value-function approximation that is defined in terms of their scoring policy. Thus, it is akin to a reinforcement learning approach and builds upon many of the references that the authors appropriately cite but do not discuss or highlight appropriately, in my view.\n\nIn particular, deep learning has been used to guide tree search (e.g., references [26] and [34] in the paper). The differences here, to the best of my knowledge, are (a) the routing applications, (b) the fact that authors expand DP states (allowing them to break some symmetry and dominance) and not tree nodes; and (c) the heatmap and beam search implementation for DPs. I would strongly suggest the authors to extend their related work discussion to make this comparison clearer.\n\n**Quality**\n\nMy major concern in terms of quality is that results still read as somewhat preliminary (which seems to be still consistent with the previous ICML comments as well).\n\nIndeed, there are improvements with respect to the neural network approaches evaluated by the authors and the TSPTW results are meaningful. However, it does not seem that the paper outperforms exact approaches for small instances (e.g., Concorde/TSP) nor standard heuristic techniques (e.g., LKH/VRP) in several settings. The overall tradeoffs between their technique (considering the implementation complexities/training) and other methods are not clear.\n\nMoreover, the scalability benefits mentioned by the authors was not investigated further; for example, authors do not indicate whether their method really scales for instances with significant more nodes (e.g., a few thousand).\n\n**Clarity**\n\nThe paper is well written. I believe the results are mostly reproduceable, though there are a few parameters based on \"educated guesses\" as indicated by the authors. Some further discussion concerning training and limitations could have also been beneficial.\n\n**Significance**\n\nIn my view, the paper presents meaningful and interesting ideas, but still requires a stronger experimental section to be of interest beyond a specific area (i.e., deep learning models to routing problems). For example, authors could demonstrate the scalability of their method to instances with a few thousand nodes, which is common in papers investigating LKH-3. Connection to existing works must also be presented in much more details.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct negative societal impacts to the best of my knowledge.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MO8RNevwx4h", "reviewer": "Reviewer_C5JT", "summary": "The paper proposes a framework for solving vehicle routing problems, based on a combination of supervised learning and dynamic programming. The proposed method is an extension of the restricted dynamic programming algorithm where at each iteration, the selection of the (fixed number of) most promising solutions is done by a learning-based heuristic. The framework is tested on instances of 100 nodes of the TSP, CVRP and TSP with time windows. \n", "questions": "", "limitations": "", "rating": 5, "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---------------\nThe novelty of this work is the use of a learned heuristic to define the criteria upon which the most promising states are selected in a restricted dynamic programming algorithm. The criteria is based on a heat map provided by an existing pretrained neural network and a “potential” formula that is handcrafted by the authors.  \n\nThe contributions are clearly positioned w.r.t related works.\n\nQuality\n----------\nThe paper is of high quality. The explanation of how the framework is adapted for each of the 3 routing problems is clear. \nThe authors discuss both the strengths and limitations of their work and do not overclaim their contribution. \nI appreciated the comparison to a stronger (non-learned) heuristic baseline (HGS) for the VRP experiments. \n\nRegarding the framework itself, I wonder how it differs from a beam search using the same scoring function (heat+potential) with the elimination of dominated solutions at each step. Or an A* algorithm with the same elimination trick. In other words, what is \"dynamic programming-specific\" about this framework?\n\nClarity\n---------\nThe paper is very well-written and easy to follow. \n\nDetails:\n* I found confusing that at L112 “state variables” are defined as triplets (visited, current, cost) and then  L122 “DP state” is defined as only (visited, current) \n* Figure 3 titles and legends fonts are too small \n* L189 \"travel time is equal to cost/distance\" not clear \n* L337 We *believe*\n\nSignificance\n----------------\nTh proposed framework is flexible and able to naturally handle constraints, which is a big strength compared to other NCO methods.\n\nHowever, the reported results are slightly better or close to the best existing NCO methods but still not as good as specialized algorithms. And these results were obtained on graphs of size 100, which is relatively small compared to what can be solved, both with specialized methods and NCO today. For instance the cited reference [17] solves TSP problems with up to 10,000 nodes. As noted by the authors, standard VRP benchmarks have instances of 100 to 1000 nodes. \n\nThe authors note that scaling is challenging because of the “fully-connected O(n^2) GNN” but this GNN is an essential ingredient of their framework so it’s not clear if/how this framework can scale.\n\nTherefore despite the high quality of the paper, I feel like it is quite an incremental contribution.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, in the checklist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "DUtj1Jl8x6B", "reviewer": "Reviewer_fh68", "summary": "The present submission is concerned with dynamic programming (DP) methods for  traveling salesperson problems and a capacitated vehicle problem. Since DP for these problems struggles with enormous DP table sizes, the authors propose to heuristically prune the DP table using a neural network. \n\nEssentially, the idea is to leverage recent approaches that use neural network to predict good solutions for combinatorial optimization problems. In this particular case, a neural network is used to predict partial solutions, and these in turn allow the others to compute priority values for the edges. High priority edges are preferred in the solution expansion step of the DP.\n\nThe contribution of the paper is the evaluation of the approach (which, according to the authors, has not been tried before); the neural network itself stems from the literature (with few modifications).", "questions": "", "limitations": "", "rating": 4, "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": "The paper is generally well written and nicely illustrated. The only two aspects of the writeup that I found lacking was that none of the considered problems are defined in the paper, not even informally; and that not all column labels in the computational tables are defined. \n\nI found the proposed approach intriguing. From the combinatorial optimization point of view, I feel it is more attractive to combine DP and neural networks than to use neural networks directly to predict good solutions. Additionally, it seems that the approach is easily applied to other problems as well, provided there is a DP scheme and a suitable neural network; nothing in the approach is really specific to vehicle routing/TSP. On the other hand, the approach does away with a major benefit of DP, namely, that optimality may be guaranteed. In fact, there are no theoretical guarantees.\n\nThe computational experiments are extensive:\n\n- For the TSP, the authors compare to a large body of literature including the Concorde TSP solver which is a staple in the combinatorial optimization community. Indeed, the results look favorable for Concorde (Concorde finds a better solution while requiring only one fourth of the running time), although the authors approach seems to be superior to the other algorithms from the literature. \n\n- For the VRP, the authors compare to genetic algorithms and an ancient DP approach. The authors approach offers a speed-up of about a factor of 10 at the expense of losing 2 percent of the solution quality. The approach is unable to find competitive solutions even if allowed several times the running time of the approaches from the literature. Hence, the usefulness of the approach depends on the trade-offs that the user is willing to make.\n\n- TSP with time windows: The authors compare against a combination of constraint programming and learning, and against a local search appraoch. This time, the results look largely favorable for the new approach.\n\nOverall, however, the choice of reference algorithms seems a bit arbitrary; I found the text did not make clear why were these particular algorithms chosen and others were not. For instance, reference [1] is not included in the VRP experiments. The benchmark instances for TSP stem from another learning publication; what about the standard TSPlib benchmark?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My conclusion from the experiments is that the proposed approach is promising, but I am not convinced that it would beat mathematical programming based approaches, even though these would certainly be the method of choice in combinatorial optimization/operations research where TSP/VRP originates and is heavily studied. Indeed, the only math. programming approach (Concorde) included in the comparison turns out to be superior. To illuminate this question, further literature review and extended benchmarks with new instance sets from the OR community would be required.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a neural network based approach to dynamic programming with large state spaces and applies it to traveling salesman and vehicle routing problems. While the paper is well written and interesting, the experimental side is preventing acceptance at NeurIPS. In particular, while it is not strictly needed to outperform competitors, the theoretical novelty just needs to be larger to merit publication.

In order to better prove the merit of the presented approach, running the algorithm on problems where dynamic programming is a better methodology than TSP might be one avenue, as suggested by the reviewers.
Decision: Reject