How Cainiao’s VRP Engine Breaks World Records with Adaptive Large Neighborhood Search

Problem Introduction

Vehicle Routing Problem (VRP) is a classic optimization problem in logistics where a fleet of vehicles must serve a set of customers from a depot while minimizing the number of vehicles used and the total travel distance. The decision variables include assigning customers to vehicles and determining the service order for each vehicle.

VRP Variants

CVRP : Capacitated VRP – limits vehicle capacity.

VRPTW : VRP with Time Windows – customers have delivery time windows.

VRPPD : VRP with Pickup and Delivery – vehicles can pick up and deliver in the same route.

MDVRP : Multi‑Depot VRP – multiple depots are available.

OVRP : Open VRP – vehicles do not need to return to the depot.

VRPB : VRP with Backhauls – vehicles return to pick up goods after deliveries.

Classic Solving Algorithms

VRP is NP‑hard. Exact methods such as branch‑and‑bound, branch‑and‑cut, and branch‑cut‑and‑price guarantee optimality but become impractical for instances larger than about 200 nodes. Consequently, most research focuses on heuristic and meta‑heuristic approaches. Classic heuristics include the Clarke‑Wright savings algorithm, while meta‑heuristics such as simulated annealing, tabu search, genetic algorithms, ant colony optimization, variable neighbourhood search, and adaptive large neighbourhood search (ALNS) have shown strong performance.

Cainiao VRP Engine Development

Stage 1: Core Algorithm

The team chose Adaptive Large Neighborhood Search (ALNS) as the engine’s core because it is extensible, explores a large solution space, adapts operator selection to problem characteristics, and allows easy integration of new operators.

ALNS Main Process

Construct an initial solution (Initial).

Select Ruin and Insert operators based on their weights.

Apply the Ruin operator to destroy part of the current solution, creating an infeasible solution.

Apply the Insert operator to repair the solution, aiming for feasibility.

Evaluate the new solution with the objective function and decide whether to accept it.

Check termination criteria; if not met, update operator weights and repeat from step 2.

Using this framework, the first version of the VRP engine outperformed popular open‑source solvers such as jsprit.

Stage 2: Enriching the Algorithm Suite

The engine was extended to handle Pickup‑and‑Delivery, Multi‑Trip, and other variant problems, and to support diverse objective functions (e.g., minimizing tiered pricing cost, delivery time) and constraints (vehicle distance, order count, cross‑region limits). New operators were added, including Two‑Opt, Three‑Opt, Cross‑Exchange, Guided Ejection Search (GES), Fast Local Search (FLS), Guided Local Search (GLS), Edge Assembly Crossover (EAX), Branch‑and‑Price‑based LNS, Path‑Relink, and Hybrid Cluster & Heuristics.

Stage 3: Parallelization

To further boost solution quality, three parallel architectures were implemented.

Population Island

Multiple islands run independent evolutionary processes; each island has a master coordinating workers and periodically exchanges knowledge with other islands.

Parallel Memetic

The first phase focuses on reducing the number of vehicles (Delete Route) with parallel workers; the second phase reduces total distance (Reduce Distance) using the intermediate results as initial populations.

Central Pool

Workers submit solutions to a central pool where a manager ranks, filters, and clusters them, then generates new tasks for workers, balancing exploration and exploitation.

Results

Through continuous algorithmic upgrades and engineering improvements, Cainiao’s VRP engine achieved world‑record solutions on the SINTEF benchmark (Solomon and Gehring & Homberger datasets). By April 2019 the team held 48 world records, ranking among the top global research groups.

Conclusion and Outlook

The team will keep strengthening the engine, making it more robust, stable, and user‑friendly, while also offering it externally to enhance logistics efficiency across China.