Tutorial

Stop sorting deliveries by postcode: optimize a route in Python in 40 lines

Most delivery teams order their stops in one of three ways: the order the orders came in, by postcode, or by whatever the dispatcher remembers about the neighbourhood. It works until you have 30 stops, two deadlines and a driver who crosses the same bridge three times.

That ordering problem has a name, the travelling-salesman problem, and with time windows it becomes the harder vehicle-routing problem. You can solve it yourself with an open-source solver, and for some teams that is the right call (more on that below). If you just need a good order inside your own app, a route optimization API is faster to ship.

In this tutorial we do something concrete: take 10 stops in Paris, send them to the Otiggo route optimization API, and measure how much shorter the optimized route is than the order we started with. You can run everything with a free test key.

What you need

• Python 3.8+ and pip install requests
• A free test key (otg_test_...) from the sandbox. No card is required.

Test keys accept GPS coordinates only and are capped at 10 stops per call, which is exactly what we need here.

export OTIGGO_API_KEY=otg_test_...

The script

import math
import os
import requests

API = "https://app.otiggo.com/api/v1/optimize"
KEY = os.environ["OTIGGO_API_KEY"]

DEPOT = {"latitude": 48.8809, "longitude": 2.3553}  # Gare du Nord

# Stops in the order they "arrived": nothing clever about it.
STOPS = [
    {"id": "Eiffel Tower",    "latitude": 48.8584, "longitude": 2.2945},
    {"id": "Sacre-Coeur",     "latitude": 48.8867, "longitude": 2.3431},
    {"id": "Gare de Lyon",    "latitude": 48.8443, "longitude": 2.3744},
    {"id": "Arc de Triomphe", "latitude": 48.8738, "longitude": 2.2950},
    {"id": "Bastille",        "latitude": 48.8531, "longitude": 2.3691},
    {"id": "Louvre",          "latitude": 48.8606, "longitude": 2.3376},
    {"id": "Montparnasse",    "latitude": 48.8422, "longitude": 2.3219},
    {"id": "Republique",      "latitude": 48.8674, "longitude": 2.3636},
    {"id": "Opera Garnier",   "latitude": 48.8720, "longitude": 2.3316},
    {"id": "Notre-Dame",      "latitude": 48.8530, "longitude": 2.3499},
]


def haversine_km(a, b):
    """Straight-line distance between two points, in km."""
    la1, lo1, la2, lo2 = map(math.radians, (a["latitude"], a["longitude"], b["latitude"], b["longitude"]))
    h = math.sin((la2 - la1) / 2) ** 2 + math.cos(la1) * math.cos(la2) * math.sin((lo2 - lo1) / 2) ** 2
    return 2 * 6371 * math.asin(math.sqrt(h))


def route_km(points):
    return sum(haversine_km(p, q) for p, q in zip(points, points[1:]))


response = requests.post(
    API,
    json={"start": DEPOT, "stops": STOPS},
    headers={"Authorization": f"Bearer {KEY}"},
)
response.raise_for_status()
result = response.json()

by_id = {s["id"]: s for s in STOPS}
optimized = [DEPOT] + [by_id[i] for i in result["order"]]
original = [DEPOT] + STOPS

before, after = route_km(original), route_km(optimized)
print("Optimized order:", " -> ".join(result["order"]))
print(f"Original order : {before:.1f} km (straight lines)")
print(f"Optimized order: {after:.1f} km (straight lines)")
print(f"Saved          : {100 * (before - after) / before:.0f}%")
print(f"API estimate   : {result['totalDistanceKm']} km by road, {result['estimatedTimeMin']} min")

Run it and you get your own numbers. We do not quote a result here on purpose: the saving depends on the stops, and it is more convincing when you see it on your data.

What the script does

1. Sends one request. The body is a start point and a list of stops, each with an id you choose and coordinates (or, with a live key, a street address).
2. Reads the order. The response lists your ids in the best visiting order, plus totalDistanceKm, estimatedTimeMin and a timestamped schedule.
3. Compares both orders with the same yardstick. The API reports distance by road, so to compare fairly we measure both orders ourselves in straight lines with the haversine formula. It is a rough proxy, not a road distance, but it is the same for both routes.

Adding deadlines

Real deliveries have constraints. Give a stop a deadline (HH:MM, Paris time) and a serviceSeconds (time spent at the door):

{"id": "Louvre", "latitude": 48.8606, "longitude": 2.3376,
 "deadline": "10:30", "serviceSeconds": 240}

The response then includes lateStops, the stops that would still miss their deadline, so you can warn the dispatcher before the route starts rather than after.

Handling errors

Failed calls are not charged, and live calls that fail after a debit are refunded. Full list in the error reference.

Going to 50 or 200 stops

With a live key you can send up to 200 stops per call and pass addresses instead of coordinates; the API geocodes them for you. Billing is prepaid per stop, with no subscription: 2,000 stops cost €99 and 250,000 cost €2,999, and stops never expire (pricing).

When you should not use an API

An API is not always the right answer, and it is fair to say so:

• You have a very large or unusual problem, such as hundreds of vehicles, pickups and deliveries, or custom cost functions. An open-source solver like OR-Tools gives you full control, at the price of running and tuning it yourself.
• You need results offline or inside a network you cannot leave.
• You solve a handful of routes a year. Then a spreadsheet and a map are fine.

An API fits the middle: you want a good order for one driver's round, inside your product, without owning a solver.

Resources

• API documentation and the OpenAPI 3.1 spec (import it into Postman or Insomnia)
• Python, Node, PHP and curl examples on GitHub