The Vehicle Routing Problem

Every morning a depot fills its trucks and sends them out. A hundred packages, six drivers, one question: who delivers what, and in which order? Get it wrong and trucks crisscross the city burning fuel and overtime. Get it right and the same deliveries finish hours earlier.

This is the Vehicle Routing Problem (VRP). You have one depot, a fleet of vehicles, and a set of customers to serve. Each truck leaves the depot, visits some customers, and returns. The goal is to serve everyone at the least total cost — usually total distance or time — often while respecting limits like how much each truck can carry.

It sounds like a scheduling chore. It is, in fact, one of the most studied hard problems in all of optimization, and shaving even a few percent off the answer is worth billions to the companies that move the world's goods.

Below is a depot (the square) and eight delivery stops. Two trucks must cover them all. Click a stop to send it to the other truck, and each truck instantly re-orders its own stops with a quick nearest-neighbor tour. Watch the total length at the bottom.

<p class="hint">{{hint}}</p>
<svg id="map" viewBox="0 0 320 240" role="img" aria-label="{{map_aria}}"></svg>
<div class="legend">
  <span><i class="sw a"></i>{{truck_a}} <b id="lenA">0</b></span>
  <span><i class="sw b"></i>{{truck_b}} <b id="lenB">0</b></span>
  <span class="tot">{{total_label}} <b id="total">0</b></span>
</div>
<div class="btns">
  <button id="balance" type="button">{{btn_balance}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#map { width: 100%; max-width: 460px; height: auto; background: #f5f7fa;
       border: 1px solid #d7dee6; border-radius: 10px; display: block; }
.stop { cursor: pointer; }
.stop circle { transition: r .1s; }
.stop:hover circle { r: 9; }
.legend { display: flex; gap: 1.1rem; flex-wrap: wrap; align-items: center;
          font-size: .92rem; margin: .6rem 0; }
.legend b { font-variant-numeric: tabular-nums; }
.legend .tot { font-weight: 600; }
.sw { display: inline-block; width: 14px; height: 4px; border-radius: 2px; margin-right: .4rem; vertical-align: middle; }
.sw.a { background: #2563eb; } .sw.b { background: #e8590c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; color: #0a7d33; }

// Code not found

Try to make the total as small as you can, then press Auto-balance to let the computer search. Notice the tension: each truck wants a short, tight loop, but the two loops must together cover every stop. With just eight stops there are already $2^{8}$ = 256 ways to split them between two trucks — and real fleets have hundreds of stops and many trucks, where the number of splits is astronomically larger.

How hard is the Vehicle Routing Problem, really?

• It contains TSP. Give VRP a single truck with unlimited capacity and the problem collapses into the Traveling Salesman Problem: find one shortest tour through every stop. Because that special case is already NP-hard, VRP is NP-hard too — at least as hard, and usually harder.
• Capacity makes it worse. The standard industrial version, the Capacitated VRP (CVRP), adds a load limit per truck, so you must simultaneously partition the stops into feasible groups and route each group. Two hard problems welded together.
• Brute force is hopeless. Splitting n stops among k trucks and then ordering each route blows up factorially. Exact solvers using branch-and-cut and column generation can prove optimality for instances up to a few hundred customers, but they can grind for hours and don't scale to a nationwide fleet.
• Status: NP-hard, not undecidable, not a Millennium problem. There is no known efficient (polynomial-time) algorithm, and finding one would settle P vs NP. So in practice, industry abandons "perfect" and runs heuristics and metaheuristics — savings algorithms, local search, large-neighborhood search — that return very good routes fast, without any guarantee they are the absolute best.

That is the quiet truth behind your delivery app: the route you got was almost certainly not provably optimal. It was good enough, found fast enough, because optimal is out of reach.

"Send a fleet out and bring it back cheaply" describes a startling share of the physical economy:

• Parcel and grocery delivery: the last mile is the single most expensive leg of shipping, and routing is where it is won or lost.
• Waste collection and street sweeping: garbage trucks are classic capacitated routing, with the dump as a second depot.
• School buses: route students to school under time windows and capacity — a VRP that touches millions of children daily.
• Field service and home health: technicians or nurses visiting clients are vehicles serving customers with time windows.
• Ride-pooling and on-demand transit: matching riders to shared vehicles is dynamic vehicle routing solved in real time.

Because the prize is so large, VRP is one of the most commercially valuable optimization problems on Earth — close cousin to bin packing when capacity dominates, and built on the same intractable core as the Traveling Salesman Problem.

The Vehicle Routing Problem is the Traveling Salesman Problem grown up: not one traveler but a whole fleet, not just an order but also a partition, and capacity limits on top. That extra structure keeps it firmly NP-hard, with no efficient algorithm known and none expected unless P vs NP surprises us all.

And yet the trucks still roll. The lesson of VRP is the lesson of modern optimization: when "best" is unreachable, "demonstrably very good, found fast" is what keeps the world's parcels moving. Every package you receive is a small monument to a hard problem we cannot solve — but have learned to live with brilliantly.