VRP Optimization API

🔥 Vibe Prompt

"Create a FastAPI delivery optimization service: input depot + customer coordinates and demands, output optimized routes."

from fastapi import FastAPI
from pydantic import BaseModel

app = FastAPI(title="Delivery Optimization API")

class DeliveryRequest(BaseModel):
    depot: tuple[float, float]
    customers: list[tuple[float, float]]
    demands: list[int]
    vehicle_capacity: int
    num_vehicles: int

@app.post("/optimize")
def optimize_delivery(req: DeliveryRequest):
    # Use OR-Tools to solve CVRP
    # Return optimized routes
    return {"routes": routes, "total_distance": total_dist}

🚀 Test with curl

curl -X POST "http://localhost:8000/optimize" -H "Content-Type: application/json" -d '{"depot":[25.03,121.56],"customers":[[25.05,121.58],...],"demands":[100,...],"vehicle_capacity":2000,"num_vehicles":3}'

VRP Course Complete! 🎉

✅ TSP/VRP Basics
✅ CVRP
✅ VRPTW
✅ Large-Scale Heuristics
✅ VRP API

Chapter Summary

Understand core concepts and principles
Master implementation methods and techniques
Familiar with common issues and solutions
Able to apply in real projects

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

Setup: Configure development environment
Data: Prepare required data
Implementation: Build core functionality
Testing: Verify correctness
Optimization: Improve performance

Common Errors

| Error Type | Cause | Solution | |------------|-------|----------| | Compilation | Syntax | Check code syntax | | Runtime | Environment | Verify dependencies installed | | Logic | Algorithm | Step-by-step debugging | | Performance | Efficiency | Use profilers |

Code Example

import sys

def main():
    print("Hello, World!")

if __name__ == "__main__":
    main()

References

Official documentation
API reference
Open source examples
Community discussions

VRP API Overview

The VRP API exposes vehicle routing optimization as a web service. Send customer data and vehicle parameters, receive optimized routes.

API Features

| Feature | Description | |---------|-------------| | CVRP optimization | Capacity-constrained routing | | VRPTW optimization | Time-window constrained routing | | Distance matrix input | Accepts custom distance matrices | | Route visualization | Returns ordered lists of stops | | Multiple algorithms | Savings, OR-Tools, or heuristic |

FastAPI Implementation

from fastapi import FastAPI, HTTPException
from pydantic import BaseModel
from typing import List, Optional

app = FastAPI(title="VRP Optimization API")

class Customer(BaseModel):
    id: int
    demand: float
    x: float
    y: float
    ready_time: Optional[float] = 0
    due_time: Optional[float] = 1e9
    service_time: Optional[float] = 0

class Vehicle(BaseModel):
    id: int
    capacity: float

class VRPRequest(BaseModel):
    depot: Customer
    customers: List[Customer]
    vehicles: List[Vehicle]
    algorithm: str = "savings"  # savings, ortools, nearest

class RouteStop(BaseModel):
    customer_id: int
    arrival_time: Optional[float] = None

class Route(BaseModel):
    vehicle_id: int
    stops: List[RouteStop]
    total_distance: float
    total_load: float

class VRPResponse(BaseModel):
    routes: List[Route]
    total_distance: float
    algorithm_used: str

@app.post("/optimize", response_model=VRPResponse)
async def optimize_routes(request: VRPRequest):
    """Optimize vehicle routes given customers and vehicles."""
    if len(request.customers) == 0:
        raise HTTPException(status_code=400, detail="At least one customer required")
    if len(request.vehicles) == 0:
        raise HTTPException(status_code=400, detail="At least one vehicle required")
    
    # Build distance matrix
    all_points = [request.depot] + request.customers
    n = len(all_points)
    dist_matrix = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            dx = all_points[i].x - all_points[j].x
            dy = all_points[i].y - all_points[j].y
            dist_matrix[i][j] = (dx * dx + dy * dy) ** 0.5
    
    # Run selected algorithm
    if request.algorithm == "savings":
        routes = clarke_wright_savings(dist_matrix, [c.demand for c in request.customers], request.vehicles[0].capacity)
    elif request.algorithm == "nearest":
        routes = nearest_neighbor_heuristic(dist_matrix, [c.demand for c in request.customers], request.vehicles[0].capacity)
    else:
        raise HTTPException(status_code=400, detail=f"Unknown algorithm: {request.algorithm}")
    
    # Format response
    response_routes = []
    total_dist = 0
    for i, route in enumerate(routes):
        if len(route) == 0:
            continue
        route_dist = 0
        prev = 0  # depot
        stops = []
        for customer_idx in route:
            dist = dist_matrix[prev][customer_idx + 1]  # +1 for depot offset
            route_dist += dist
            stops.append(RouteStop(customer_id=customer_idx))
            prev = customer_idx + 1
        # Return to depot
        route_dist += dist_matrix[prev][0]
        total_dist += route_dist
        total_load = sum(request.customers[c].demand for c in route)
        response_routes.append(Route(
            vehicle_id=i,
            stops=stops,
            total_distance=round(route_dist, 2),
            total_load=total_load
        ))
    
    return VRPResponse(
        routes=response_routes,
        total_distance=round(total_dist, 2),
        algorithm_used=request.algorithm
    )

Savings Algorithm

def clarke_wright_savings(dist_matrix, demands, capacity):
    """Clark-Wright savings algorithm for CVRP."""
    n = len(demands)
    if n == 0:
        return []
    
    # Calculate savings
    savings = []
    for i in range(n):
        for j in range(i + 1, n):
            s = dist_matrix[0][i + 1] + dist_matrix[0][j + 1] - dist_matrix[i + 1][j + 1]
            savings.append((s, i, j))
    savings.sort(reverse=True)
    
    # Initialize routes
    routes = [[i] for i in range(n)]
    route_demands = [demands[i] for i in range(n)]
    
    def find_route_idx(customer):
        for idx, r in enumerate(routes):
            if customer in r:
                return idx
        return -1
    
    # Merge routes by savings
    for s, i, j in savings:
        r_i = find_route_idx(i)
        r_j = find_route_idx(j)
        if r_i != r_j:
            merged_demand = route_demands[r_i] + route_demands[r_j]
            if merged_demand <= capacity:
                routes[r_i].extend(routes[r_j])
                routes.pop(r_j)
                route_demands[r_i] = merged_demand
                route_demands.pop(r_j)
    
    return routes

Nearest Neighbor Heuristic

def nearest_neighbor_heuristic(dist_matrix, demands, capacity):
    """Simple nearest neighbor heuristic for CVRP."""
    n = len(demands)
    unvisited = set(range(n))
    routes = []
    
    while unvisited:
        current = 0  # depot
        route = []
        load = 0
        
        while unvisited:
            nearest = None
            nearest_dist = float('inf')
            
            for c in unvisited:
                d = dist_matrix[current][c + 1]
                if d < nearest_dist and load + demands[c] <= capacity:
                    nearest = c
                    nearest_dist = d
            
            if nearest is None:
                break
            
            route.append(nearest)
            load += demands[nearest]
            unvisited.remove(nearest)
            current = nearest + 1
        
        if route:
            routes.append(route)
    
    return routes

Running the API

# Install dependencies
pip install fastapi uvicorn

# Start server
uvicorn main:app --reload --port 8000

# Test with curl
curl -X POST http://localhost:8000/optimize \
  -H "Content-Type: application/json" \
  -d '{
    "depot": {"id": 0, "demand": 0, "x": 0, "y": 0},
    "customers": [
      {"id": 1, "demand": 10, "x": 5, "y": 5},
      {"id": 2, "demand": 15, "x": 10, "y": 2},
      {"id": 3, "demand": 12, "x": 3, "y": 8},
      {"id": 4, "demand": 8, "x": 8, "y": 7}
    ],
    "vehicles": [{"id": 0, "capacity": 30}],
    "algorithm": "savings"
  }'

Summary

The VRP API exposes vehicle routing optimization as a web service. Implement multiple algorithms (savings, nearest neighbor, OR-Tools) and let users choose. Accept customer locations and demands, return optimized routes.

Key takeaways:

FastAPI endpoint accepts customer and vehicle data
Implement at least savings and nearest neighbor heuristics
Build distance matrix from coordinate data
Return ordered routes with total distance per route
Support CVRP and extend for VRPTW
Test with curl or Swagger UI (auto-generated)
The savings heuristic gives better quality than nearest neighbor

What's Next: Vehicle Routing Problem Intro

The next course covers the Vehicle Routing Problem introduction — types, variants, and real-world applications.