Deep Policy Dynamic Programming for Vehicle Routing Problems
Year: 2021

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

text: Routing problems are a class of combinatorial problems with many practical1 applications. Recently, end-to-end deep learning methods have been proposed2 to learn approximate solution heuristics for such problems. In contrast, classical3 dynamic programming (DP) algorithms guarantee optimal solutions, but scale4 badly with the problem size. We propose Deep Policy Dynamic Programming5 (DPDP), which aims to combine the strengths of learned neural heuristics with6 those of DP algorithms. DPDP prioritizes and restricts the DP state space using7 a policy derived from a deep neural network, which is trained to predict edges8 from example solutions. We evaluate our framework on the travelling salesman9 problem (TSP), the vehicle routing problem (VRP) and TSP with time windows10 (TSPTW) and show that the neural policy improves the performance of (restricted)11 DP algorithms, making them competitive to strong alternatives such as LKH, while12 also outperforming most other ‘neural approaches’ for solving TSPs, VRPs and13 TSPTWs with 100 nodes.14
1 Introduction15
Dynamic programming (DP) is a powerful framework for solving optimization problems by solving16 smaller subproblems through the principle of optimality [3]. Famous examples are Dijkstra’s17 algorithm [14] for the shortest route between two locations, and the classic Held-Karp algorithm for18 the travelling salesman problem (TSP) [23, 4]. Despite their long history, dynamic programming19 algorithms for vehicle routing problems (VRPs) have seen limited use in practice, primarily due to20 their bad scaling performance. More recently, a line of research has attempted the use of machine21 learning (especially deep learning) to automatically learn heuristics for solving routing problems22 [57, 5, 41, 29, 7]. While the results are promising, most learned heuristics are not (yet) competitive23 to ‘traditional’ algorithms such as LKH [24] and lack (asymptotic) guarantees on their performance.24
In this paper, we propose Deep Policy Dynamic Programming (DPDP) as a framework for solving25 vehicle routing problems. The key of DPDP is to combine the strengths of deep learning and DP,26 by restricting the DP state space (the search space) using a policy derived from a neural network.27 In Figure 1 it can be seen how the neural network indicates promising parts of the search space28 (through a heatmap over the edges of the graph), which is then used by the DP algorithm to find a29 good solution. DPDP is more powerful than some related ideas [62, 52, 61, 6, 34] as it combines30 supervised training of a large neural network with just a single model evaluation at test time, to enable31 running a large scale guided search using DP. The DP framework is flexible as it can model a variety32 of realistic routing problems with difficult practical constraints [20]. We illustrate this by testing33 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 a restricted dynamic programming35 algorithm [20]. Such an algorithm heuristically reduces the search space by retaining only the B most36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
promising solutions per iteration. The selection process is very important as it defines the part of the37 DP state space considered and, thus, the quality of the solution found (see Fig. 2). Instead of manually38 defining a selection criterion, DPDP defines it using a (sparse) heatmap of promising route segments39 obtained by pre-processing the problem instance using a (deep) graph neural network (GNN) [26].40 This approach is reminiscent of neural branching policies for branch-and-bound algorithms [19, 40].41
In this work, we thus aim for a ‘neural boost’ of DP algorithms, by using a graph neural network42 for scoring partial solutions. Prior work on ‘neural’ vehicle routing has focused on auto-regressive43 models [57, 5, 13, 29], but they have high computational cost when combined with (any form of)44 search, as the model needs to be evaluated for each partial solution considered. Instead, we use (for45 TSP) and adapt (for VRP and TSPTW) a model to predict a heatmap indicating promising edges [26],46 and define the score of a partial solution as the ‘heat’ of the edges it contains (plus an estimate of the47 ‘heat-to-go’ or potential of the solution). As the neural network only needs to be evaluated once for48 each instance, this enables a much larger search (defined by B), making a good trade-off between49 quality and computational cost. Additionally, we can apply a threshold to the heatmap to define a50 sparse graph on which to run the DP algorithm, reducing the runtime by eliminating many solutions.51
Figure 2 illustrates the overall DPDP algorithm. In Section 4, we show that DPDP significantly52 improves over ‘classic’ restricted DP algorithms (with the same B). Additionally, we show that53 DPDP outperformes most other ‘neural’ approaches for TSP, VRP and TSPTW and is competitive54 with the highly-optimized LKH solver [24] for VRP, while achieving similar results much faster for55 TSP and TSPTW. For TSPTW, DPDP also outperforms the best open-source solver we could find56 [10], illustrating the power of DPDP to handle difficult hard constraints (time windows).57
2 Related work58
DP has a long history as an exact solution method for routing problems [31, 50], e.g. for the TSP59 with time windows [15] and precedence constraints [39], but typically limited to small problems only,60 due to the curse of dimensionality. Restricted DP (with heuristic policies) has been used to address,61 e.g., the time dependent TSP [37], and has been generalized into a flexible framework for VRPs with62 different types of practical constraints [20]. DP approaches have also been shown to be useful in63 settings with difficult practical issues such as time-dependent travel times and driving regulations [28]64 or stochastic demands [42]. For a thorough investigation of modelling choices of DP for routing (and65 scheduling), see [53]. For sparse graphs, alternative, but less flexible, formulations can be used [8].66
Despite the flexibility, constructive DP methods have not gained much popularity compared to67 heuristic search approaches such as Ruin and Recreate [47], Adaptive Large Neighborhood Search68 [46], LKH [24] or FILO [1]. While highly effective, these methods are limited in their flexibility as69 special operators need to be engineered for different types of problems. While restricted DP was70 shown to have superior performance on realistic VRPs with many constraints [20], the performance71 gap of around 10% for standard (benchmark) VRPs (with time windows) is too large to popularize72 the restricted dynamic programming approach. We argue that the missing ingredient for restricted73 dynamic programming is the availability of a strong but computationally cheap policy for selecting74 which solutions should be considered, which is the motivation behind DPDP.75
In the machine learning community, recent advances have significantly improved deep neural networks76 (DNNs) to perform tasks such as image classification and machine translation [32]. After the first77 deep learning model was trained (using example solutions) to construct TSP tours [57], many78 improvements have been proposed, e.g. different training strategies such as reinforcement learning79 (RL) [5, 27, 12, 30] and model architectures, which enabled the same idea to be used for other80 routing problems [41, 29, 13, 45, 16, 60]. Most constructive neural methods are auto-regressive,81 evaluating the model many times to predict one node at the time, but other works have considered82 predicting a ‘heatmap’ of promising edges at once [43, 26, 17], which allows a tour to be constructed83 (using sampling or beam search) without further evaluating the model. An alternative direction is84 ‘learning to search’, where a neural network is used to guide a search procedure such as local search85 [7, 35, 18, 59, 25]. Some works have attempted scaling to larger instances beyond 100 nodes, which86 remains challenging [36, 17]. The combination of machine learning with DP has been proposed in87 limited settings [62, 52, 61]. Most related to our approach, a DP algorithm for TSPTW, guided by an88 RL agent, was implemented using an existing solver [6] and a neural network predicting edges has89 been combined with tree search [34] and local search for maximum independent set (MIS). For a90 wider view on machine learning for routing problems and combinatorial optimization, see [38, 54].91
3 Deep Policy Dynamic Programming92
DPDP uses an existing graph neural network [26] (which we modify for VRP and TSPTW) to predict93 a heatmap of promising edges, which is used to derive the policy for scoring partial solutions in94 the DP algorithm. The DP algorithm starts with a beam of a single initial (empty) solution. It then95 proceeds by iterating the following steps: (1) all solutions on the beam are expanded, (2) dominated96 solutions are removed for each DP state, (3) the B best solutions according to the scoring policy97 define the beam for the next iteration. These steps are illustrated in Fig. 2. The objective function is98 used to select the best solution from the final beam. The resulting algorithm is a beam search over the99 DP state space (which is not a ‘standard beam search’ over the solution space!) and we call B the100 beam size. DPDP is asymptotically optimal as using B = n · 2n for a TSP with n nodes guarantees101 optimal results, but choosing smaller B allows to trade performance for computational cost.102
DPDP is a generic framework that can be applied to different problems, by defining the following103 ingredients: (1) the state variables to track while constructing solutions, (2) the initial solution,104 (3) feasible actions to expand solutions, (4) rules to define dominated solutions and (5) a scoring105 policy for selecting the B solutions to keep. A solution is always (uniquely) defined as a sequence of106 actions, which allows the DP algorithm to construct the final solution by backtracking. In the next107 sections, we define these ingredients for the TSP, VRP and TSPTW.108
3.1 Travelling Salesman Problem109
We implement DPDP for Euclidean TSPs with n nodes on a (sparse) graph, where the cost for edge110 (i, j) is given by cij , the Euclidean distance between the coordinates of nodes i and j.111
For each partial solution, defined by a sequence of actions a, the state variables are cost(a), the112 total cost (distance), current(a), the current node, and visited(a), the set of visited nodes (including113 the start node). Without loss of generality, we let 0 be the start node, so we initialize the beam at step114 t = 0 with the empty initial solution with cost(a) = 0, current(a) = 0 and visited(a) = {0}. At115 step t, the action at ∈ {0, ..., n − 1} indicates the next node to visit, and is a feasible action for a116 partial solution a = (a0, ..., at−1) if (at−1, at) is an edge in the graph and at 6∈ visited(a), or, when117 all are visited, if at = 0 to return to the start node. When expanding the solution to a′ = (a0, ..., at),118 we can compute the state variables incrementally as:119
cost(a′) = cost(a) + ccurrent(a),at , current(a ′) = at, visited(a ′) = visited(a) ∪ {at}. (1)
A (partial) solution a is a dominated solution if there exists a (dominating) solution a∗ such120 that visited(a∗) = visited(a), current(a∗) = current(a) and cost(a∗) < cost(a). The tuple121 (visited(a), current(a)) we refer to as the DP state, so removing all dominated partial solutions,122 we keep exactly one minimum-cost solution for each unique DP state1. Since a solution can only123 dominate other solutions with the same set of visited nodes, we only need to remove dominated124 solutions from sets of solutions with the same number of actions. Therefore, we can efficiently125 execute the DP algorithm in iterations, where at step t all solutions have (after t actions) t+ 1 visited126 nodes (including the start node), keeping the memory need at O(B) states (with B the beam size).127
We define the scoring policy using a pretrained model [26], which takes as input node coordinates128 and edge distances to predict a raw ‘heatmap’ value ĥij ∈ (0, 1) for each edge (i, j). The model was129 trained to predict optimal solutions, so ĥij can be seen as the probability that edge (i, j) is in the130 optimal tour. We force the heatmap to be symmetric thus we define hij = max{ĥij , ĥji}. The policy131 is defined using the heatmap values, in such a way to select the (partial) solutions with the largest132 total heat, while also taking into account the (heat) potential for the unvisited nodes. The policy thus133 selects the B solutions which have the highest score, defined as score(a) = heat(a)+potential(a),134 with heat(a) = ∑t−1 i=1 hai−1,ai , i.e. the sum of the heat of the edges, which can be computed135 incrementally when expanding a solution. The potential is added as an estimate of the ‘heat-to-136 go’ (similar to the heuristic in A∗ search) for the remaining nodes, and avoids the ‘greedy pitfall’137 of selecting the best edges while skipping over nearby nodes, which would prevent good edges138 from being used later. It is defined as potential(a) = potential0(a) + ∑ i6∈visited(a) potentiali(a)139
with potentiali(a) = wi ∑ j 6∈visited(a) hji∑n−1
k=0 hki , where wi is the node potential weight given by140 wi = (maxj hji) · (1 − 0.1( ci0maxj cj0 − 0.5)). By normalizing the heatmap values for incoming141 edges, the (remaining) potential for node i is initially equal to wi but decreases as good edges142 become infeasible due to neighbours being visited. The node potential weight wi is equal to the143 maximum incoming edge heatmap value (an upper bound to the heat contributed by node i), which144 gets multiplied by a factor 0.95 to 1.05 to give a higher weight to nodes closer to the start node, which145 we found helps to encourage the algorithm to keep edges that enable to return to the start node. The146 overall heat + potential function identifies promising partial solutions and is computationally cheap.147
3.2 Vehicle Routing Problem148
For the VRP, we add a special depot node to the graph, indicated by DEP. Each node i has a demand149 di, and the goal is to find multiple routes, which have a limited capacity denoted by CAPACITY.150
Additionally to the TSP state variables cost(a), current(a) and visited(a), we keep track of151 capacity(a), which is the remaining capacity in the current route/vehicle. A solution starts at the152 depot, so we initialize the beam at step t = 0 with the empty initial solution with cost(a) = 0,153 current(a) = DEP, visited(a) = ∅ and capacity(a) = CAPACITY. For the VRP, we do not consider154 visiting the depot as a separate action. Instead, we define 2n actions, where at ∈ {0, ..., 2n − 1}.155 The actions 0, ..., n− 1 indicate a direct move from the current node to node at, whereas the actions156
1If 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.
n, ..., 2n − 1 indicate a move to node at − n via the depot. Feasible actions are those that move157 to unvisited nodes via edges in the graph and obey the following constraints. For the first action158 a0 there is no choice and we constrain (for convenience of implementation) a0 ∈ {n, ..., 2n − 1}.159 A direct move (at < n) is only feasible if dat ≤ capacity(a) and updates the state similar to TSP160 but reduces remaining capacity by dat . A move via the depot is always feasible (respecting the161 graph edges and assuming di ≤ CAPACITY ∀i) as it resets the vehicle CAPACITY before subtracting162 demand, but incurs the ‘via-depot cost’ cDEPij = ci,DEP + cDEP,j . When all nodes are visited, we allow a163 special action to return to the depot. This somewhat unusual way of representing a CVRP solution164 has desirable properties similar to the TSP formulation: at step t we have exactly t nodes visited, and165 we can run the DP in iterations, removing dominated solutions at each step t.166
For VRP, a partial solution a is a dominated solution dominated by a∗ if visited(a∗) = visited(a)167 and current(a∗) = current(a) (i.e. a∗ corresponds to the same DP state) and cost(a∗) ≤ cost(a)168 and capacity(a∗) ≥ capacity(a), with at least one of the two inequalities being strict. This means169 that for each DP state, given by the set of visited nodes and the current node, we do not only keep170 the (single) solution with lowest cost (as in the TSP algorithm), but keep the complete set of pareto-171 efficient solutions in terms of cost and remaining vehicle capacity. This is because a higher cost172 partial solution may still be preferred if it has more remaining vehicle capacity, and vice versa.173
For the VRP scoring policy, we modify the model [26] to include the depot node and demands. The174 special depot node gets a separate learned initial embedding parameter, and we add additional edge175 types for connections to the depot, to mark the depot as being special. Additionally, each node gets176 an extra input (next to its coordinates) corresponding to di/CAPACITY (where we set dDEP = 0).177 Apart from this, the model remains exactly the same2. The model is trained on example solutions178 from LKH [24] (see Section 4.2), which are not optimal, but still provide a useful training signal.179 Compared to TSP, the definition of the heat is slightly changed to accommodate for the ‘via-depot180 actions’ and is best defined incrementally using the ‘via-depot heat’ hDEPij = hi,DEP · hDEP,j · 0.1,181 where multiplication is used to keep heat values interpretable as probabilities and in the range (0, 1).182 The additional penalty factor of 0.1 for visiting the depot encourages the algorithm to minimize the183 number of vehicles/routes. The initial heat is 0 and when expanding a solution a to a′ using action184 at, the heat is incremented with either hcurrent(a),at (if at < n) or h DEP current(a),at−n (if at ≥ n). The185 potential is defined similarly to TSP, replacing the start node 0 by DEP.186
3.3 Travelling Salesman Problem with Time Windows187
For the TSPTW, we also have a special depot / start node 0, and each node i has a time window188 defined by (li, ui) in which the node should be visited, assuming travel time is equal to cost/distance.189 It is allowed to wait if arrival at a node is before li, but arrival cannot be after ui (i.e. the constraint is190 hard). We consider the objective to be minimizing total cost, but minimizing total time (or makespan)191 only requires training on different example solutions. Due to the hard constraints, TSPTW is typically192 considered more challenging to solve than plain TSP, for which every solution is feasible.193
The state variables and initial solution are equal to TSP except that we add time(a) which is194 initially 0 (= l0). Feasible actions at ∈ {0, ..., n − 1} are those that move to unvisited nodes via195 edges in the graph such that the arrival time is no later than uat and do not directly eliminate the196 possibility to visit other nodes in time3. Expanding a solution a to a′ using action at updates the197 time as time(a′) = max{time(a) + ccurrent(a),at , lat}.198 For each DP state, we keep all efficient solutions in terms of cost and time, so a partial solution a is a199 dominated solution dominated by a∗ if a∗ has the same DP state (visited(a∗) = visited(a) and200 current(a∗) = current(a)) and is strictly better in terms of cost and time, i.e. cost(a∗) ≤ cost(a)201 and time(a∗) ≤ time(a), with at least one of the two inequalities being strict.202 The model [26] for the scoring policy is adapted to include the time windows (li, ui) as node features203 (in the same unit as coordinates and costs), and we use a special embedding for the depot similar to204 VRP. Due to the time dimension, a TSPTW solution is directed, and edge (i, j) may be good whereas205 (j, i) may be not, so we adapt the model to enable predictions hij 6= hji (see details in Appendix206 B). We generated example training solutions using (heuristic) DP with a large beam size, which was207 faster than using LKH. Given the heat predictions, the score (heat + potential) is exactly as for TSP.208
2Except that we do not use the K-nearest neighbour feature [26] as it contains no additional information. 3E.g., arriving at a node i at t = 10 (including waiting) is not feasible if node j has uj = 12 and cij = 3.
3.4 Graph sparsity209
As described, the DP algorithm can take into account a sparse graph to define feasible expansions. As210 our problems are defined on sets of nodes rather than graphs, the use of a sparse graph is an artificial211 design choice, which allows to significantly reduce the runtime but may sacrifice the possibility to212 find good or optimal tours. We propose two different strategies for defining the sparse graph on213 which to run the DP: thresholding the heatmap values hij and using the K-nearest neighbour (KNN)214 graph. By default, we use a (low) heatmap threshold of 10−5, which rules out most of the edges as215 the model confidently predicts (close to) 0 for most edges. This is a secondary way to leverage the216 neural network (independent of the scoring policy), which can be seen as a form of learned problem217 reduction [49]. For symmetric problems (TSP and VRP), we add KNN edges in both directions. For218 the VRP, we additionally connect each node to the depot (and vice versa) to ensure feasibility.219
3.5 Implementation & hyperparameters220
We implement DPDP using PyTorch [44] to leverage batched computation on the GPU. For details,221 see Appendix A. Our code is publicly available.4 DPDP has very few hyperparameters, but the222 heatmap threshold of 10−5 and details like the functional form of e.g. the scoring policy are ‘educated223 guesses’ or manually tuned on a few validation instances and can likely be improved. The runtime is224 influenced by implementation choices which were manually selected using a few validation instances.225
4 Experiments226
4.1 Travelling Salesman Problem227
In Table 1 we report our main results for DPDP with beam sizes of 10K (10 thousand) and 100K,228 for the TSP with 100 nodes on a commonly used test set [29]. We report results using Concorde [2],229 LKH [24] and Gurobi [22], as well as recent results of the strongest methods using neural networks230 (‘neural approaches’) from literature. Running times for solving 10000 instances after training should231 be taken as rough indications as some are on different machines, typically with 1 GPU or a many-core232 CPU (8 - 32). The costs indicated with * are not directly comparable due to slight dataset differences233 [17]. Times for generating heatmaps (if applicable) is reported separately (as the first term) from the234 running time for MCTS [17] or DP. DPDP achieves close to optimal results, strictly outperforming235 the neural baselines achieving better results in less time (except POMO [30], see Section 4.2).236
4https://github.com/?????, to be disclosed after review
4.2 Vehicle Routing Problem237
For the VRP, we train the model using 1 million instances of 100 nodes, generated according to the238 distribution described by [41] and solved using one run of LKH [24]. We train using a batch size of239 48 and a learning rate of 10−3 (selected as the result of manual trials to best use our GPUs), for (at240 most) 1500 epochs of 500 training steps (following [26]) from which we select the saved checkpoint241 with the lowest validation loss. We use the validation and test sets by [29].242
Table 1 shows the results compared to a recent implementation of Hybrid Genetic Search (HGS)5,243 a SOTA heuristic VRP solver [56, 55]. HGS is faster and improves around 0.5% over LKH, which244 is typically considered the baseline in related work. We present the results for LKH, as well as the245 strongest neural approaches and DPDP with beam sizes up to 1 million. Some results used 2000246 (different) instances [35] and cannot be directly compared6. DPDP outperforms all other neural247 baselines, except POMO [30], which delivers good results very quickly by exploiting symmetries in248 the problem. However, as it cannot (easily) improve further with additional runtime, we consider this249 contribution orthogonal to DPDP. DPDP is competitive to LKH (see also Section 4.4).250
More realistic instances We also train the model and run experiments with instances with 100251 nodes from a more realistic and challenging data distribution [51]. This distribution, commonly used252 in the routing community, has greater variability, in terms of node clustering and demand distributions.253 LKH failed to solve two of the test instances, which we found out is because LKH by default uses254
a fixed number of routes equal to a lower bound, given by ⌈∑n−1
i=0 di CAPACITY
⌉ , which may be infeasible7.255
Therefore we solve these instances by rerunning LKH with an unlimited number of allowed routes256 (which in general gives worse results, see Section 4.4).257
DPDP was run on a machine with 4 GPUs, but we also report (estimated) runtimes for 1 GPU258 (1080Ti), and we compare against 16 or 32 CPUs for HGS and LKH. In Table 2 it can be seen that259 the difference with LKH is, as expected, slightly larger than for the simpler dataset, but still below260 1% for beam sizes of 100K-1M. We also observed a higher validation loss, so it may be possible to261 improve results using more training data. Nevertheless, finding solutions within 1% of the specialized262 SOTA HGS algorithm, and even closer to LKH, is impressive for these challenging instances, and we263 consider the runtime (for solving 10K instances) acceptable, especially when using multiple GPUs.264
4.3 TSP with Time Windows265
For the TSP with hard time window constraints, we use the data distribution by [6] and use their set266 of 100 test instances with 100 nodes. These were generated with small time windows, resulting in267 a small feasible search space, such that even with very small beam sizes, our DP implementation268 solves these instances optimally, eliminating the need for a policy. Therefore, we also consider a269 more difficult distribution similar to [10], which has larger time windows which are more difficult270 as the feasible search space is larger8 [15]. For details, see Appendix B. For both distributions, we271 generate training data and train the model exactly as we did for the VRP.272
5https://github.com/vidalt/HGS-CVRP 6The running time of 4000 hours (167 days) for 10K instances is estimated from 24min/instance [35]. 7For example, three nodes with a demand of two cannot be assigned to two routes with a capacity of three. 8Up to a limit, as making the time windows infinite size reduces the problem to plain TSP.

heading: PROBLEM SMALL TIME WINDOWS [6] (100 INST.) LARGE TIME WINDOWS [10] (10K INST.) METHOD COST GAP FAIL TIME COST GAP FAIL TIME
text: Table 3 shows the results for both data distributions, which are reported in terms of the difference273 to General Variable Neighbourhood Search (GVNS) [10], the best open-source solver for TSPTW274 we could find9, using 30 runs. For the small time window setting, both GVNS and DPDP find275 optimal solutions for all 100 instances in just 7 seconds (in total, either on 16 CPUs or a single GPU).276 LKH fails to solve one instance, but finds close to optimal solutions, but around 50 times slower.277 BaB-DQN* and ILDS-DQN* [6], methods combining an existing solver with an RL trained neural278 policy, take around 15 minutes per instance (orders of magnitudes slower) to solve most instances to279 optimality. Due to complex set-up, we were unable to run BaB-DQN* and ILDS-DQN* ourselves for280 the setting with larger time windows. In this setting, we find DPDP outperforms both LKH (where281 DPDP is orders of magnitude faster) and GVNS, in both speed and solution quality. This illustrates282 that DPDP, due to its nature, is especially well suited to handle constrained problems.283
4.4 Ablations284
Scoring policy To evaluate the value of different components of DPDP’s GNN Heat + Potential285 scoring policy, we compare against other variants. GNN Heat is the version without the potential,286 whereas Cost Heat + Potential and Cost Heat are variants that use a ‘heuristic’ ĥij =
cij maxk cik 287 instead of the GNN. Cost directly uses the current cost of the solution, and can be seen as ‘classic’288 restricted DP. Finally, BS GNN Heat + Potential uses beam search without dynamic programming,289 i.e. without removing dominated solutions. To evaluate only the scoring policy, each variant uses290 the fully connected graph (knn = n− 1). Figure 3a shows the value of DPDP’s potential function,291 although even without it results are still significantly better than ‘classic’ heuristic DP variants using292 cost-based scoring policies. Also, it is clear that using DP significantly improves over a standard beam293 search (by removing dominated solutions). Lastly, the figure illustrates how the time for generating294 the heatmap using the neural network, despite its significant value, only makes up a small portion of295 the total runtime.296
9https://github.com/sashakh/TSPTW
Beam size DPDP allows to trade off the performance vs. the runtime using the beam size B (and to297 some extent the graph sparsity, see Section 4.4). We illustrate this trade-off in Figure 3b, where we298 evaluate DPDP on 100 validation instances for VRP, with different beam sizes from 10K to 2.5M.299 We also report the trade-off curve for the LKH(U), which is the strongest baseline that can also300 solve different problems. We vary the runtime using 1, 2, 5 and 10 runs (returning the best solution).301 LKHU(nlimited) is the version which allows an unlimited number of routes (see Section 4.2). It is302 hard to compare GPU vs CPU, so we report (estimated) runtimes for different hardware, i.e. 1 or 4303 GPUs (with 3 CPUs per GPU) and 16 or 32 CPUs. We report the difference (i.e. the gap) with HGS,304 analog to how results are reported in Table 1. We emphasize that in most related work (e.g. [29]), the305 strongest baseline considered is one run of LKH, so we compare against a much stronger baseline.306 Also, our goal is not to outperform HGS (which is SOTA and specific to VRP) or LKH, but to show307 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 as another309 way to trade off performance and runtime of DPDP. In Figure 3c, we experiment with different310 heatmap thresholds from 10−5 to 0.9 and different values for KNN from 5 to 99 (fully connected).311 The heatmap threshold strategy clearly outperforms the KNN strategy as it yields the same results312 using sparser graphs (and lower runtimes). This illustrates that the heatmap threshold strategy is more313 informed than the KNN strategy, confirming the value of the neural network predictions.314
5 Discussion315
In this paper we introduced Deep Policy Dynamic Programming, which combines machine learning316 and dynamic programming for solving vehicle routing problems. The method yields close to optimal317 results for TSPs with 100 nodes and is competitive to the highly optimized LKH [24] solver for VRPs318 with 100 nodes. On the TSP with time windows, DPDP also outperforms LKH, being significanlty319 faster, as well as GVNS [10], the best open source solver we could find. Given that DPDP was not320 specifically designed for TSPTW, and still has possibilities for improvement, we consider this an321 impressive and promising achievement.322
The constructive nature of DPDP (combined with search) allows to efficiently address hard constraints323 such as time windows, which are typically considered challenging in neural combinatorial optimiza-324 tion [5, 29] and are also difficult for local search heuristics (as they need to maintain feasibility while325 adapting a solution). Given our results on TSP, VRP and TSPTW, and the flexibility of DP as a326 framework, we think DPDP has great potential for solving many more variants of routing problems,327 and possibly even other problems that can be formulated using DP (e.g. job shop scheduling [21]).328 We hope that our work brings machine learning research for combinatorial optimization closer to329 the operations research (especially vehicle routing) community, by combining machine learning330 with DP and evaluating the resulting new framework on different data distributions used by different331 communities [41, 51, 6, 10].332
Scope, limitations & future work Deep learning for combinatorial optimization is a recent re-333 search direction, which could significantly impact the way practical optimization problems get solved334 in the future. Currently, however, it is still hard to beat most SOTA problem specific solvers from the335 OR community. Despite our success for TSPTW, DPDP is not yet a practical alternative in general,336 but we do consider our results as highly encouraging for further research. We belief such research337 could yield significant further improvement by addressing key current limitations: (1) the scalability338 to larger instances, (2) the dependency on example solutions and (3) the heuristic nature of the scoring339 function. First, while 100 nodes is not far from the size of common benchmarks (100 - 1000 for VRP340 [51] and 20 - 200 for TSPTW [10]), scaling is a challenge, mainly due to the ‘fully-connected’ O(n2)341 graph neural network. Future work could reduce this complexity following e.g. [33]. The dependency342 on example solutions from an existing solver also becomes more prominent for larger instances,343 but could potentially be removed by ‘bootstrapping’ using DP itself as we, in some sense, have344 done for TSPTW (see Section 3.3). Future work could iterate this process to train the model ‘tabula345 rasa’ (without example solutions), where DP could be seen analogous to MCTS in AlphaZero [48].346 Lastly, the heat + potential score function is a well-motivated but heuristic function that was manually347 designed as a function of the predicted heatmap. While it worked well for the three problems we348 considered, it may need suitable adaption for other problems. Training this function end-to-end349 [11, 58], while keeping a low computational footprint, would be an interesting topic for future work.350
References351 [1] Luca Accorsi and Daniele Vigo. A fast and scalable heuristic for the solution of large-scale352 capacitated vehicle routing problems. Technical report, Tech. rep., University of Bologna, 2020.353
[2] David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006.354
[3] Richard Bellman. On the theory of dynamic programming. Proceedings of the National355 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. Journal357 of the ACM (JACM), 9(1):61–63, 1962.358
[5] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combina-359 torial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.360
[6] Quentin Cappart, Thierry Moisan, Louis-Martin Rousseau, Isabeau Prémont-Schwarz, and361 Andre Cire. Combining reinforcement learning and constraint programming for combinatorial362 optimization. arXiv preprint arXiv:2006.01610, 2020.363
[7] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial364 optimization. In Advances in Neural Information Processing Systems, volume 32, pages365 6281–6292, 2019.366
[8] William Cook and Paul Seymour. Tour merging via branch-decomposition. INFORMS Journal367 on Computing, 15(3):233–248, 2003.368
[9] Paulo Roberto de O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-369 opt heuristics for the traveling salesman problem via deep reinforcement learning. Proceedings370 of Machine Learning Research, 1:17, 2020.371
[10] Rodrigo Ferreira Da Silva and Sebastián Urrutia. A general vns heuristic for the traveling372 salesman problem with time windows. Discrete Optimization, 7(4):203–211, 2010.373
[11] Hal Daumé III and Daniel Marcu. Learning as search optimization: Approximate large margin374 methods for structured prediction. In Proceedings of the 22nd international conference on375 Machine learning, pages 169–176, 2005.376
[12] Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with377 combinatorial actions: An application to vehicle routing. Advances in Neural Information378 Processing Systems, 33, 2020.379
[13] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin380 Rousseau. Learning heuristics for the TSP by policy gradient. In International Conference on381 the Integration of Constraint Programming, Artificial Intelligence, and Operations Research,382 pages 170–181. Springer, 2018.383
[14] Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik,384 1(1):269–271, 1959.385
[15] Yvan Dumas, Jacques Desrosiers, Eric Gelinas, and Marius M Solomon. An optimal algorithm386 for the traveling salesman problem with time windows. Operations research, 43(2):367–371,387 1995.388
[16] Jonas K Falkner and Lars Schmidt-Thieme. Learning to solve vehicle routing problems with389 time windows through joint attention. arXiv preprint arXiv:2006.09100, 2020.390
[17] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to391 arbitrarily large tsp instances. arXiv preprint arXiv:2012.10658, 2020.392
[18] Lei Gao, Mingxiang Chen, Qichang Chen, Ganzhong Luo, Nuoyi Zhu, and Zhixin Liu. Learn393 to design the heuristics for vehicle routing problem. arXiv preprint arXiv:2002.08539, 2020.394
[19] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact395 combinatorial optimization with graph convolutional neural networks. In Advances in Neural396 Information Processing Systems.397
[20] Joaquim Gromicho, Jelke J van Hoorn, Adrianus Leendert Kok, and Johannes MJ Schutten.398 Restricted dynamic programming: a flexible framework for solving realistic vrps. Computers &399 operations research, 39(5):902–909, 2012.400
[21] Joaquim AS Gromicho, Jelke J Van Hoorn, Francisco Saldanha-da Gama, and Gerrit T Timmer.401 Solving the job-shop scheduling problem optimally by dynamic programming. Computers &402 Operations Research, 39(12):2968–2977, 2012.403
[22] Gurobi Optimization, LLC. Gurobi, 2018.404
[23] Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems.405 Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.406
[24] Keld Helsgaun. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained407 traveling salesman and vehicle routing problems: Technical report. 2017.408
[25] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle409 routing problem. arXiv preprint arXiv:1911.09539, 2019.410
[26] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional411 network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.412
[27] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the413 travelling salesman problem. arXiv preprint arXiv:1910.07210, 2019.414
[28] AL Kok, Elias W Hans, Johannes MJ Schutten, and Willem HM Zijm. A dynamic programming415 heuristic for vehicle routing with time-dependent travel times and required breaks. Flexible416 services and manufacturing journal, 22(1-2):83–108, 2010.417
[29] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In418 International Conference on Learning Representations, 2019.419
[30] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai420 Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in421 Neural Information Processing Systems, 33, 2020.422
[31] Gilbert Laporte. The vehicle routing problem: An overview of exact and approximate algorithms.423 European journal of operational research, 59(3):345–358, 1992.424
[32] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436,425 2015.426
[33] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh.427 Set transformer: A framework for attention-based permutation-invariant neural networks. In428 International Conference on Machine Learning, pages 3744–3753. PMLR, 2019.429
[34] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu-430 tional networks and guided tree search. Advances in Neural Information Processing Systems,431 page 539, 2018.432
[35] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving433 vehicle routing problems. In International Conference on Learning Representations, 2020.434
[36] Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti-435 mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint436 arXiv:1911.04936, 2019.437
[37] Chryssi Malandraki and Robert B Dial. A restricted dynamic programming heuristic algorithm438 for the time dependent traveling salesman problem. European Journal of Operational Research,439 90(1):45–55, 1996.440
[38] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning441 for combinatorial optimization: A survey. arXiv preprint arXiv:2003.03600, 2020.442
[39] Aristide Mingozzi, Lucio Bianco, and Salvatore Ricciardelli. Dynamic programming strategies443 for the traveling salesman problem with time window and precedence constraints. Operations444 research, 45(3):365–377, 1997.445
[40] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov,446 Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al.447 Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.448
[41] MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement449 learning for solving the vehicle routing problem. In Advances in Neural Information Processing450 Systems, pages 9860–9870, 2018.451
[42] Clara Novoa and Robert Storer. An approximate dynamic programming approach for the452 vehicle routing problem with stochastic demands. European Journal of Operational Research,453 196(2):509–515, 2009.454
[43] Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note on learning algorithms455 for quadratic assignment with graph neural networks. arXiv preprint arXiv:1706.07450, 2017.456
[44] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito,457 Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in458 pytorch. 2017.459
[45] Bo Peng, Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dy-460 namic attention model for vehicle routing problems. In International Symposium on Intelligence461 Computation and Applications, pages 636–650. Springer, 2019.462
[46] Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the463 pickup and delivery problem with time windows. Transportation science, 40(4):455–472, 2006.464
[47] Gerhard Schrimpf, Johannes Schneider, Hermann Stamm-Wilbrandt, and Gunter Dueck. Record465 breaking optimization results using the ruin and recreate principle. Journal of Computational466 Physics, 159(2):139–171, 2000.467
[48] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur468 Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general469 reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science,470 362(6419):1140–1144, 2018.471
[49] Yuan Sun, Andreas Ernst, Xiaodong Li, and Jake Weiner. Generalization of machine learning472 for problem reduction: a case study on travelling salesman problems. OR Spectrum, pages 1–27,473 2020.474
[50] Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM,475 2014.476
[51] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subrama-477 nian. New benchmark instances for the capacitated vehicle routing problem. European Journal478 of Operational Research, 257(3):845–858, 2017.479
[52] Wouter van Heeswijk and Han La Poutré. Approximate dynamic programming with neural480 networks in linear discrete action spaces. arXiv preprint arXiv:1902.09855, 2019.481
[53] Jelke J. van Hoorn. Dynamic Programming for Routing and Scheduling. PhD thesis, 2016.482
[54] Natalia Vesselinova, Rebecca Steinert, Daniel F Perez-Ramirez, and Magnus Boman. Learning483 combinatorial optimization on graphs: A survey with applications to networking. IEEE Access,484 8:120388–120416, 2020.485
[55] Thibaut Vidal. Hybrid genetic search for the cvrp: Open-source implementation and swap*486 neighborhood. arXiv preprint arXiv:2012.10384, 2020.487
[56] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A488 hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations489 Research, 60(3):611–624, 2012.490
[57] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural491 Information Processing Systems, pages 2692–2700, 2015.492
[58] Sam Wiseman and Alexander M Rush. Sequence-to-sequence learning as beam-search opti-493 mization. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language494 Processing, pages 1296–1306, 2016.495
[59] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement496 heuristics for solving routing problems. arXiv preprint arXiv:1912.05784, 2019.497
[60] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for498 solving routing problems. IEEE Transactions on Industrial Informatics, 2020.499
[61] Shenghe Xu, Shivendra S Panwar, Murali Kodialam, and TV Lakshman. Deep neural network500 approximated dynamic programming for combinatorial optimization. In Proceedings of the501 AAAI Conference on Artificial Intelligence, volume 34, pages 1684–1691, 2020.502
[62] Feidiao Yang, Tiancheng Jin, Tie-Yan Liu, Xiaoming Sun, and Jialin Zhang. Boosting dynamic503 programming with neural networks for solving np-hard problems. In Asian Conference on504 Machine Learning, pages 726–739. PMLR, 2018.505
Checklist506
1. For all authors...507 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s508 contributions and scope? [Yes]509 (b) Did you describe the limitations of your work? [Yes] Scaling and scoring policy, see510 discussion511 (c) Did you discuss any potential negative societal impacts of your work? [No] We do not512 see any issues513 (d) Have you read the ethics review guidelines and ensured that your paper conforms to514 them? [Yes]515 2. If you are including theoretical results...516
(a) Did you state the full set of assumptions of all theoretical results? [Yes] For claim that517 DPDP is asymptotically optimal, the DP description defines the set of assumptions and518 we note the beam size for which this holds.519
(b) Did you include complete proofs of all theoretical results? [No] Optimality and520 complexity of full DP for TSP is already known [23, 4] (we do not claim this is a new521 result, we just mention it)522
3. If you ran experiments...523 (a) Did you include the code, data, and instructions needed to reproduce the main experi-524 mental results (either in the supplemental material or as a URL)? [Yes] Code will be525 available upon release526
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they527 were chosen)? [Yes] We did a fair job to include all the information necessary to528 reproduce the experiments529
(c) Did you report error bars (e.g., with respect to the random seed after running experi-530 ments multiple times)? [No] For training the model, we used a standard supervised531 learning setup and we found training to be stable across different problems and data532 distributions. Due to high computational costs, we did not do multiple runs, which533 we consider conservative as likely results can be improved by further experiments and534 training with multiple seeds. As for evaluation of the algorithms on random instances,535 we use a large test set of 10.000 instances. As we use the same instances for our own536 implemented baselines, the statistical significance in such a ‘paired’ setting is much537 higher than would be suggested by error bars. For results directly reported from other538 papers, the margin is large enough with 10000 instances or we avoid strong claims.539 With our code, we plan to release all solutions for all test instances for the methods we540 evaluated ourselves.541
(d) Did you include the total amount of compute and the type of resources used (e.g.,542 type of GPUs, internal cluster, or cloud provider)? [Yes] While not explicitly, the543 total computational requirement for generating training data, which requires the most544 compute, can be derived from solving 1M instances and the time reported for solving545 10K instances in Table 1. This is a number of days (around 4) on a cluster with 10546 32-core machines, per problem.547
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...548 (a) If your work uses existing assets, did you cite the creators? [Yes]549 (b) Did you mention the license of the assets? [No] This can be found in the original550 repositories551 (c) Did you include any new assets either in the supplemental material or as a URL? [Yes]552 Will be provided with the released code as URL553 (d) Did you discuss whether and how consent was obtained from people whose data you’re554 using/curating? [No] Data is public or provided in personal communication, consent555 for publication was given556
(e) Did you discuss whether the data you are using/curating contains personally identifiable557 information or offensive content? [N/A]558
5. If you used crowdsourcing or conducted research with human subjects...559
(a) Did you include the full text of instructions given to participants and screenshots, if560 applicable? [N/A]561
(b) Did you describe any potential participant risks, with links to Institutional Review562 Board (IRB) approvals, if applicable? [N/A]563
(c) Did you include the estimated hourly wage paid to participants and the total amount564 spent on participant compensation? [N/A]565

Review summaries:
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.   Essentially, 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.  The 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).

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

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.  

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.