Source-linked AI summary
Deep Policy Dynamic Programming for Vehicle Routing Problems
Wouter Kool, Herke van Hoof, Joaquim Gromicho, Max Welling
TL;DR
Routing methods face a trade-off between DP’s optimality guarantees and poor scaling, and neural heuristics’ approximate solutions and limited competitiveness. DPDP combines neural edge-based policies with restricted DP, and evaluations on TSP, VRP, and TSPTW show strong performance against neural and classical alternatives. The method remains limited in scalability, dependence on example solutions, and heuristic scoring.
Problem
Dynamic programming offers optimal solutions but scales poorly, while learned routing heuristics are often not competitive with traditional algorithms and lack asymptotic guarantees.
Method
DPDP uses a GNN-predicted heatmap to score partial solutions and restrict the DP state space, retaining promising candidates through a beam over DP states.
Results
Across TSP, VRP, and TSPTW with 100 nodes, DPDP improves restricted DP, outperforms most neural approaches, competes with LKH for VRP, and outperforms LKH on TSPTW while being significantly faster.
Takeaways & Limitations
DPDP shows that combining learned policies with dynamic programming can provide strong routing performance while retaining flexibility for difficult constraints such as time windows.
Takeaways & Limitations
The authors identify scalability to larger instances, dependence on example solutions, and the heuristic nature of the scoring function as current limitations.
Abstract
from arXiv · showhide
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 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.
1 Introduction
DPDP combines neural edge predictions with restricted dynamic programming to guide routing search. Across TSP, VRP, and TSPTW, this approach improves restricted DP and achieves competitive results against strong routing solvers.
- Classical DP provides optimality principles but scales poorly for vehicle routing, while learned heuristics often lack competitiveness and performance guarantees.
- DPDP restricts the DP state space using a neural policy that identifies promising graph edges through a heatmap.The heatmap guides which parts of the search space the DP algorithm explores.
- DPDP is evaluated on the TSP, capacitated VRP, and TSPTW, including hard time-window constraints.
- A GNN is evaluated once per instance, scoring partial solutions through edge heat and potential while enabling larger searches and sparse-graph runtime reductions.
- DPDP improves over classic restricted DP, outperforms most neural approaches, competes with LKH for VRP, and achieves similar results faster for TSP and TSPTW.For TSPTW, it also outperforms the best open-source solver identified by the authors.
2 Related work
Prior routing methods include exact and restricted DP, heuristic search, and neural construction approaches, but each has important limitations. DPDP addresses the need for a computationally cheap policy that selects promising solutions across constrained routing problems.
- Exact DP methods handle routing problems but are limited to small instances by the curse of dimensionality.
- Heuristic search methods are effective but require specialized operators for different problem types, limiting their flexibility.
- Restricted DP previously showed a roughly 10% performance gap on standard benchmark VRPs with time windows, hindering broader adoption.
- Neural routing methods expanded from supervised TSP tour construction to reinforcement learning, varied architectures, and additional routing problems, but are often autoregressive.
- Prior work combined machine learning with DP or used neural edge predictions with tree search, while DPDP applies edge predictions through a policy with a potential function.
3 Deep Policy Dynamic Programming
DPDP guides restricted dynamic programming with neural edge predictions, using beam search, dominance rules, and problem-specific state representations for TSP, VRP, and TSPTW. It also uses learned graph sparsity to reduce feasible expansions, trading runtime against the possibility of missing good or optimal tours.
- Core DPDP framework: DPDP derives a scoring policy from a neural edge heatmap and retains the B highest-scoring partial solutions in each DP iteration.The beam search expands solutions, removes dominated states, and selects the next beam using heat plus a potential estimate.
- 3.1 Travelling Salesman Problem: For TSP, partial solutions track cost, current node, and visited nodes, with feasible actions extending tours and eventually returning to the start.Costs, current nodes, and visited sets are updated incrementally as actions are appended.
- 3.1 Travelling Salesman Problem: TSP dominance keeps the minimum-cost partial solution for each state defined by its visited-node set and current node.Removing dominated solutions enables iterative execution while requiring O(B) memory for beam size B.
- 3.2 Vehicle Routing Problem: VRP extends the state with remaining vehicle capacity and represents direct moves and depot-mediated moves as distinct actions.Routes start and end at the depot, and each route’s demand must not exceed vehicle capacity; VRP dominance preserves Pareto-efficient solutions by cost and remaining capacity.
- 3.2 Vehicle Routing Problem: The VRP scoring policy modifies the neural model for depot and demand information and penalizes depot visits to encourage fewer routes.Via-depot heat is multiplied by 0.1, and the potential is defined analogously to TSP with the depot replacing the start node.
- 3.4 Graph sparsity: DPDP restricts feasible expansions with heatmap thresholding or a K-nearest-neighbour graph, reducing runtime while potentially excluding good or optimal tours.The default heatmap threshold is 10^-5; VRP graphs additionally connect every node with the depot to preserve feasibility.
4 Experiments
Experiments evaluate DPDP on TSP, VRP, realistic VRP, TSPTW, and ablations. Across these settings, DPDP is competitive with strong specialized solvers, outperforms most neural baselines, and benefits from its learned scoring and sparsification choices.
- 4.1 Travelling Salesman Problem: DPDP achieves close-to-optimal TSP results and strictly outperforms neural baselines in better time, except POMO.The evaluation uses 10,000 TSP instances with beam sizes of 10K and 100K.
- 4.2 Vehicle Routing Problem: DPDP outperforms all other neural VRP baselines except POMO and remains competitive with LKH.The comparison includes beam sizes up to 1 million; HGS improves around 0.5% over LKH and is faster.
- 4.2 Vehicle Routing Problem: For realistic VRP instances, DPDP stays below a 1% gap from LKH at beam sizes of 100K–1M.The authors report solutions within 1% of HGS and even closer to LKH, using estimated runtimes across GPU and CPU configurations.
- 4.3 TSP with Time Windows: For larger time windows, DPDP outperforms both LKH and GVNS in speed and solution quality.With small time windows, DPDP and GVNS solve all 100 instances optimally in 7 seconds, while LKH is around 50 times slower.
- 4.4 Ablations: The GNN Heat + Potential policy improves over cost-based restricted DP, while dynamic programming improves over standard beam search.Heatmap generation contributes only a small portion of total runtime despite its value.
- 4.4 Ablations: Heatmap threshold sparsification matches k-nearest-neighbor results with sparser graphs and lower runtimes.The comparison varies heatmap thresholds from 10^-5 to 0.9 and k_n values from 5 to 99.
5 Discussion
DPDP combines machine learning with dynamic programming for routing and shows strong results on TSP, VRP, and TSPTW, while remaining limited in general practicality and scalability.
- 5 Discussion: DPDP combines machine learning and dynamic programming to solve vehicle routing problems.Its constructive search can address hard constraints such as time windows.
- 5 Discussion: DPDP achieves near-optimal results for 100-node TSPs, competes with LKH on 100-node VRPs, and outperforms LKH and GVNS on TSPTW.On TSPTW, it is also significantly faster than LKH.
- 5 Discussion: DPDP is not yet a practical alternative in general and faces limitations in scalability, dependence on example solutions, and heuristic scoring.The scalability challenge is mainly associated with the fully connected O(n^2) graph neural network.
- 5 Discussion: The authors identify larger-instance scalability, dependence on example solutions, and heuristic scoring as priorities for future work.They suggest reducing graph-network complexity and potentially bootstrapping without example solutions.
A Implementation
The implementation uses PyTorch to run the dynamic programming algorithm on a GPU, accelerating generic vectorized computations.
- A Implementation: The dynamic programming algorithm is implemented on a GPU using PyTorch for faster vectorized computation.PyTorch is used here as a computational framework, not only as a deep-learning framework.
A.1 Beam variables
The beam stores partial-solution state variables and parent information, while retaining only a trace for later backtracking to reduce memory use.
- A.1 Beam variables: Each beam solution tracks cost, current node, visited nodes, and problem-specific capacity or current time.A parent vector records which previous beam solution generated each expansion.
- A.1 Beam variables: The implementation stores parents and last actions rather than past beams, enabling solution backtracking after search finishes.The trace is stored in CPU memory and has size O(Bn) to save GPU memory.
- A.1 Beam variables: Visited nodes are packed into 64-bit bitmasks, allowing fast feasibility checks with bitwise operations.For 100 nodes, the implementation uses two packed integers.
A.2 Generating non-dominated expansions
Non-dominated expansion handling groups beam parents by visited-node sets because dominance comparisons are valid only among solutions sharing the same dynamic-programming state.
- A.2 Generating non-dominated expansions: Two solutions can be compared for dominance only when they have identical visited-node sets and current nodes.These shared variables define the same dynamic-programming state.
- A.2 Generating non-dominated expansions: The implementation groups current beam solutions by visited-node set before generating expansions, restricting dominance checks to relevant groups.A lexicographic sort of packed bitmasks can perform this grouping efficiently.
A.2.1 Travelling Salesman Problem
The TSP implementation generates feasible expansions in grouped form and selects minimum-cost solutions efficiently for each DP state. Figure 4 is identified as a VRP implementation example, while the surrounding procedure describes the analogous TSP expansion process.
- A.2.1 Travelling Salesman Problem: Feasible TSP expansions are represented in a B×n boolean matrix, with columns corresponding to possible next nodes.An expansion is feasible when its node is unvisited and adjacent to the current node.
- A.2.1 Travelling Salesman Problem: The figure caption labels Figure 4 as the implementation of DPDP for VRP rather than TSP.The supplied figure reference does not provide additional TSP-specific visual details.
- A.2.1 Travelling Salesman Problem: Sequentially locating positive matrix entries groups expansions by action and parent set of visited nodes, corresponding to DP states.The grouped representation exposes consecutive segments for each state.
- A.2.1 Travelling Salesman Problem: The minimum-cost solution can then be found independently within each grouped DP-state segment.The implementation uses a scatter operation for these segment-wise minima.
A.2.2 Vehicle Routing Problem
The VRP implementation handles dominance across cost and remaining capacity while supporting direct and via-depot actions. It first preserves the best via-depot expansion, then filters and ranks direct expansions before retaining the beam.
- A.2.2 Vehicle Routing Problem: VRP dominance has two dimensions—cost and remaining capacity—and considers 2n actions: direct moves and moves via the depot.This requires a two-stage dominance check.
- A.2.2 Vehicle Routing Problem: For each DP state, the algorithm first finds the single non-dominated via-depot expansion.Returning to the depot resets remaining capacity, so via-depot expansions share the same remaining capacity.
- A.2.2 Vehicle Routing Problem: Direct expansions with cost at least as high as the via-depot expansion are removed because they have higher cost and lower remaining capacity.The remaining direct expansions are sorted by cost within each DP state.
- A.2.2 Vehicle Routing Problem: TSPTW uses analogous two-dimensional dominance over cost and time, replacing remaining capacity with time to be minimized.The implementation can represent time by multiplying it by −1 so the VRP-style maximization logic can be reused.
- A.2.2 Vehicle Routing Problem: The implementation can generate candidate non-dominated expansions or stream them while retaining the top B with a priority queue.The streaming approach also enables score-bound pruning before dominance checks.
A.4 Performance improvements
The implementation discussion describes directional edge representations in the neural model and notes that several sorting, priority-queue, and batching choices limit current speed. Separate parameters allow direction-specific predictions.
- A.4 Performance improvements: Current speed is constrained by slow lexicographic sorting, inefficient large-k top-k selection, Python multiprocessing overhead, and the absence of a batched implementation.The authors state that batching would provide a significant speedup.
- A.4 Performance improvements: The scoring-function bound can slightly change results when it is inconsistent with the dominance rules.A better-scoring solution may be removed before dominance checking in that case.
- A.4 Performance improvements: The edge-embedding update uses trainable parameters, including W^l_3, W^l_4, and W^l_5.The supplied equation fragments identify an edge-embedding update but do not provide its complete expression.
- A.4 Performance improvements: Sharing W^l_4 and W^l_5 makes opposite edge embeddings equal across layers under the stated initialization.The implementation instead separates W^l_5 so the model can represent (i,j) and (j,i) differently.
- A.4 Performance improvements: Training labels are directed for directed solutions, while undirected TSP and VRP edges receive label 1 in both directions.This label design matches the model’s ability to distinguish edge directions.
B.2 Dataset generation
The TSPTW data-generation discussion contrasts easy instances with harder datasets created by increasing time-window overlap and tightening schedules. Training data were generated with a large-beam heuristic DP procedure that often found optimal solutions.
- B.2 Dataset generation: Instances from [6] were all solved optimally with a beam size around 10 under the described DP formulation.The authors attribute this to little time-window overlap and consequently few feasible actions.
- B.2 Dataset generation: The large time window dataset samples windows around no-wait arrival times, producing tighter schedules with more overlap than the [6] procedure.This modification makes the data more similar to.
- B.2 Dataset generation: Training data were generated using a cost-heat-plus-potential heuristic with a beam size of 1M.This procedure often resulted in optimal solutions.
- B.2 Dataset generation: Time-window overlap determines the branching factor and therefore contributes to TSPTW difficulty.With disjoint windows, only one feasible solution exists.
- B.2 Dataset generation: For 100 customers on a 100×100 grid, the empirically observed makespan including waiting is around 5000.This value is provided as a schedule-duration reference for the data-generation setting.