Delivery Route Optimization in London¶
This notebook solves a Capacitated Vehicle Routing Problem (CVRP) for a fleet of delivery vehicles serving customers across London.
A depot dispatches vehicles to deliver parcels to customers scattered around the city. Each vehicle has a limited capacity, and the goal is to minimize total travel distance while ensuring every customer is served exactly once.
\[\min \sum_{k \in K} \sum_{(i,j) \in A} c_{ij} \, x_{ijk}
\quad \text{s.t.} \quad
\sum_{i} q_i \sum_{j} x_{ijk} \leq Q \;\; \forall k, \quad
\sum_{k} \sum_{j} x_{ijk} = 1 \;\; \forall i \neq 0\]
See vrp_example.ipynb for the complete mathematical formulation.
[1]:
import sys
sys.path.insert(0, "../src")
[2]:
import numpy as np
import folium
from folium import plugins
from optymus.routing import solve_vrp, VRPSolver, compute_distance_matrix
/Users/holisticai008/Documents/repos/quantsci/optymus/.venv/lib/python3.12/site-packages/tqdm/auto.py:21: TqdmWarning: IProgress not found. Please update jupyter and ipywidgets. See https://ipywidgets.readthedocs.io/en/stable/user_install.html
from .autonotebook import tqdm as notebook_tqdm
1. London Delivery Instance¶
We model a parcel delivery company operating from a depot near King’s Cross, serving 25 customer locations across London. Each customer has a demand (number of parcels), and each van can carry up to 50 parcels.
[3]:
# Depot and customer locations (latitude, longitude)
locations = {
# Depot
0: {"name": "Depot (King's Cross)", "lat": 51.5317, "lon": -0.1240, "demand": 0},
# Customers
1: {"name": "Camden Town", "lat": 51.5392, "lon": -0.1426, "demand": 8},
2: {"name": "Islington (Angel)", "lat": 51.5322, "lon": -0.1058, "demand": 5},
3: {"name": "Shoreditch", "lat": 51.5265, "lon": -0.0799, "demand": 12},
4: {"name": "Hackney Central", "lat": 51.5467, "lon": -0.0555, "demand": 6},
5: {"name": "Stratford", "lat": 51.5415, "lon": -0.0035, "demand": 9},
6: {"name": "Canary Wharf", "lat": 51.5054, "lon": -0.0235, "demand": 15},
7: {"name": "Greenwich", "lat": 51.4769, "lon": -0.0005, "demand": 7},
8: {"name": "Lewisham", "lat": 51.4613, "lon": -0.0139, "demand": 4},
9: {"name": "Brixton", "lat": 51.4613, "lon": -0.1145, "demand": 10},
10: {"name": "Clapham", "lat": 51.4625, "lon": -0.1380, "demand": 6},
11: {"name": "Battersea", "lat": 51.4751, "lon": -0.1517, "demand": 3},
12: {"name": "Chelsea", "lat": 51.4875, "lon": -0.1687, "demand": 8},
13: {"name": "Kensington", "lat": 51.4990, "lon": -0.1940, "demand": 11},
14: {"name": "Notting Hill", "lat": 51.5117, "lon": -0.1955, "demand": 5},
15: {"name": "Paddington", "lat": 51.5154, "lon": -0.1755, "demand": 7},
16: {"name": "Marylebone", "lat": 51.5225, "lon": -0.1563, "demand": 4},
17: {"name": "Soho", "lat": 51.5137, "lon": -0.1337, "demand": 13},
18: {"name": "Covent Garden", "lat": 51.5117, "lon": -0.1240, "demand": 9},
19: {"name": "City of London", "lat": 51.5155, "lon": -0.0922, "demand": 14},
20: {"name": "Tower Bridge", "lat": 51.5055, "lon": -0.0754, "demand": 6},
21: {"name": "Bermondsey", "lat": 51.4977, "lon": -0.0636, "demand": 5},
22: {"name": "Hampstead", "lat": 51.5565, "lon": -0.1781, "demand": 3},
23: {"name": "Highbury", "lat": 51.5510, "lon": -0.0988, "demand": 7},
24: {"name": "Westminster", "lat": 51.4975, "lon": -0.1357, "demand": 10},
25: {"name": "Waterloo", "lat": 51.5036, "lon": -0.1143, "demand": 8},
}
names = [locations[i]["name"] for i in range(len(locations))]
coordinates = np.array([[locations[i]["lat"], locations[i]["lon"]] for i in range(len(locations))])
demands = np.array([locations[i]["demand"] for i in range(len(locations))], dtype=float)
vehicle_capacity = 50
n_customers = len(locations) - 1
print(f"Depot: {names[0]}")
print(f"Customers: {n_customers}")
print(f"Total parcels: {int(demands.sum())}")
print(f"Van capacity: {vehicle_capacity} parcels")
print(f"Min vans needed: {int(np.ceil(demands.sum() / vehicle_capacity))}")
Depot: Depot (King's Cross)
Customers: 25
Total parcels: 195
Van capacity: 50 parcels
Min vans needed: 4
2. Solve the CVRP¶
[4]:
result = solve_vrp(
coordinates=coordinates,
demands=demands,
vehicle_capacity=vehicle_capacity,
)
result
Initial solution: 5 routes, distance = 0.9696
Final solution: 5 routes, distance = 0.9696 (0.0% improvement)
[4]:
OptimizeResult: CVRP (Clarke-Wright Savings + 2-opt)
----------------------------------------------------
Optimal Solution 5 routes
Function Value 9.695525e-01
Iterations 1
Termination local_search_converged
Time (s) 0.0018
Converged True
----------------------------------------------------
3. Route Summary¶
[5]:
print(f"{'Route':<8} {'Stops':<8} {'Parcels':<10} {'Distance':<12} {'Customers'}")
print("-" * 80)
for i, rd in enumerate(result.route_details):
stop_names = " -> ".join(names[c] for c in rd["customers"])
print(f"{i+1:<8} {len(rd['customers']):<8} {int(rd['load']):<10} {rd['distance']:<12.4f} {stop_names}")
print("-" * 80)
print(f"{'Total':<8} {n_customers:<8} {int(demands.sum()):<10} {result.total_distance:<12.4f}")
Route Stops Parcels Distance Customers
--------------------------------------------------------------------------------
1 3 15 0.1335 Camden Town -> Hampstead -> Marylebone
2 4 40 0.0917 Covent Garden -> Waterloo -> Westminster -> Soho
3 5 44 0.1435 Islington (Angel) -> City of London -> Tower Bridge -> Shoreditch -> Highbury
4 6 46 0.3518 Hackney Central -> Stratford -> Canary Wharf -> Greenwich -> Lewisham -> Bermondsey
5 7 50 0.2492 Brixton -> Clapham -> Battersea -> Chelsea -> Kensington -> Notting Hill -> Paddington
--------------------------------------------------------------------------------
Total 25 195 0.9696
4. Interactive Map¶
[6]:
# Route color palette
ROUTE_COLORS = ["#e6194b", "#3cb44b", "#4363d8", "#f58231", "#911eb4",
"#42d4f4", "#f032e6", "#bfef45", "#fabed4", "#469990"]
# Build customer -> route mapping
customer_route = {}
for ri, route in enumerate(result.routes):
for c in route:
customer_route[c] = ri
# Create the map centered on London
center_lat = coordinates[:, 0].mean()
center_lon = coordinates[:, 1].mean()
m = folium.Map(location=[center_lat, center_lon], zoom_start=12,
tiles="cartodbpositron")
# Add route polylines and customer markers as FeatureGroups (togglable)
for ri, route in enumerate(result.routes):
color = ROUTE_COLORS[ri % len(ROUTE_COLORS)]
rd = result.route_details[ri]
fg = folium.FeatureGroup(name=f"Route {ri+1} ({int(rd['load'])} parcels, {rd['distance']:.3f})")
# Route polyline: depot -> customers -> depot
full_route = [0] + route + [0]
path = [[coordinates[node, 0], coordinates[node, 1]] for node in full_route]
folium.PolyLine(
path, color=color, weight=4, opacity=0.8,
dash_array="10" if ri % 2 == 1 else None, # alternate solid/dashed
).add_to(fg)
# Customer markers
for seq, c in enumerate(route):
popup_html = (
f"<b>{names[c]}</b><br>"
f"Route {ri+1}, stop #{seq+1}<br>"
f"Demand: {int(demands[c])} parcels"
)
folium.CircleMarker(
location=[coordinates[c, 0], coordinates[c, 1]],
radius=6 + demands[c] * 0.5, # size proportional to demand
color=color,
fill=True,
fill_color=color,
fill_opacity=0.85,
popup=folium.Popup(popup_html, max_width=200),
tooltip=f"{names[c]} ({int(demands[c])} parcels)",
).add_to(fg)
# Sequence number label
folium.Marker(
location=[coordinates[c, 0], coordinates[c, 1]],
icon=folium.DivIcon(
html=f'<div style="font-size:9px; font-weight:bold; color:{color}; '
f'text-shadow: 1px 1px 1px white, -1px -1px 1px white, '
f'1px -1px 1px white, -1px 1px 1px white;'
f'margin-top:-20px; margin-left:8px;">{seq+1}</div>',
icon_size=(20, 20),
),
).add_to(fg)
fg.add_to(m)
# Depot marker
folium.Marker(
location=[coordinates[0, 0], coordinates[0, 1]],
icon=folium.Icon(color="red", icon="warehouse", prefix="fa"),
popup=f"<b>{names[0]}</b><br>Depot",
tooltip="Depot",
).add_to(m)
# Layer control and fit bounds
folium.LayerControl(collapsed=False).add_to(m)
sw = [coordinates[:, 0].min() - 0.01, coordinates[:, 1].min() - 0.01]
ne = [coordinates[:, 0].max() + 0.01, coordinates[:, 1].max() + 0.01]
m.fit_bounds([sw, ne])
m
[6]:
Make this Notebook Trusted to load map: File -> Trust Notebook
5. Animated Vehicle Simulation¶
Generate a standalone HTML file that animates the delivery vans moving along their routes in real time.
[ ]:
import json, string
def build_animation_html(coordinates, names, demands, result, route_colors, output_path):
"""Generate a standalone HTML file with animated vehicle markers on a Leaflet map."""
depot = [float(coordinates[0, 0]), float(coordinates[0, 1])]
routes_js = []
for ri, route in enumerate(result.routes):
full_route = [0] + route + [0]
routes_js.append({
"color": route_colors[ri % len(route_colors)],
"stops": [[float(coordinates[n, 0]), float(coordinates[n, 1])] for n in full_route],
"names": [names[n] for n in full_route],
"demands": [int(demands[n]) for n in full_route],
"load": int(result.route_details[ri]["load"]),
})
center_lat = float(coordinates[:, 0].mean())
center_lon = float(coordinates[:, 1].mean())
sw = [float(coordinates[:, 0].min()) - 0.01, float(coordinates[:, 1].min()) - 0.01]
ne = [float(coordinates[:, 0].max()) + 0.01, float(coordinates[:, 1].max()) + 0.01]
# Use string.Template to avoid f-string conflicts with JS curly braces
tmpl = string.Template("""<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0"/>
<title>London VRP — Vehicle Animation</title>
<link rel="stylesheet" href="https://unpkg.com/leaflet@1.9.4/dist/leaflet.css"/>
<script src="https://unpkg.com/leaflet@1.9.4/dist/leaflet.js"></script>
<style>
*{margin:0;padding:0;box-sizing:border-box}
body{font-family:'Segoe UI',system-ui,sans-serif}
#map{width:100vw;height:100vh}
#controls{position:absolute;top:14px;right:14px;z-index:1000;background:rgba(255,255,255,.95);
border-radius:10px;padding:14px 18px;box-shadow:0 2px 12px rgba(0,0,0,.18);
display:flex;flex-direction:column;gap:10px;min-width:220px}
#controls h3{font-size:14px;margin-bottom:2px}
#controls label{font-size:12px;color:#555}
#controls input[type=range]{width:100%}
.btn{padding:8px 16px;border:none;border-radius:6px;cursor:pointer;font-size:13px;font-weight:600;transition:all .15s}
.btn-play{background:#3cb44b;color:#fff} .btn-play:hover{background:#2e9639}
.btn-pause{background:#e6194b;color:#fff} .btn-pause:hover{background:#c4163f}
.btn-reset{background:#4363d8;color:#fff} .btn-reset:hover{background:#3452b0}
.btn-row{display:flex;gap:6px}
#progress-bar{position:absolute;bottom:0;left:0;z-index:1000;width:100%;height:5px;background:rgba(0,0,0,.1)}
#progress-fill{height:100%;width:0%;background:#3cb44b;transition:width .1s}
#legend{position:absolute;bottom:20px;left:14px;z-index:1000;background:rgba(255,255,255,.95);
border-radius:10px;padding:12px 16px;box-shadow:0 2px 12px rgba(0,0,0,.18);font-size:12px}
.legend-item{display:flex;align-items:center;gap:8px;margin:4px 0}
.legend-dot{width:12px;height:12px;border-radius:50%;flex-shrink:0}
#status{position:absolute;bottom:20px;right:14px;z-index:1000;background:rgba(255,255,255,.95);
border-radius:10px;padding:12px 16px;box-shadow:0 2px 12px rgba(0,0,0,.18);font-size:12px;min-width:200px}
.status-vehicle{margin:3px 0;display:flex;justify-content:space-between}
</style>
</head>
<body>
<div id="map"></div>
<div id="controls">
<h3>🚚 Vehicle Simulation</h3>
<div class="btn-row">
<button class="btn btn-play" id="playBtn" onclick="togglePlay()">▶ Play</button>
<button class="btn btn-reset" onclick="resetAnimation()">↺ Reset</button>
</div>
<label>Speed</label>
<input type="range" id="speed" min="1" max="20" value="8" oninput="updateSpeed(this.value)"/>
</div>
<div id="legend"></div>
<div id="status"></div>
<div id="progress-bar"><div id="progress-fill"></div></div>
<script>
const ROUTES = $routes_json;
const DEPOT = $depot_json;
const INTERP = 80;
const map = L.map('map').setView([$center_lat, $center_lon], 12);
L.tileLayer('https://{s}.basemaps.cartocdn.com/light_all/{z}/{x}/{y}{r}.png', {
attribution: '© OpenStreetMap © CARTO', maxZoom: 19
}).addTo(map);
map.fitBounds([$sw_json, $ne_json]);
// Depot
L.marker(DEPOT, {icon: L.divIcon({html:'<div style="font-size:24px">🏭</div>',
iconSize:[28,28], iconAnchor:[14,14], className:''})
}).addTo(map).bindTooltip("Depot (King's Cross)");
// Static elements
const custMarkers=[], trails=[];
ROUTES.forEach((r,ri)=>{
L.polyline(r.stops,{color:r.color,weight:3,opacity:0.25,dashArray:'8,8'}).addTo(map);
r.stops.forEach((pos,si)=>{
if(si===0||si===r.stops.length-1) return;
const cm=L.circleMarker(pos,{radius:5+r.demands[si]*0.4,color:r.color,
fillColor:r.color,fillOpacity:0.15,weight:1.5,opacity:0.4}).addTo(map);
cm.bindTooltip(r.names[si]+' ('+r.demands[si]+' parcels)');
cm._ri=ri; cm._si=si;
custMarkers.push(cm);
});
trails.push(L.polyline([],{color:r.color,weight:4,opacity:0.8}).addTo(map));
});
// Vehicle markers
const vans=ROUTES.map((r,ri)=>{
const m=L.marker(DEPOT,{icon:L.divIcon({html:'<div style="font-size:22px">🚐</div>',
iconSize:[26,26],iconAnchor:[13,13],className:''}),zIndexOffset:1000}).addTo(map);
m.bindTooltip('Van '+(ri+1),{permanent:true,direction:'top',offset:[0,-14]});
return m;
});
// Interpolate paths
function interp(stops){
const fr=[];
for(let i=0;i<stops.length-1;i++){
const[a,b]=stops[i],[c,d]=stops[i+1];
for(let f=0;f<INTERP;f++){const t=f/INTERP;fr.push({lat:a+(c-a)*t,lon:b+(d-b)*t,seg:i,t});}
}
const l=stops[stops.length-1]; fr.push({lat:l[0],lon:l[1],seg:stops.length-2,t:1});
return fr;
}
const paths=ROUTES.map(r=>interp(r.stops));
const maxF=Math.max(...paths.map(p=>p.length));
// Animation
let frame=0, playing=false, speed=8, animId=null, lt=0;
function updateSpeed(v){speed=parseInt(v);}
function togglePlay(){if(playing)pause();else play();}
function play(){
playing=true;
document.getElementById('playBtn').innerHTML='▮▮ Pause';
document.getElementById('playBtn').className='btn btn-pause';
tick();
}
function pause(){
playing=false;
document.getElementById('playBtn').innerHTML='▶ Play';
document.getElementById('playBtn').className='btn btn-play';
if(animId)cancelAnimationFrame(animId);
}
function resetAnimation(){
pause(); frame=0;
vans.forEach(m=>m.setLatLng(DEPOT));
trails.forEach(t=>t.setLatLngs([]));
custMarkers.forEach(c=>c.setStyle({fillOpacity:0.15,opacity:0.4}));
updateUI();
}
function tick(ts){
if(!playing)return;
if(!ts)ts=0;
if(ts-lt<(28-speed*1.2)){animId=requestAnimationFrame(tick);return;}
lt=ts;
ROUTES.forEach((r,ri)=>{
const p=paths[ri], f=Math.min(frame,p.length-1), pos=p[f];
vans[ri].setLatLng([pos.lat,pos.lon]);
const tc=[];for(let i=0;i<=f;i++)tc.push([p[i].lat,p[i].lon]);
trails[ri].setLatLngs(tc);
const vs=pos.seg+(pos.t>0.5?1:0);
custMarkers.forEach(cm=>{if(cm._ri===ri&&cm._si<=vs)cm.setStyle({fillOpacity:0.85,opacity:1});});
});
updateUI(); frame++;
if(frame>=maxF){pause();frame=maxF;return;}
animId=requestAnimationFrame(tick);
}
function updateUI(){
const pct=maxF>0?(frame/maxF*100):0;
document.getElementById('progress-fill').style.width=pct+'%';
let h='';
ROUTES.forEach((r,ri)=>{
const p=paths[ri],f=Math.min(frame,p.length-1),s=p[f].seg;
const nm=r.names[Math.min(s+1,r.names.length-1)];
const done=f>=p.length-1;
h+='<div class="status-vehicle"><span style="color:'+r.color+';font-weight:600">Van '+(ri+1)
+'</span><span>'+(done?'✅ Done':'📦 '+nm)+'</span></div>';
});
document.getElementById('status').innerHTML='<b>Live Status</b>'+h;
}
// Legend
let lh='';
ROUTES.forEach((r,ri)=>{
lh+='<div class="legend-item"><div class="legend-dot" style="background:'+r.color+'"></div>'
+'<span>Van '+(ri+1)+' — '+r.load+' parcels, '+(r.stops.length-2)+' stops</span></div>';
});
document.getElementById('legend').innerHTML='<b>Routes</b>'+lh;
updateUI();
</script>
</body>
</html>""")
html = tmpl.substitute(
routes_json=json.dumps(routes_js),
depot_json=json.dumps(depot),
center_lat=center_lat,
center_lon=center_lon,
sw_json=json.dumps(sw),
ne_json=json.dumps(ne),
)
with open(output_path, "w") as f:
f.write(html)
print(f"Animation saved to {output_path}")
# Generate the animated HTML
build_animation_html(
coordinates, names, demands, result, ROUTE_COLORS,
output_path="vrp_london_animation.html",
)
6. Constrained Fleet Size¶
Use VRPSolver directly to fix the number of vehicles.
7. Using a Custom Distance Matrix¶
If you have a real road-distance or travel-time matrix (e.g. from a routing API), pass it directly instead of coordinates.
[8]:
D = compute_distance_matrix(coordinates)
result_dm = solve_vrp(
distance_matrix=D,
demands=demands,
vehicle_capacity=vehicle_capacity,
verbose=False,
)
print(f"Total distance: {result_dm.total_distance:.4f}")
print(f"Vehicles used: {result_dm.num_vehicles_used}")
print(f"Converged: {result_dm.converged}")
Total distance: 0.9696
Vehicles used: 5
Converged: True