Periodic Capacitated Vehicle Routing Problem

Combinatorial Optimization Research 2025

Solving the
PCVRP Horizon

The Periodic Capacitated Vehicle Routing Problem has shifted from Branch-and-Cut exact methods to Hybrid Genetic Search and emerging Deep Graph Learning.

Exact Methods

Branch-and-Cut-and-Price

Optimality Guaranteed
Limited to N < 100
Computation: Hours/Days

Metaheuristics (Current King)

Hybrid Genetic Search (HGS)

Industry Standard (Vidal et al.)
Population Diversity Management
Scales to N > 10,000

Neural / Learning

Deep Reinforcement Learning

Inference in Milliseconds
POMO / Attention Models
Generalization Issues

The Dominance of HGS

While Neural approaches gain hype, Hybrid Genetic Search (HGS) remains the champion for solution quality in PCVRP. It decouples the problem into two phases:

1. Pattern Assignment

Selecting which days a customer is visited (e.g., M-W-F vs T-Th-S). Handled via crossover operators.

2. Split Algorithm

Transforms a Giant Tour (permutation) into feasible routes optimally in $O(1)$ amortized time.

Convergence Profile (Gap to Best Known)

Instance: Cordeau p10

HGS approaches 0.0% gap slower than Neural methods start, but achieves higher final precision.

Alternative Architectures

⚙️

ALNS

Adaptive Large Neighborhood Search

Destroys and repairs solutions. The "Swiss Army Knife" of VRP.

Pros Handles complex side-constraints (time windows, driver breaks) easily.

Cons Many hyperparameters to tune. Slower than HGS on pure PCVRP.

🧠

Neural VRP (POMO)

Deep Reinforcement Learning

Encoder-Decoder Transformers trained via REINFORCE to construct routes node-by-node.

Pros Instant inference ($<1s$). No retraining needed for similar instances.

Cons Training takes days. Hard to enforce strict hard constraints (capacity/time).

Algorithm Selection Strategy

The choice of algorithm depends on the operational horizon. For Strategic Planning (where compute time is irrelevant), HGS or Branch-and-Cut is preferred. For Real-Time Dispatch (dynamic requests), Neural approaches are gaining traction.

1

Vidal's Unified HGS

Current record holder on Cordeau benchmarks. Uses "broken pairs" distance for diversity.
2

N2S (Neural Neighborhood Search)

A hybrid that uses Neural Networks to *guide* the local search operators of a metaheuristic.