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: How Delivery Companies Cut Fuel Costs by 20% with ML
Building intelligent routing systems that balance time, cost, and capacity constraints
Learn how AI-powered route optimization algorithms are transforming last-mile delivery — reducing fuel consumption, improving delivery windows, and handling real-time disruptions automatically.
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.
相关教程
How companies are using ML and NLP to monitor supplier health and predict supply disruptions
How warehouses are using AI to reduce picking time by 35% without full robotics investment
Building machine learning demand forecasting systems that outperform traditional statistical methods