AI Route Optimization: How Delivery Companies Cut Fuel Costs by 20% with ML
Building intelligent routing systems that balance time, cost, and capacity constraints
AI Route Optimization: Solving the Last-Mile Delivery Challenge
Last-mile delivery accounts for 53% of total shipping costs. With fuel prices volatile and customer expectations for same-day delivery rising, route optimization has become a critical competitive differentiator.
The Route Optimization Problem
Traditional route planning has limitations:
The Vehicle Routing Problem (VRP) is NP-hard — there's no perfect algorithm. Modern approaches use a combination of heuristics, ML, and optimization to find near-optimal solutions.
Building a Route Optimization System
python
import numpy as np
from scipy.spatial.distance import cdist
from dataclasses import dataclass
from typing import Optional
import json@dataclass
class Delivery:
id: str
lat: float
lon: float
time_window_start: int # Minutes from depot open
time_window_end: int
service_time_minutes: int # How long to deliver
weight_kg: float
priority: int # 1=standard, 2=express, 3=critical
@dataclass
class Vehicle:
id: str
max_weight_kg: float
max_stops: int
start_lat: float
start_lon: float
end_lat: float # Return to depot
end_lon: float
class RouteOptimizer:
"""
Vehicle Routing Problem solver using nearest neighbor heuristic
+ 2-opt improvement. Production systems use OR-Tools or Vroom.
"""
EARTH_RADIUS_KM = 6371
AVG_SPEED_KMH = 40 # Urban average with traffic
FUEL_COST_PER_KM = 0.15 # USD
def __init__(self):
pass
def haversine_distance(self, lat1: float, lon1: float,
lat2: float, lon2: float) -> float:
"""Calculate distance between two coordinates in km."""
lat1, lon1, lat2, lon2 = map(np.radians, [lat1, lon1, lat2, lon2])
dlat = lat2 - lat1
dlon = lon2 - lon1
a = np.sin(dlat/2)2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon/2)2
return 2 * self.EARTH_RADIUS_KM * np.arcsin(np.sqrt(a))
def build_distance_matrix(self, locations: list[tuple]) -> np.ndarray:
"""Build matrix of distances between all locations."""
n = len(locations)
distances = np.zeros((n, n))
for i in range(n):
for j in range(i+1, n):
d = self.haversine_distance(
locations[i][0], locations[i][1],
locations[j][0], locations[j][1]
)
distances[i][j] = distances[j][i] = d
return distances
def nearest_neighbor_route(self, depot_idx: int,
delivery_indices: list[int],
distance_matrix: np.ndarray) -> list[int]:
"""
Build route using nearest neighbor heuristic.
Fast, ~20% above optimal on average.
"""
unvisited = set(delivery_indices)
route = [depot_idx]
current = depot_idx
while unvisited:
# Find nearest unvisited
nearest = min(
unvisited,
key=lambda x: distance_matrix[current][x]
)
route.append(nearest)
unvisited.remove(nearest)
current = nearest
route.append(depot_idx) # Return to depot
return route
def two_opt_improvement(self, route: list[int],
distance_matrix: np.ndarray,
max_iterations: int = 100) -> list[int]:
"""
2-opt improvement: iteratively reverse segments to reduce distance.
Typically improves nearest neighbor by 10-15%.
"""
best = route[:]
improved = True
iteration = 0
while improved and iteration < max_iterations:
improved = False
iteration += 1
for i in range(1, len(best) - 2):
for j in range(i + 1, len(best) - 1):
# Calculate current distance for this segment
current_dist = (
distance_matrix[best[i-1]][best[i]] +
distance_matrix[best[j]][best[j+1]]
)
# Calculate distance if we reverse the segment
new_dist = (
distance_matrix[best[i-1]][best[j]] +
distance_matrix[best[i]][best[j+1]]
)
if new_dist < current_dist - 0.001:
# Reverse the segment
best[i:j+1] = best[i:j+1][::-1]
improved = True
return best
def optimize_fleet(self, deliveries: list[Delivery],
vehicles: list[Vehicle]) -> dict:
"""
Assign deliveries to vehicles and optimize each route.
Simple nearest neighbor assignment (production: use OR-Tools).
"""
# Sort by priority then time window
sorted_deliveries = sorted(
deliveries,
key=lambda d: (-d.priority, d.time_window_end)
)
routes = {v.id: [] for v in vehicles}
vehicle_load = {v.id: 0.0 for v in vehicles}
# Assign deliveries to vehicles (greedy)
for delivery in sorted_deliveries:
# Find best vehicle (one with capacity and nearest current position)
best_vehicle = None
best_distance = float('inf')
for vehicle in vehicles:
if vehicle_load[vehicle.id] + delivery.weight_kg <= vehicle.max_weight_kg:
if len(routes[vehicle.id]) < vehicle.max_stops:
current_route = routes[vehicle.id]
last_location = (
(current_route[-1].lat, current_route[-1].lon)
if current_route else (vehicle.start_lat, vehicle.start_lon)
)
dist = self.haversine_distance(
last_location[0], last_location[1],
delivery.lat, delivery.lon
)
if dist < best_distance:
best_distance = dist
best_vehicle = vehicle
if best_vehicle:
routes[best_vehicle.id].append(delivery)
vehicle_load[best_vehicle.id] += delivery.weight_kg
else:
print(f"Warning: Cannot assign delivery {delivery.id}")
# Optimize each vehicle's route
optimized_routes = {}
total_distance = 0
for vehicle in vehicles:
route_deliveries = routes[vehicle.id]
if not route_deliveries:
continue
# Build locations list: [depot, d1, d2, ..., depot]
locations = [(vehicle.start_lat, vehicle.start_lon)] + [
(d.lat, d.lon) for d in route_deliveries
]
distance_matrix = self.build_distance_matrix(locations)
# Optimize
indices = list(range(1, len(locations)))
nn_route = self.nearest_neighbor_route(0, indices, distance_matrix)
optimized_route = self.two_opt_improvement(nn_route, distance_matrix)
# Calculate route statistics
route_distance = sum(
distance_matrix[optimized_route[i]][optimized_route[i+1]]
for i in range(len(optimized_route)-1)
)
estimated_time = (route_distance / self.AVG_SPEED_KMH * 60 +
sum(d.service_time_minutes for d in route_deliveries))
total_distance += route_distance
optimized_routes[vehicle.id] = {
'delivery_order': [
route_deliveries[i-1].id for i in optimized_route[1:-1]
],
'total_distance_km': round(route_distance, 1),
'estimated_time_minutes': round(estimated_time),
'stops': len(route_deliveries),
'fuel_cost_usd': round(route_distance * self.FUEL_COST_PER_KM, 2),
'load_kg': round(vehicle_load[vehicle.id], 1)
}
return {
'routes': optimized_routes,
'total_distance_km': round(total_distance, 1),
'total_fuel_cost': round(total_distance * self.FUEL_COST_PER_KM, 2),
'vehicles_used': len([r for r in optimized_routes.values() if r['stops'] > 0])
}
Real-time replanning for failed deliveries
def handle_failed_delivery(failed_delivery_id: str,
current_routes: dict,
optimizer: RouteOptimizer) -> dict:
"""
Replan remaining stops when a delivery fails.
Critical for maintaining time windows.
"""
updated_routes = {}
for vehicle_id, route in current_routes.items():
if failed_delivery_id in route.get('delivery_order', []):
# Remove failed delivery and continue optimizing remaining
remaining = [d for d in route['delivery_order'] if d != failed_delivery_id]
updated_routes[vehicle_id] = {
**route,
'delivery_order': remaining,
'stops': len(remaining),
'replan_reason': f'Failed delivery {failed_delivery_id} removed'
}
else:
updated_routes[vehicle_id] = route
return updated_routes
Production Route Optimization Tools
For real deployments, use dedicated optimization engines:
OR-Tools is the gold standard for custom implementations — it's what Google, Lyft, and many logistics companies use internally.
Environmental and Business Impact
AI route optimization creates a compelling sustainability story alongside cost savings:
For a company doing 10,000 deliveries/day, a 25% route optimization translates to roughly $2M annual savings and 1,500 fewer tons of CO2.
Also available in 中文.