A rider leaves the shop with ten parcels, drives across town for the first drop, comes back past the shop for the second, and crosses the same bridge three times before lunch. Nobody planned that. The app just listed orders in the sequence they were placed, and the rider followed the list.
Delivery route optimization fixes that by choosing the order of stops so the total trip is as short as you can reasonably make it. You don’t need a paid API or a research paper to get a useful first version. A simple heuristic, a cleanup pass and a few honest tests will take a small delivery app a long way. This post walks through that start in plain PHP, and then covers when it’s time to hand the problem to a routing API.
In this guide
- What delivery route optimization actually solves
- Step 1: a nearest-neighbour route
- Step 2: clean it up with 2-opt
- Step 3: test it before you trust it
- When to use a routing API instead
- FAQ
What delivery route optimization actually solves
With one vehicle and a list of stops, you’re trying to find the shortest loop that starts at the depot, visits every stop once and comes back. That’s the travelling salesman problem. Add more vehicles, parcel capacity or delivery time windows and it becomes the vehicle routing problem, which is what most real delivery businesses have.
Both get hard fast. The number of possible orders grows faster than any server can check once you pass a dozen or so stops, so nobody looks for the perfect answer in a live app. You look for a good answer quickly. That’s what heuristics are for: rules of thumb that get close to the best route in a fraction of a second.
For an early product that’s usually enough. A rider with 8 to 15 drops a shift mostly needs a sensible order with no obvious backtracking. If you’re still deciding what goes into the first release, my field guide to building an MVP covers how to keep features like this small until real usage tells you more.
Step 1: a nearest-neighbour route
The simplest rule is the one a rider would use without an app: from where you are, go to the closest stop you haven’t visited yet. Repeat until the list is empty, then go home.
Here’s the whole planner. It uses straight-line (great-circle) distance between coordinates, which is fine for a first version and needs no external service. Each Stop is just an id with a latitude and longitude.
final readonly class Stop
{
public function __construct(
public string $id,
public float $lat,
public float $lng,
) {}
}
final class RoutePlanner
{
private const EARTH_RADIUS_KM = 6371.0;
/** Straight-line (great-circle) distance between two stops, in km. */
public static function km(Stop $a, Stop $b): float
{
$dLat = deg2rad($b->lat - $a->lat);
$dLng = deg2rad($b->lng - $a->lng);
$h = sin($dLat / 2) ** 2
+ cos(deg2rad($a->lat)) * cos(deg2rad($b->lat)) * sin($dLng / 2) ** 2;
return 2 * self::EARTH_RADIUS_KM * asin(min(1.0, sqrt($h)));
}
/** Total length of depot -> stops... -> depot. */
public static function length(Stop $depot, array $route): float
{
$total = 0.0;
$prev = $depot;
foreach ($route as $stop) {
$total += self::km($prev, $stop);
$prev = $stop;
}
return $total + self::km($prev, $depot);
}
/** Step 1: always drive to the closest stop you haven't visited yet. */
public static function nearestNeighbour(Stop $depot, array $stops): array
{
$left = array_values($stops);
$route = [];
$current = $depot;
while ($left !== []) {
$bestIndex = 0;
$bestKm = INF;
foreach ($left as $i => $stop) {
$d = self::km($current, $stop);
if ($d < $bestKm) {
$bestKm = $d;
$bestIndex = $i;
}
}
$current = $left[$bestIndex];
$route[] = $current;
array_splice($left, $bestIndex, 1);
}
return $route;
}
/** Step 2: reverse any section of the route that makes it shorter (2-opt), until nothing improves. */Nearest neighbour is fast and easy to explain to a rider, but it has a known weakness. It’s greedy. Early on it grabs whatever is close, and later it’s left with stops scattered across town, so the route often crosses over itself near the end.
Step 2: clean it up with 2-opt
2-opt is the classic fix for those crossings. Take any two legs of the route. If swapping their ends, which means reversing the section between them, makes the trip shorter, keep the change. Keep going until no swap helps.
/** Step 2: reverse any section of the route that makes it shorter (2-opt), until nothing improves. */
public static function twoOpt(Stop $depot, array $route, int $maxPasses = 50): array
{
$path = [$depot, ...$route, $depot];
$n = count($path);
for ($pass = 0; $pass < $maxPasses; $pass++) {
$improved = false;
for ($i = 1; $i < $n - 2; $i++) {
for ($k = $i + 1; $k < $n - 1; $k++) {
$before = self::km($path[$i - 1], $path[$i]) + self::km($path[$k], $path[$k + 1]);
$after = self::km($path[$i - 1], $path[$k]) + self::km($path[$i], $path[$k + 1]);
if ($after + 1e-9 < $before) {
$middle = array_reverse(array_slice($path, $i, $k - $i + 1));
array_splice($path, $i, $k - $i + 1, $middle);
$improved = true;
}
}
}
if (! $improved) {
break;
}
}
return array_slice($path, 1, $n - 2);
}
public static function plan(Stop $depot, array $stops): array
{
return self::twoOpt($depot, self::nearestNeighbour($depot, $stops));
}The $maxPasses limit is there so a large list can’t keep a web request busy for too long. For bigger batches, plan the route in a background job and save the result rather than running it inside the request. The same thinking applies to any heavy work, and my Laravel performance guide and the post on fair background queues per tenant cover how to keep that kind of job from slowing everyone else down.
Step 3: test it before you trust it
Routing bugs are quiet. A route that drops a stop or visits one twice still looks like a route. So the first tests check the boring things: every stop appears exactly once, 2-opt never makes the trip longer, and a deliberately crossed route gets uncrossed.
$greedy = RoutePlanner::nearestNeighbour($depot, $stops);
$planned = RoutePlanner::plan($depot, $stops);
$ids = fn (array $r) => array_map(fn (Stop $s) => $s->id, $r);
$sorted = function (array $r) use ($ids) { $x = $ids($r); sort($x); return $x; };
check($sorted($greedy) === $sorted($stops), 'nearest neighbour visits every stop exactly once');
check($sorted($planned) === $sorted($stops), '2-opt keeps every stop exactly once');
$g = RoutePlanner::length($depot, $greedy);
$p = RoutePlanner::length($depot, $planned);
check($p <= $g + 1e-9, '2-opt route is never longer than the greedy route');
// Four corners of a square: the best tour walks the edges and never crosses.
$sq = new Stop('sq-depot', 0.0, 0.0);
$crossing = [new Stop('1', 0.0, 0.01), new Stop('2', 0.01, 0.0), new Stop('3', 0.01, 0.01)];
$fixed = RoutePlanner::twoOpt($sq, $crossing);
check(RoutePlanner::length($sq, $fixed) < RoutePlanner::length($sq, $crossing), '2-opt removes a crossing on a square');
check(abs(RoutePlanner::km($depot, $depot)) < 1e-12, 'distance from a stop to itself is zero');I ran this on PHP 8.4.27 with plain php route_test.php, no framework and no extra packages, using ten example coordinates I made up for the demo. All five checks passed. On that example the greedy route came out at 16.06 km and the 2-opt route at 14.47 km. That’s one made-up example, not a benchmark, so test on your own stop data before you promise riders anything.
| Route | Order | Straight-line length |
|---|---|---|
| Nearest neighbour | J, A, D, I, F, B, G, C, E, H | 16.06 km |
| Nearest neighbour + 2-opt | J, H, E, C, G, B, F, D, I, A | 14.47 km |
When to use a routing API instead
The planner above measures distance as the crow flies. Riders don’t drive that way. One-way streets, a river with two bridges or a stretch of road that’s jammed every evening can make the shortest-looking route the slowest one. That’s the first sign you’ve outgrown it.
Move to a routing service or a solver when one of these becomes true:
- Road distance and traffic matter. Riders complain the order makes no sense on real roads.
- You have time windows. A customer is only home between 2 and 4, or a shop opens at 10.
- You have more than one vehicle. Splitting stops between riders is a separate problem, and it’s where hand-written heuristics get messy.
- Capacity limits apply. A bike holds less than a van, and some orders are heavy.
For a hosted option, Google’s Route Optimization API handles multiple vehicles, time windows and capacities and returns an ordered plan per vehicle. If you’d rather run the solver on your own servers, Google’s open-source OR-Tools has a well-documented vehicle routing guide that you can feed with a distance matrix from any maps provider.
Either way, keep the simple planner around. It’s a good fallback when the API is down or a quota runs out, and its output gives you a baseline to judge whether the paid route is actually better. If you’re scoping a delivery product with a client and need to decide which of these belongs in phase one, Diligent Creators has a practical piece on scoping an MVP without blowing the budget.
FAQ
What is delivery route optimization?
It’s choosing the order of delivery stops, and on bigger setups which vehicle takes which stops, so the total distance or time is as low as practical. Most apps use heuristics because finding the perfect route takes too long once there are more than a handful of stops.
What’s the difference between the travelling salesman problem and the vehicle routing problem?
The travelling salesman problem has one vehicle visiting every stop once. The vehicle routing problem adds several vehicles and usually limits such as capacity or time windows. A one-rider delivery app starts with the first and grows into the second.
Do I need the Google Maps Routes API to start?
No. A nearest-neighbour route with a 2-opt pass, like the code above, works offline and costs nothing to run. Add a routing API when real road distances, traffic, time windows or several vehicles start to matter.
I’m Shahrukh Akhtar (Shaz3e), CTO & Co-Founder of Diligent Creators Pvt. Ltd., a Technology Executive & Product Builder. I run client delivery and build SaaS products, including EloSync. You can find me on X, LinkedIn, Peerlist and GitHub.
