Vehicle Routing Problem: Nearest-Neighbor + 2-opt Simulator

Fleet

Vehicle capacity 40

Max vehicles 6

Customers

Click empty canvas to add a customer at that point. Click a customer dot to remove it. Drag the depot (yellow square) to move it.

Solver

Nearest-neighbor construction, then 2-opt improvement, one swap per animation frame.

Route length

Nearest-neighbor

–

After 2-opt

–

Improvement

–

2-opt swaps applied

–

Vehicles used

–

Customers

–

How it works

This is a real solver for the Capacitated Vehicle Routing Problem, not an animation of one. Construction: starting from the depot, each route repeatedly appends the nearest unvisited customer whose demand still fits the vehicle's remaining capacity (nearest-neighbor heuristic); when no customer fits, the route closes and a new vehicle starts, until every customer is assigned or the vehicle limit is hit. Improvement: 2-opt scans every pair of edges in every route and tests reversing the path segment between them — if the two new edges are shorter in total real Euclidean distance than the two they replace, the reversal is kept; otherwise it is discarded. This repeats, one candidate swap per frame so you can watch it converge, until a full pass finds no improving swap (a local optimum).

gain = d(a,b) + d(c,d) − d(a,c) − d(b,d)
if gain > 0: reverse segment b..c   // real 2-opt move
route valid only while Σ demand ≤ capacity

Vehicle capacity — total demand a single vehicle may carry; lower it and more, shorter routes are needed to serve the same customers.
Max vehicles — a hard cap on fleet size; if capacity and count together can't cover all demand, the excess customers stay unrouted (shown in red).
2-opt swaps applied — count of accepted edge-reversal moves; each one strictly reduced total route distance, so this number only rises while total distance only falls.

Real-world relevance: nearest-neighbor + 2-opt is the classic fast, good-enough baseline behind real delivery, parcel and field-service routing software — it never reaches the true optimum on large instances, but it consistently removes the "obviously crossing" routes a naive greedy assignment leaves behind, at a fraction of the cost of exact methods.

Click canvas: add customer · click dot: remove · drag depot to move

Depot Route 1 Route 2 Route 3+ Unrouted (capacity exceeded)