Route Optimization

Route optimization uses ML to plan efficient paths for vehicles, delivery drivers, and logistics networks. Classic operations research provides exact algorithms, but ML adds learning from historical patterns, handling uncertainty, and real-time adaptation that pure optimization cannot achieve alone.

Where It Is Used

Route optimization powers modern logistics:

• Last-mile delivery: Amazon, FedEx, UPS route planning
• Ride-sharing: Uber, Lyft driver dispatch
• Food delivery: DoorDash, Deliveroo order batching
• Field services: Technician scheduling, home visits
• Supply chain: Truck routing, warehouse picking
• Public transit: Bus route optimization
• Robotics: Warehouse robots, autonomous vehicles

Problem Variants

What You Do in Practice

1. Define constraints - Capacity, time windows, driver hours
2. Model the problem - Distance matrix, service times
3. Start with heuristics - Nearest neighbour, sweep algorithm
4. Improve with local search - 2-opt, 3-opt, LKH
5. Add ML predictions - Travel time, service duration
6. Handle dynamics - Real-time re-routing
7. Validate solutions - Constraint satisfaction
8. Monitor execution - Actual vs planned

Baseline First

Start with classic OR algorithms before ML-enhanced approaches:

import numpy as np
from typing import List, Tuple, Dict
from scipy.spatial.distance import cdist

class NearestNeighbourTSP:
    """Classic nearest neighbour heuristic."""

    def solve(self, distances: np.ndarray, start: int = 0) -> List[int]:
        """
        Nearest neighbour TSP solution.

        Args:
            distances: N x N distance matrix
            start: Starting node

        Returns:
            Tour as list of node indices
        """
        n = len(distances)
        visited = [False] * n
        tour = [start]
        visited[start] = True

        for _ in range(n - 1):
            current = tour[-1]
            nearest = None
            nearest_dist = float('inf')

            for j in range(n):
                if not visited[j] and distances[current][j] < nearest_dist:
                    nearest = j
                    nearest_dist = distances[current][j]

            tour.append(nearest)
            visited[nearest] = True

        return tour

    def tour_length(self, tour: List[int], distances: np.ndarray) -> float:
        """Calculate total tour length."""
        total = sum(
            distances[tour[i]][tour[i + 1]] 
            for i in range(len(tour) - 1)
        )
        total += distances[tour[-1]][tour[0]]  # Return to start
        return total

class TwoOptImprover:
    """2-opt local search improvement."""

    def improve(self, tour: List[int], distances: np.ndarray, 
                max_iterations: int = 1000) -> List[int]:
        """Improve tour using 2-opt swaps."""
        improved = True
        iteration = 0

        while improved and iteration < max_iterations:
            improved = False
            iteration += 1

            for i in range(len(tour) - 1):
                for j in range(i + 2, len(tour)):
                    if j == len(tour) - 1 and i == 0:
                        continue  # Skip if would just reverse whole tour

                    # Calculate improvement
                    delta = self._swap_delta(tour, i, j, distances)

                    if delta < -1e-10:  # Improvement found
                        # Perform 2-opt swap (reverse segment)
                        tour = tour[:i+1] + tour[i+1:j+1][::-1] + tour[j+1:]
                        improved = True
                        break

                if improved:
                    break

        return tour

    def _swap_delta(self, tour: List[int], i: int, j: int, 
                    distances: np.ndarray) -> float:
        """Calculate change in tour length from 2-opt swap."""
        n = len(tour)

        # Current edges
        a, b = tour[i], tour[i + 1]
        c, d = tour[j], tour[(j + 1) % n]

        # New edges after swap
        old_cost = distances[a][b] + distances[c][d]
        new_cost = distances[a][c] + distances[b][d]

        return new_cost - old_cost

class CapacitatedVRP:
    """Basic CVRP with savings algorithm."""

    def __init__(self, depot: int = 0):
        self.depot = depot

    def solve(self, distances: np.ndarray, demands: np.ndarray,
              vehicle_capacity: float, num_vehicles: int) -> List[List[int]]:
        """
        Clarke-Wright savings algorithm for CVRP.

        Returns:
            List of routes, each route is a list of customer indices
        """
        n = len(distances)
        customers = [i for i in range(n) if i != self.depot]

        # Calculate savings
        savings = []
        for i in customers:
            for j in customers:
                if i < j:
                    s = (distances[self.depot][i] + distances[self.depot][j] 
                         - distances[i][j])
                    savings.append((s, i, j))

        # Sort by savings (descending)
        savings.sort(reverse=True)

        # Initialize: each customer in own route
        routes = {i: [i] for i in customers}
        route_demands = {i: demands[i] for i in customers}

        # Merge routes based on savings
        for s, i, j in savings:
            if i not in routes or j not in routes:
                continue

            route_i = routes[i]
            route_j = routes[j]

            if route_i is route_j:
                continue

            # Check capacity
            combined_demand = route_demands[i] + route_demands[j]
            if combined_demand > vehicle_capacity:
                continue

            # Check if i and j are at route ends
            if route_i[-1] == i and route_j[0] == j:
                # Merge routes
                new_route = route_i + route_j
                new_demand = combined_demand

                # Update route references
                for node in new_route:
                    routes[node] = new_route
                    route_demands[node] = new_demand

        # Extract unique routes
        unique_routes = []
        seen = set()
        for route in routes.values():
            route_key = tuple(route)
            if route_key not in seen:
                seen.add(route_key)
                unique_routes.append(route)

        return unique_routes[:num_vehicles]

ML-Enhanced Routing

import numpy as np
import torch
import torch.nn as nn
from torch.distributions import Categorical

class TravelTimePredictor:
    """Predict travel times from features."""

    def __init__(self, feature_dim: int):
        self.model = nn.Sequential(
            nn.Linear(feature_dim, 64),
            nn.ReLU(),
            nn.Linear(64, 32),
            nn.ReLU(),
            nn.Linear(32, 1),
            nn.Softplus()  # Ensure positive times
        )

    def predict(self, origin: np.ndarray, destination: np.ndarray,
                time_features: np.ndarray) -> float:
        """Predict travel time given origin, destination, and context."""
        features = np.concatenate([origin, destination, time_features])
        with torch.no_grad():
            x = torch.FloatTensor(features)
            return self.model(x).item()

    def build_time_matrix(self, locations: np.ndarray, 
                          time_features: np.ndarray) -> np.ndarray:
        """Build predicted travel time matrix."""
        n = len(locations)
        times = np.zeros((n, n))

        for i in range(n):
            for j in range(n):
                if i != j:
                    times[i][j] = self.predict(
                        locations[i], locations[j], time_features
                    )

        return times

class AttentionVRPModel(nn.Module):
    """Attention-based model for VRP (inspired by Attention, Learn to Solve)."""

    def __init__(self, input_dim: int = 2, embed_dim: int = 128, n_heads: int = 8):
        super().__init__()

        # Node embedding
        self.node_embed = nn.Linear(input_dim, embed_dim)

        # Transformer encoder
        encoder_layer = nn.TransformerEncoderLayer(
            d_model=embed_dim, nhead=n_heads, batch_first=True
        )
        self.encoder = nn.TransformerEncoder(encoder_layer, num_layers=3)

        # Context for decoding
        self.context_embed = nn.Linear(embed_dim * 2, embed_dim)

        # Pointer network attention
        self.pointer = nn.Linear(embed_dim, embed_dim)

    def forward(self, nodes: torch.Tensor) -> torch.Tensor:
        """
        Encode nodes and compute attention weights.

        Args:
            nodes: (batch, n_nodes, input_dim)

        Returns:
            Node embeddings
        """
        # Embed nodes
        embedded = self.node_embed(nodes)

        # Encode with transformer
        encoded = self.encoder(embedded)

        return encoded

    def get_action_probs(self, encoded: torch.Tensor, 
                         current_node: int,
                         visited_mask: torch.Tensor) -> torch.Tensor:
        """Get probabilities for next node selection."""
        batch_size, n_nodes, embed_dim = encoded.shape

        # Current node embedding
        current_embed = encoded[:, current_node, :]

        # Global context
        graph_embed = encoded.mean(dim=1)

        # Combined context
        context = torch.cat([current_embed, graph_embed], dim=-1)
        context = self.context_embed(context)

        # Compute attention scores
        query = self.pointer(context).unsqueeze(1)  # (batch, 1, embed_dim)
        scores = torch.bmm(query, encoded.transpose(1, 2)).squeeze(1)  # (batch, n_nodes)

        # Mask visited nodes
        scores = scores.masked_fill(visited_mask, float('-inf'))

        # Softmax for probabilities
        probs = torch.softmax(scores, dim=-1)

        return probs

    def sample_tour(self, nodes: torch.Tensor, greedy: bool = False) -> List[int]:
        """Sample a tour using the model."""
        batch_size, n_nodes, _ = nodes.shape

        encoded = self.forward(nodes)

        tour = [0]  # Start at depot
        visited = torch.zeros(batch_size, n_nodes, dtype=torch.bool)
        visited[:, 0] = True

        current = 0
        for _ in range(n_nodes - 1):
            probs = self.get_action_probs(encoded, current, visited)

            if greedy:
                next_node = probs.argmax(dim=-1).item()
            else:
                dist = Categorical(probs)
                next_node = dist.sample().item()

            tour.append(next_node)
            visited[:, next_node] = True
            current = next_node

        return tour

class RLRoutingAgent:
    """RL agent for dynamic routing decisions."""

    def __init__(self, state_dim: int, action_dim: int):
        self.policy = nn.Sequential(
            nn.Linear(state_dim, 128),
            nn.ReLU(),
            nn.Linear(128, 64),
            nn.ReLU(),
            nn.Linear(64, action_dim),
            nn.Softmax(dim=-1)
        )
        self.optimizer = torch.optim.Adam(self.policy.parameters(), lr=0.001)

    def encode_state(self, current_location: np.ndarray,
                     remaining_stops: List[np.ndarray],
                     vehicle_capacity: float,
                     current_load: float,
                     time_remaining: float) -> np.ndarray:
        """Encode routing state for policy."""
        # Fixed-size state representation
        state = [
            *current_location,
            len(remaining_stops),
            current_load / vehicle_capacity,
            time_remaining
        ]

        # Add aggregated stop info
        if remaining_stops:
            stops = np.array(remaining_stops)
            state.extend([
                stops[:, 0].mean(), stops[:, 1].mean(),  # Mean location
                stops[:, 0].std(), stops[:, 1].std(),    # Spread
            ])
        else:
            state.extend([0, 0, 0, 0])

        return np.array(state)

    def select_next_stop(self, state: np.ndarray, 
                         valid_actions: List[int]) -> int:
        """Select next stop to visit."""
        with torch.no_grad():
            state_t = torch.FloatTensor(state)
            probs = self.policy(state_t).numpy()

        # Mask invalid actions
        masked_probs = np.zeros_like(probs)
        masked_probs[valid_actions] = probs[valid_actions]
        masked_probs /= masked_probs.sum()

        return np.random.choice(len(probs), p=masked_probs)

Time Windows and Constraints

from dataclasses import dataclass
from typing import Optional
import heapq

@dataclass
class Stop:
    """Delivery stop with constraints."""
    id: int
    location: np.ndarray
    demand: float
    time_window_start: float
    time_window_end: float
    service_time: float
    priority: int = 1

class VRPTWSolver:
    """VRP with time windows."""

    def __init__(self, depot_location: np.ndarray):
        self.depot = depot_location

    def is_feasible(self, route: List[Stop], arrival_times: List[float],
                    vehicle_capacity: float) -> bool:
        """Check if route satisfies all constraints."""
        # Capacity constraint
        total_demand = sum(stop.demand for stop in route)
        if total_demand > vehicle_capacity:
            return False

        # Time window constraints
        for stop, arrival in zip(route, arrival_times):
            if arrival > stop.time_window_end:
                return False

        return True

    def compute_arrival_times(self, route: List[Stop], 
                              travel_times: callable,
                              start_time: float = 0) -> List[float]:
        """Compute arrival times for each stop."""
        arrivals = []
        current_time = start_time
        current_loc = self.depot

        for stop in route:
            travel = travel_times(current_loc, stop.location)
            arrival = current_time + travel

            # Wait if arriving before time window
            if arrival < stop.time_window_start:
                arrival = stop.time_window_start

            arrivals.append(arrival)
            current_time = arrival + stop.service_time
            current_loc = stop.location

        return arrivals

    def insertion_cost(self, route: List[Stop], new_stop: Stop,
                       position: int, travel_times: callable) -> Optional[float]:
        """Calculate cost of inserting stop at position."""
        if position == 0:
            prev_loc = self.depot
        else:
            prev_loc = route[position - 1].location

        if position == len(route):
            next_loc = self.depot
        else:
            next_loc = route[position].location

        # Added distance
        old_dist = travel_times(prev_loc, next_loc) if route else 0
        new_dist = (travel_times(prev_loc, new_stop.location) + 
                   travel_times(new_stop.location, next_loc))

        # Check time feasibility
        test_route = route[:position] + [new_stop] + route[position:]
        arrivals = self.compute_arrival_times(test_route, travel_times)

        for stop, arrival in zip(test_route, arrivals):
            if arrival > stop.time_window_end:
                return None  # Infeasible

        return new_dist - old_dist + new_stop.service_time

    def greedy_insertion(self, stops: List[Stop], 
                         num_vehicles: int,
                         vehicle_capacity: float,
                         travel_times: callable) -> List[List[Stop]]:
        """Build routes using greedy insertion."""
        # Sort by time window end
        remaining = sorted(stops, key=lambda s: s.time_window_end)
        routes = [[] for _ in range(num_vehicles)]
        route_loads = [0] * num_vehicles

        for stop in remaining:
            best_route = None
            best_position = None
            best_cost = float('inf')

            for r_idx, route in enumerate(routes):
                # Check capacity
                if route_loads[r_idx] + stop.demand > vehicle_capacity:
                    continue

                # Try all positions
                for pos in range(len(route) + 1):
                    cost = self.insertion_cost(route, stop, pos, travel_times)
                    if cost is not None and cost < best_cost:
                        best_cost = cost
                        best_route = r_idx
                        best_position = pos

            if best_route is not None:
                routes[best_route].insert(best_position, stop)
                route_loads[best_route] += stop.demand

        return routes

Evaluation Metrics

def route_metrics(routes: List[List[Stop]], 
                  travel_times: callable,
                  depot: np.ndarray) -> dict:
    """Compute comprehensive routing metrics."""

    total_distance = 0
    total_time = 0
    total_wait = 0
    on_time = 0
    total_stops = 0

    for route in routes:
        if not route:
            continue

        # Calculate route distance and times
        current_loc = depot
        current_time = 0

        for stop in route:
            travel = travel_times(current_loc, stop.location)
            arrival = current_time + travel
            total_distance += travel

            # Wait time
            if arrival < stop.time_window_start:
                total_wait += stop.time_window_start - arrival
                arrival = stop.time_window_start

            # On-time check
            if arrival <= stop.time_window_end:
                on_time += 1

            current_time = arrival + stop.service_time
            current_loc = stop.location
            total_stops += 1

        # Return to depot
        total_distance += travel_times(current_loc, depot)

    return {
        'total_distance': total_distance,
        'num_routes': len([r for r in routes if r]),
        'on_time_percentage': on_time / total_stops if total_stops > 0 else 0,
        'total_wait_time': total_wait,
        'avg_stops_per_route': total_stops / len(routes) if routes else 0
    }

Failure Modes and Debugging Checklist

• [ ] Infeasible solutions: Routes violate constraints
• [ ] Suboptimal results: Stuck in local minima
• [ ] Time prediction errors: Actual != predicted travel times
• [ ] Dynamic changes: Not adapting to real-time updates
• [ ] Scalability: Too slow for problem size
• [ ] Driver compliance: Routes not followed in practice
• [ ] Edge cases: Unusual locations, demands

Production Checklist

Before deployment: - [ ] Validate against historical routes - [ ] Test constraint handling - [ ] Benchmark solve time - [ ] Set up fallback solutions - [ ] Driver interface/navigation

After deployment: - [ ] Monitor actual vs planned routes - [ ] Track on-time delivery rate - [ ] Measure driver satisfaction - [ ] Update travel time models - [ ] A/B test improvements

Tools and Stack

Example Mini-Case

Scenario: Last-mile delivery optimization for e-commerce.

Approach: - ML travel time prediction (traffic-aware) - VRPTW with soft time windows - Real-time re-routing for delays - Driver preference learning

Results: - 15% reduction in total distance - 23% improvement in on-time delivery - 8% fewer vehicles needed - Driver satisfaction improved by 12%

Related Pages

• Index: ML Field Guide
• Resource Allocation
• Reinforcement Learning
• Time Series Forecasting

Further Reading

• Google OR-Tools Routing
• Attention, Learn to Solve Routing Problems
• Vehicle Routing: Problems, Methods, and Applications

Try it live

Everything above runs in your browser — open AI Route Optimization Lab — A Delivery Fleet Case Study and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.