PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning for Solving the Vehicle Routing Problem

Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V. Snyder, Martin Takáč

arXiv:1802.04240v2cs.AIcs.LGstat.ML

TL;DR

The Vehicle Routing Problem requires fast, reliable solutions despite its computational difficulty. This paper trains a reinforcement-learning policy that generates feasible routes for instances from a given distribution, outperforming classical heuristics and OR-Tools on medium-sized capacitated VRP instances with comparable computation time after training.

  • Problem

    The VRP remains computationally difficult, and providing fast, reliable solutions is still challenging despite extensive exact and heuristic research.

  • Method

    The framework trains a stochastic policy by policy gradients to generate feasible VRP action sequences using reward signals and feasibility verification.

  • Results

    In VRP instances with 50 and 100 customers, the method provides shorter tours than OR-Tools in roughly 61% of instances.

  • Takeaways & Limitations

    Once trained, the framework can solve new instances from the training distribution without retraining and with competitive solution time.

  • Takeaways & Limitations

    The approach is scoped to instances sampled from a training distribution, while prior pointer-network methods are limited by VRP's time-varying system representation.

Abstract

from arXiv · show

We present an end-to-end framework for solving the Vehicle Routing Problem (VRP) using reinforcement learning. In this approach, we train a single model that finds near-optimal solutions for problem instances sampled from a given distribution, only by observing the reward signals and following feasibility rules. Our model represents a parameterized stochastic policy, and by applying a policy gradient algorithm to optimize its parameters, the trained model produces the solution as a sequence of consecutive actions in real time, without the need to re-train for every new problem instance. On capacitated VRP, our approach outperforms classical heuristics and Google's OR-Tools on medium-sized instances in solution quality with comparable computation time (after training). We demonstrate how our approach can handle problems with split delivery and explore the effect of such deliveries on the solution quality. Our proposed framework can be applied to other variants of the VRP such as the stochastic VRP, and has the potential to be applied more generally to combinatorial optimization problems.

1 Introduction

The paper presents a reinforcement-learning framework that learns near-optimal VRP solution policies from rewards and feasibility signals, generalizing across instances sampled from a training distribution. Experiments report strong performance against classical heuristics and OR-Tools without retraining per instance.

  • Problem: VRP is computationally difficult, and obtaining fast, reliable solutions remains challenging despite many exact and heuristic algorithms.The problem involves routing vehicles to serve customer nodes while satisfying capacity and return constraints.
  • Approach: The framework formulates VRP as a Markov Decision Process, treating solutions as decision sequences whose desirable outputs are reinforced.A parameterized policy increases the probability of decoding near-optimal sequences.
  • Generalization: A single trained policy solves new VRP instances from the same node, capacity, location, and demand distributions without retraining.The policy works immediately when new instances match the training distribution and problem dimensions.
  • Learning signal: Learning requires only reward calculation for generated solutions and verification that their action sequences are feasible.The method can learn even when the solver does not know how to construct solutions, provided solution costs and feasibility can be evaluated.
  • Results: Roughly 61% of VRP instances with 50 and 100 customers receive shorter tours than with the OR-Tools VRP engine.The experiments also report significantly better performance than well-known classical heuristics and relatively near-optimal worst results.

2 Background

The background reviews sequence-to-sequence architectures and neural combinatorial optimization methods related to the proposed VRP model. It highlights encoder–decoder sequence processing, Pointer Networks with reinforcement learning, and limitations of graph-based approaches for VRP.

  • Sequence-to-Sequence Models: Sequence-to-sequence models map one sequence to another using an encoder and decoder, with the encoder producing a fixed-size vector or sequence of vectors for decoding.The architecture is widely studied in neural machine translation and generally consists of two RNN networks.
  • Sequence-to-Sequence Models: In the vanilla architecture, the source sequence is encoded once and the entire output is generated from the encoder’s final hidden state.Extensions such as Bahdanau et al. use source information more extensively during decoding.
  • Neural Combinatorial Optimization: Pointer Networks adapt sequence-to-sequence models for combinatorial optimization and remain applicable across varying encoder-sequence lengths.They were introduced as an early neural approach to combinatorial optimization.
  • Neural Combinatorial Optimization: Bello et al. use reinforcement learning to optimize a Pointer Network policy, demonstrating effectiveness on problems including the traveling-salesperson and knapsack problems.Their framework is described as both effective and general across these classical combinatorial optimization tasks.
  • Neural Combinatorial Optimization: Dai et al. combine graph embeddings with deep Q-learning for graph optimization, but their model does not directly apply to VRP because nodes such as depots may be revisited.VRP can be represented as a graph with weighted nodes and edges, yet repeated visits create a mismatch with their proposed model.

3 The Model

The model represents combinatorial optimization states with shared embeddings and uses an RNN decoder plus attention to generate feasible action sequences, while remaining invariant to input order. It is trained with policy-gradient methods that optimize a parameterized stochastic policy.

  • 3.1 Problem Representation: The framework models each input as static and dynamic features, updates the state across decoding steps, and selects available inputs until a problem-specific feasibility condition is met.For the VRP, customer locations are static, remaining demands are dynamic, and decoding terminates when no demand remains; vehicle returns can make the output sequence longer than the input set.
  • 3.1 Problem Representation: The decoder starts from an arbitrary input and recursively points to an available input at each step, producing a sequence whose length may differ from the number of inputs.The sequence continues until termination, with repeated depot visits providing one reason its length can exceed the input length.
  • 3.2 Model Architecture: Shared input embeddings and an RNN decoder replace the RNN encoder, avoiding full-network updates when dynamic elements change and enforcing invariance to input ordering.This design targets problems such as VRP, where customer locations and demands form an unordered input set and dynamic updates complicate encoding and back-propagation.
  • 3.3 Attention Mechanism: At each decoder step, glimpse-based context attention computes relevance weights over inputs, combines the resulting context with embedded inputs, and applies softmax to obtain next-action probabilities.The attention mechanism uses the decoder RNN memory state and a variable-length alignment vector to identify information relevant to the next decision.
  • 3.4 Training: Training parameterizes a stochastic policy π with θ and uses policy-gradient estimates of expected-return gradients to iteratively improve the policy.The method comprises an actor that predicts the next-action distribution and a critic network.

4 Computational Experiment

The experiments evaluate reinforcement-learning decoders for capacitated VRP instances sampled from a fixed random distribution, comparing them with classical heuristics and OR-Tools. Beam search improves solution quality, while the framework achieves strong near-optimality on small instances and favorable scaling with problem size.

  • Experimental setup: Instances use customer and depot locations sampled in [0, 1]×[0, 1], with demands uniformly drawn from {1, .., 9}.The experiments assume a fixed distribution, although demand values could also come from other distributions.
  • Decoding methods: Beam search improves solution quality with only a slight increase in computation time compared with greedy decoding.Beam search retains the most probable paths and selects the one with minimum tour length.
  • Experimental setup: The study compares RL greedy and beam-search decoders with Clarke-Wright, Sweep, and Google’s OR-Tools on 1000 instances per problem size.Tests cover multiple problem sizes and vehicle capacities.
  • Solution quality: 95% of VRP10 instances and 13% of VRP20 instances are at most 10% away from optimality using beam width 10.For VRP10 and VRP20, optimal solutions are obtained from a mixed integer formulation, enabling direct optimality-gap comparisons.
  • Solution quality: Classical heuristics are outperformed by the proposed algorithms on VRP50 and VRP100 according to pairwise winning rates.Optimal objective values are computationally unaffordable for these larger instances, so comparisons use the percentage of shorter tours.
  • Computational scaling: RL solution-time ratios remain almost unchanged across decoders, whereas Clarke-Wright and Sweep runtimes increase faster than linearly with node count.This scaling behavior motivates applying the framework to more general combinatorial problems.

5 Discussion and Conclusion

The method requires only feasibility verification and reward signals, then reuses a trained model on new problems from the training distribution without retraining. It scales with problem size, achieves competitive solution time, avoids distance-matrix calculation, and may extend beyond VRP.

  • Future research: The architecture may be applied to other combinatorial optimization problems, including bin-packing, job-shop, and flow-shop.Applying the method beyond VRP is identified as future research.
  • Method requirements: The method needs only a verifier for feasible solutions and a reward signal indicating policy performance.This makes the framework appealing for learning-based optimization.
  • Reuse after training: Once trained, the model can solve multiple new problems from the training distribution without retraining.Reuse is conditional on new problems being generated from the training distribution.
  • Performance and scalability: The method scales with increasing problem size, delivers superior performance with competitive solution time, and avoids computationally cumbersome distance-matrix calculation.The distance-matrix advantage is especially relevant to dynamically changing VRPs.

A Our Model versus Pointer Network … B.4 Optimal Solution

The paper evaluates its learned routing framework on TSP instances against a pointer-network implementation and optimal tours, then describes heuristic, OR-Tools, and exact VRP benchmarks. These benchmarks include randomized Clarke-Wright and sweep procedures, adjusted OR-Tools, and a mixed-integer Gurobi formulation for small-instance optima.

  • A Our Model versus Pointer Network: The TSP test bed compares the proposed framework with Bello et al.’s model on random instances containing 20, 50, and 100 nodes.For each problem size, training uses 10^6 TSP instances over 20 epochs.
  • A Our Model versus Pointer Network: Table 1 reports average tour lengths from the proposed architecture, Bello et al.’s greedy decoder, and optimal tours over 1000 instances.At each decoding step, the greedy decoder selects the city with highest probability.
  • B Capacitated VRP Baselines: The VRP benchmark suite includes two established heuristics, Google’s optimization tools, and optimal solutions for small instances to measure distance from optimality.The baselines are presented as comparison methods for the paper’s VRP experiments.
  • B.1 Clarke-Wright Savings Heuristic: The randomized Clarke-Wright heuristic starts with one route per customer and iteratively merges routes using savings while respecting feasibility conditions.Feasible mergers require different routes, depot adjacency for both nodes, and combined demand within vehicle capacity.
  • B.1 Clarke-Wright Savings Heuristic: Randomization selects among the R best feasible mergers, repeats each choice M times, and returns the shortest resulting route.When M = R = 1, the method is equivalent to the original Clarke-Wright savings heuristic.
  • B.2 Sweep Heuristic: The sweep heuristic rotates an arc from the depot to cluster nodes without exceeding vehicle capacity, solves a TSP per cluster, and combines the tours.The experiments use dynamic programming to find each cluster’s optimal TSP tour.
  • B.3 Google’s OR-Tools: OR-Tools supplies a VRP baseline combining construction heuristics and metaheuristics, with adjustments required because its default solver does not exactly match the studied VRP.Implemented methods include Clarke-Wright, Sweep, Christofides, Guided Local Search, Tabu Search, and Simulated Annealing.
  • B.4 Optimal Solution: Optimal VRP tours are obtained with a mixed-integer formulation and Gurobi, initially relaxing capacity constraints to derive a lower bound before adding violated capacities as lazy constraints.The formulation addresses VRP’s exponential number of constraints for small problems.

C Extended Results of the VRP Experiment

This section provides detailed VRP results by comparing the model with baselines, illustrating generated solutions, and examining extensions to split deliveries and stochastic VRPs.

  • Extended VRP results: The section compares the proposed model with baselines and illustrates the solutions it generates for the VRP.These results provide a more detailed view of the VRP experiment.
  • Split deliveries: Split deliveries are incorporated as an optional mechanism to further improve solution quality.The section demonstrates the model’s flexibility to include split deliveries.
  • Stochastic VRPs: An example illustrates that the framework can be applied to more challenging VRPs with stochastic elements.This extends the demonstrated scope beyond the standard VRP setting.

C.1 Implementation Details

The implementation embeds static and dynamic VRP inputs before decoding with an LSTM-based actor and attention-equipped critic. Training uses REINFORCE with Xavier initialization and requires substantial computation on a single K80 GPU.

  • Embedding: The embedding uses 1-dimensional convolutions with input width equal to input length, D filters, and input channels equal to the number of elements in x.Training without an embedding layer consistently produces inferior solutions.
  • Network architecture: A single LSTM decoder layer has state size 128, while customer locations and dynamic demand and remaining-load features are embedded into 128-dimensional vectors.The dynamic embeddings are used in the attention layer.
  • Network architecture: The critic computes a probability-weighted sum of embedded inputs, then applies ReLU and linear hidden layers, with actor and critic parameters initialized using Xavier initialization.Both networks are trained with the REINFORCE algorithm.
  • Training cost: 35 seconds per 100 training steps and 13.5 hours for 20 epochs are required for VRP instances with 20 customer nodes on a single K80 GPU.The implementation is stated to be publicly available in TensorFlow.

C.2 Flexibility to VRPs with Split Demands · C.3 Summary of Comparison with Baselines

The framework extends classical VRP to split deliveries by modifying the masking scheme, allowing customers’ demands to be satisfied across multiple subtours. Across tested VRPs, its solutions outperform heuristic algorithms and OR-Tools, with beam search improving results further.

  • C.2 Flexibility to VRPs with Split Demands: Classical VRP requires each customer to be visited exactly once, whereas split deliveries relax this constraint to allow potential savings.
  • C.2 Flexibility to VRPs with Split Demands: The split-delivery extension is implemented by omitting masking condition (iii) while retaining the same model.
  • C.2 Flexibility to VRPs with Split Demands: The relaxed method is labeled RL-SD, while other heuristics are evaluated only on the original non-relaxed problem.
  • C.2 Flexibility to VRPs with Split Demands: The reported “optimality” gap uses the optimal objective value of the non-relaxed problem, although the relaxed problem has a lower optimum.
  • C.3 Summary of Comparison with Baselines: Table 2 reports average tour lengths, tour-length standard deviations, and average solution times over a test set of size 1000.
  • C.3 Summary of Comparison with Baselines: The method’s average total solution lengths using various decoders outperform the heuristic algorithms and OR-Tools.
  • C.3 Summary of Comparison with Baselines: The beam search decoder significantly improves the method’s results compared with other decoder choices.

C.4 Sample VRP Solutions · C.5 Attention Mechanism Visualization

The paper visualizes decoded VRP solutions from greedy and beam-search policies, showing effective but sometimes suboptimal routes. It also probes the attention mechanism by relocating one customer and observing changes in the selected action.

  • C.4 Sample VRP Solutions: The illustrated routes are not always optimal, including a self-crossing route in one VRP instance.The paper notes that self-crossing is never optimal in Euclidean VRP instances.
  • C.4 Sample VRP Solutions: Another sample exhibits suboptimality introduced to make the total distance shorter.This provides a second example of a decoded route that is not optimal.
  • C.4 Sample VRP Solutions: Tables 3 and 4 report greedy and beam-search solutions for two sample VRP10 instances with vehicle capacity 20.Each instance contains 10 customers indexed 0–9 and a depot indexed 10.
  • C.4 Sample VRP Solutions: The tables compare tours produced by greedy decoding with results obtained as beam width increases.The passages identify the customer demands, locations, depot location, and decoder-generated tours as the table contents.
  • C.4 Sample VRP Solutions: Figure 6 shows VRP20 and VRP50 solutions decoded by greedy and beam-search policies.Greedy decoding appears in the top row, while beam search appears in the bottom row; node labels indicate demand values.
  • C.5 Attention Mechanism Visualization: The attention visualization relocates customer node 0 across different coordinates and records how the selected action changes.For a VRP10 instance, node 0 is assigned coordinates 0.1 × (i, j) for i, j ∈ {1, · · ·, 9}.
  • C.5 Attention Mechanism Visualization: Figure 7 visualizes attention during the initial decoding step for the relocated-node VRP10 experiment.The figure includes the case where node 0 is at [0.1,0.1], represented by a small square in the bottom left.

C.6 Experiment on Stochastic VRP

The experiment evaluates the framework on a stochastic VRP with jointly uncertain customer locations and demands. Using A3C and dynamic state representations, the learned policy outperforms the tested heuristic strategies on average satisfied demand.

  • Experiment setup: The SVRP experiment jointly randomizes customer locations and demands, requiring schedules to adapt online to different realizations.Customer locations are uniform on the unit square, demands are discrete in {1, · · ·, 9}, and demand expires after 5 time units.
  • Experiment setup: The system uses a 100-time-unit horizon, vehicle speed 0.1 per time unit, and depot position [0.5, 0.5].The vehicle must satisfy as much demand as possible while customers cancel unanswered demand after 5 time units.
  • Training method: A3C with one-step reward accumulation replaces REINFORCE because the stochastic VRP produces long trajectories.The network and hyper-parameters remain the same as in previous experiments.
  • State representation: At each step, the network considers customers with positive demand, the depot, and the vehicle’s current location instead of using masking.Customer time-in-system is also added as a dynamic element to the attention mechanism, and the current-location option allows stopping when necessary.
  • Results: Over 100 test instances, A3C outperforms Random, Largest-Demand, and Max-Reachable in average satisfied demand and its share of total demand.Max-Reachable uses customer abandonment information, whereas A3C does not use information about problem structure.

D Training Policy Gradient Methods

Training samples problem instances from ΦM for both learning and inference. REINFORCE trains actor–critic networks for VRP, while A3C trains the SVRP policy with parallel agents and periodic central-network updates.

  • Training setup: Training and inference both use problem instances sampled from distribution ΦM.The same distribution generates training instances and test examples.
  • REINFORCE for VRP: REINFORCE trains actor and critic networks by sampling N problems, generating feasible policy sequences, computing rewards, and updating their weights.The actor uses weights θ and the critic uses weights φ; critic updates reduce the difference between observed and expected rollout rewards.
  • A3C for SVRP: A3C trains the SVRP policy using a central actor–critic network and N parallel thread-specific actor–critic networks.Each thread samples an instance from ΦM and runs an episode before contributing updates to the central networks.
Loading 1802.04240v2…