PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem

Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, Jie Zhang

arXiv:2110.02629v2cs.LGmath.OC

TL;DR

Existing DRL methods mainly address homogeneous CVRP by selecting nodes without explicitly choosing among heterogeneous vehicles. This paper proposes an attention-based DRL policy with separate vehicle and node decoders for HCVRP, and reports strong performance across objectives and instance sizes, with limitations outside its tested setting.

  • Problem

    Existing DRL methods assume homogeneous fleets and omit explicit vehicle selection, limiting their direct fit to HCVRP with heterogeneous vehicle capacities.

  • Method

    An attention-based DRL construction policy uses vehicle and node selection decoders to choose both a vehicle and its next node at each step.

  • Results

    The method outperforms most conventional heuristics, competes with SISR, and generalizes to larger customer sizes and CVRPLib instances.

  • Takeaways & Limitations

    Joint vehicle–node selection provides a DRL approach for heterogeneous fleets under both min-max and min-sum objectives.

  • Takeaways & Limitations

    The method is trained and tested mainly on uniformly distributed customer locations and may perform worse on other VRP types or non-uniform test distributions.

Abstract

from arXiv · show

Existing deep reinforcement learning (DRL) based methods for solving the capacitated vehicle routing problem (CVRP) intrinsically cope with homogeneous vehicle fleet, in which the fleet is assumed as repetitions of a single vehicle. Hence, their key to construct a solution solely lies in the selection of the next node (customer) to visit excluding the selection of vehicle. However, vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed), rendering existing DRL methods less effective. In this paper, we tackle heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by different capacities. We consider both min-max and min-sum objectives for HCVRP, which aim to minimize the longest or total travel time of the vehicle(s) in the fleet. To solve those problems, we propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step. Experimental results based on randomly generated instances show that, with desirable generalization to various problem sizes, our method outperforms the state-of-the-art DRL method and most of the conventional heuristics, and also delivers competitive performance against the state-of-the-art heuristic method, i.e., SISR. Additionally, the results of extended experiments demonstrate that our method is also able to solve CVRPLib instances with satisfactory performance.

I. INTRODUCTION

HCVRP extends CVRP to heterogeneous vehicles and supports both min-max and min-sum travel objectives. Existing DRL methods mainly select nodes for homogeneous fleets, motivating a policy that jointly selects vehicles and nodes.

  • HCVRP models vehicles with different capacities or speeds serving customer demands under capacity constraints.
  • Min-max HCVRP minimizes the longest vehicle travel time, whereas min-sum HCVRP minimizes total fleet travel time.
  • Exact methods can perform well on small instances but may become prohibitively slow as problem size grows.
  • Prior DRL construction methods generally learn to select the next node while assuming a homogeneous fleet.
  • The proposed architecture jointly selects a vehicle and node using contextual information from the heterogeneous fleet and partial routes.

B. Reformulation as RL Form

The HCVRP route-construction process is formulated as a Markov decision process whose state tracks vehicle and node information. Each action selects one vehicle and one customer or depot, while rewards encode either maximum or total travel time.

  • State: The MDP state contains vehicle state and node state, representing route and customer information during construction.
  • State: Vehicle state records each vehicle’s remaining capacity, accumulated travel time, and partial route.
  • Action: At each step, the action selects one vehicle and one customer or depot to visit.
  • Transition: The transition updates vehicle and node states after the selected vehicle visits the selected node.
  • Reward: The MM-HCVRP reward is negative maximum fleet travel time, while the MS-HCVRP reward is negative total fleet travel time.

IV. METHODOLOGY

The methodology uses a deep reinforcement learning policy with attention to construct HCVRP routes under both min-max and min-sum objectives. The policy supports vehicle and node selection at every decision step.

  • The approach learns an attention-based neural policy for solving HCVRP with min-max and min-sum objectives.
  • The policy enables both vehicle selection and node selection during route construction.
  • The training procedure is described for the proposed DRL policy network.

A. Framework of Our Policy Network

The policy network encodes an instance once and repeatedly decodes vehicle–node actions to construct a complete solution. Its two decoders first choose a vehicle and then choose a node for that vehicle.

  • The stochastic policy starts from an empty solution and constructs routes until all customers are served.
  • The network comprises an encoder, a vehicle selection decoder, and a node selection decoder.
  • At each construction step, the selected vehicle and node together form the action.
  • The encoder runs once because the problem instance remains unchanged, while the decoders run repeatedly during route construction.
  • The construction horizon can exceed the number of customers plus depot visits because vehicles may return to the depot for replenishment.

B. Architecture of Our Policy Network

The policy network uses a Transformer-style encoder-decoder architecture to represent heterogeneous CVRP instances and construct routes. Its decoder separately selects a vehicle using fleet and route context, then selects a customer node using vehicle-specific context.

  • Decoder: The vehicle selection decoder uses vehicle features and route features to compute a probability distribution over vehicles.Vehicle features include current vehicle states, while route features summarize existing partial routes across the fleet.
  • Encoder: The Transformer encoder learns relationships between arbitrary sequence elements through self-attention rather than sequence-aligned recurrence.This supports parallelization and feature extraction for sequential route construction.
  • Decoder: The decoder combines vehicle selection and node selection so the policy can choose a vehicle from the heterogeneous fleet before choosing its next customer.The architecture gives every vehicle an opportunity to be selected at each step.
  • Encoder: The encoder embeds customer locations, demands, and vehicle capacities, then applies multi-head attention and feed-forward layers to produce node and graph embeddings.The graph embedding is the mean of the node embeddings and is reused by both decoders.
  • Decoder: After vehicle selection, the node selection decoder uses the selected vehicle's context and encoded node representations to choose a feasible customer.The selected vehicle's remaining capacity and prior location contribute to the node-selection context.

1) Vehicle Feature Embedding:

The vehicle feature embedding represents each vehicle's current state during route construction. It encodes the vehicle's latest location and accumulated travel time before projection into the decoder representation.

  • 1) Vehicle Feature Embedding:: The vehicle feature context captures each vehicle's last node in its partial route and accumulated travel time at the preceding step.These features describe the current state of every vehicle in the fleet.
  • 1) Vehicle Feature Embedding:: A linear projection followed by a 512-dimensional feed-forward layer with ReLU produces the vehicle feature embedding.The projection uses trainable parameters W1 and b1.

2) Route Feature Embedding:

Route feature embedding summarizes the partial routes of all vehicles so the policy can use visited-node information when selecting vehicles and constructing routes. The vehicle decoder combines this route context with vehicle features to produce vehicle-selection probabilities.

  • 2) Route Feature Embedding:: Each vehicle's route feature context is formed from the node embeddings of the nodes in its partial route.This lets the policy learn from previously visited nodes rather than only masking them.
  • 2) Route Feature Embedding:: The route contexts of all vehicles are aggregated by max-pooling and concatenated into a fleet-level route context.The aggregation preserves information from the partial routes of the entire fleet.
  • 2) Route Feature Embedding:: The route feature embedding is combined with the vehicle feature embedding and passed through a softmax to compute vehicle-selection probabilities.The selected vehicle can then be chosen greedily or sampled from the resulting probability vector.
  • 2) Route Feature Embedding:: The node selection decoder outputs probabilities over unserved nodes for the vehicle selected by the vehicle decoder.Previously served nodes are masked to maintain feasibility.
  • 2) Route Feature Embedding:: Its context combines the graph embedding, the selected vehicle's previous node embedding, and its remaining capacity before attention-based node scoring.The context query attends to node embeddings, which serve as keys and values.
  • 2) Route Feature Embedding:: The illustrated action selects both a vehicle and a node, then updates the state for the next construction step.In the example, masked probabilities exclude nodes already present in the tours.

C. Training Algorithm

The training algorithm uses policy gradient reinforcement learning with a baseline to improve the joint vehicle- and node-selection policy. A greedy-rollout baseline is periodically replaced when the current policy significantly outperforms it.

  • C. Training Algorithm: The policy network generates vehicle and node probability vectors and selects an action at each decoding step.The action-selection policy is trained for route construction.
  • C. Training Algorithm: A baseline network estimates expected reward through a greedy rollout using a structure similar to the policy network.The baseline supports policy-gradient training.
  • C. Training Algorithm: The baseline parameters are replaced by the latest policy parameters when a paired t-test indicates significant policy improvement.This update is evaluated on several instances.
  • C. Training Algorithm: Alternating updates of the policy and baseline networks iteratively improve the policy toward higher-quality solutions.The procedure updates both networks during training.

V. COMPUTATIONAL EXPERIMENTS

The experiments evaluate a DRL method for heterogeneous vehicle fleets on min-max and min-sum routing objectives, including CVRPLib extensions. The study uses heuristic baselines and adjusts implementation settings as problem size increases.

  • Experiments evaluate heterogeneous fleets serving customers while minimizing either the longest or total vehicle travel time.
  • The experiments include extended evaluations on benchmark instances from CVRPLib.
  • The authors increase iterations with problem size following the original paper or use fixed iterations where stated.
  • Both min-max and min-sum HCVRP are NP-hard, with exponential theoretical complexity as problem size grows.

A. Experiment Settings for HCVRP

The study generates random HCVRP instances with uniformly sampled locations and discrete customer demands, testing fleets of three or five vehicles with different capacities. Training uses shared hyperparameters and may stop before full convergence when further improvement is negligible.

  • Depot and customer coordinates are sampled uniformly within the unit square, while customer demands are randomly chosen from 1 through 9.
  • Training uses shared hyperparameters across problem sizes and randomly generates 1,280,000 instances per iteration.
  • Training can stop early when additional iterations produce only insignificant performance gains.
  • The experiments use 50 iterations for all problem sizes, although additional iterations may improve performance.

B. Comparison Analysis of HCVRP

The proposed DRL method is compared with exact and heuristic baselines across three- and five-vehicle HCVRP instances. It generally outperforms conventional heuristics, remains competitive with SISR, and offers substantially shorter computation times as problem size grows.

  • Baselines: The comparison includes SISR, VNS, ACO, FA, AM variants, and an exact solver where computationally feasible.
  • Decoding: Sampling improves solution quality over greedy decoding, with Sample1280 and Sample12800 achieving smaller objective values and gaps.
  • Runtime: SISR achieves the lowest objective value and gap, but its computation time grows almost exponentially while DRL(Sample12800) grows almost linearly.
  • Runtime: DRL is at least an order of magnitude faster than conventional methods, especially for large problem sizes.
  • Objective quality: DRL(Sample12800) outperforms VNS, ACO, FA, and AM overall on both MM-HCVRP and MS-HCVRP while remaining competitive with SISR.
  • Time-bounded comparison: Within a 500-second budget, SISR needs longer to catch up as problem size increases, while DRL achieves only slightly inferior objective values with much shorter computation time.

C. Generalization Analysis of HCVRP

The method generalizes across larger HCVRP instances and performs competitively on CVRPLib, while distribution shifts remain a limitation. It outperforms most conventional heuristics and approaches SISR with substantially shorter computation time.

  • Random-instance generalization: Policies trained for smaller customer sizes generalize to larger MM-HCVRP and MS-HCVRP instances, with proximal training sizes performing better than more distant ones.For five vehicles, the learned policies outperform most classical heuristics and AM across all tested cases, although they are slightly inferior to policies trained for the corresponding size.
  • CVRPLib evaluation: The method outperforms most conventional heuristics and is competitive with SISR on CVRPLib, using much shorter computation time.On uniformly distributed instances it tends to outperform VNS, while on non-uniform instances it is slightly inferior; SISR solves CMT11 in 1598 seconds versus 9.0 seconds for the proposed method.
  • Distributional scope: Performance is stronger on uniform than non-uniform test distributions because the training instances use uniform customer locations.The paper identifies this out-of-distribution challenge as outside the study’s scope and leaves it for future work.
  • CVRPLib evaluation: The CVRPLib evaluation adapts ten benchmark instances to the MM-HCVRP and MS-HCVRP settings using their customer locations and demands.The selected instances include both uniform and non-uniform customer-location distributions.
  • Method: The proposed constructive heuristic combines deep reinforcement learning and attention with encoder, vehicle-selection, and node-selection decoders.It selects a vehicle and a node for that vehicle at each construction step.
Loading 2110.02629v2…