Solution Techniques

Solution Techniques for VRP

Here, the most commonly used techniques for solving Vehicle Routing Problems are listed. Nearly all of them are heuristics and metaheuristics, because no exact algorithm can be guaranteed to find optimal tours within reasonable computing time when the number of cities is large. This is due to the NP-hardness of the problem. Below you will find a classification of the solution techniques we have considered.

Exact Approaches

As the name suggests, these approaches explore the solution space exhaustively, with the help of bounding techniques, until one of the best solutions is reached. This family also includes branch and cut methods.

Branch and Bound

Divide-and-conquer over the solution space, using relaxations to compute lower bounds. Fisher's K-tree based algorithm (1994) solves instances with up to about 100 nodes.

K-Trees

The VRP modeled as a minimum degree-constrained K-tree: a set of n + K edges spanning the graph, with degree 2K on the depot and side constraints.

Lagrangian Relaxation

Complicating constraints are moved into the objective function with iteratively adjusted multipliers, yielding easier subproblems and tight bounds.

Constraint Programming

Problems are expressed with variables, domains and constraints; constraint propagation prunes the search, combined with iterative improvement for routing problems.

Classic Heuristics

Heuristic methods perform a relatively limited exploration of the search space and typically produce good quality solutions within modest computing times. Constructive methods gradually build a feasible solution while keeping an eye on solution cost, but do not contain an improvement phase per se. Two-phase algorithms decompose the problem into its two natural components — the clustering of vertices into feasible routes and the actual route construction — with possible feedback loops between the two stages.

Clarke and Wright Savings

The best-known VRP heuristic (1964): start from single-customer routes and repeatedly merge the route pair yielding the largest feasible distance saving, in parallel or sequential form.

Matching-Based Savings

A refinement of the savings algorithm in which merge savings come from optimal TSP tour lengths and merges are selected by solving a matching problem.

Multi-Route Improvement Heuristics

Upgrade a feasible solution through edge or vertex exchanges involving several routes at a time: Thompson and Psaraftis (1993), Van Breedam (1994) and Kinderwater and Savelsbergh (1997).

Cluster-First, Route-Second

Cluster the vertices into feasible groups, then build a vehicle route on each cluster: Fisher and Jaikumar (1981), the Petal algorithm, the Sweep algorithm and Taillard (1993).

Route-First, Cluster-Second

Construct a giant TSP tour disregarding side constraints, then decompose it into feasible vehicle routes via a shortest path problem on an acyclic graph.

Metaheuristics

In metaheuristics, the emphasis is on performing a deep exploration of the most promising regions of the solution space. The quality of solutions produced by these methods is much higher than that obtained by classical heuristics.

Simulated Annealing

A stochastic relaxation technique analogous to the annealing of solids: worsening moves are accepted with a probability controlled by a cooling schedule.

Deterministic Annealing

Similar to simulated annealing, but with a deterministic acceptance rule: threshold accepting and record-to-record travel.

Tabu Search

Move at each iteration to the best neighbor solution while recently explored attributes are declared tabu; includes granular tabu and the adaptive memory procedure.

Genetic Algorithms

A population of encoded solutions evolves through selection, recombination and mutation, employing the mechanics of natural selection and genetics.

Ant Colony Systems

Inspired by real ant colonies foraging for food: artificial ants lay pheromone trails that bias the search toward the most promising paths.

Ant Algorithms for the VRP

The ant system of Bullnheimer et al. (1997) for the CVRP, and the MACS-VRPTW multiple ant colony system of Gambardella, Taillard and Agazzi (1999).

Machine Learning & Deep Learning

In recent years, machine learning — especially deep learning and reinforcement learning — has emerged as a new paradigm for tackling routing problems. Instead of hand-crafted search rules, these methods learn construction or improvement policies from data, and can generalize to new instances. More recently, large language models (LLMs) have been explored for modeling and solving VRPs.

Neural Construction (Pointer & Attention)

Sequence-to-sequence pointer networks and attention/Transformer models that build a route node by node: Bello et al. (2017), Nazari et al. (2018) and Kool et al. (2019).

Learning to Improve

Learned local search and neural large neighborhood search: deep policies pick which destroy/repair or move operators to apply, e.g. Hottung & Tierney (2020).

Deep Reinforcement Learning

RL agents trained with policy gradients or actor–critic methods to construct or improve routes, optimizing solution quality directly as the reward signal.

Large Language Models

LLMs used to model problems, generate heuristics/code (e.g. FunSearch-style approaches) and, more recently, as solvers or reasoning assistants for routing tasks.

Techniques for Electric & Green VRP

The Electric VRP and other green variants require techniques that handle energy constraints and recharging decisions in addition to routing. The most common approaches:

Exact methods

Branch-and-cut and branch-and-price on energy-aware formulations; feasible for small/medium E-VRPTW instances, often with partial-recharge modeling.

Metaheuristics with recharging

Adaptive Large Neighborhood Search, Hybrid Genetic Search and Variable Neighborhood Search extended with station-insertion and battery-feasibility repair operators.

Construction + station insertion

Classic savings or cluster-first heuristics followed by greedy insertion of charging stops to restore energy feasibility.

Machine learning for green routing

Learned policies for energy-aware routing, charge scheduling and range prediction; see the ML section for the general framework.