VRP Basics

🔥 Vibe Prompt

"Solve a TSP with 9 locations using OR-Tools Routing. 3 vehicles, minimize total distance."

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

def create_data_model():
    data = {"distance_matrix": [[0,548,...],[548,0,...],...], "num_vehicles": 3, "depot": 0}
    return data

def solve_vrp():
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data["distance_matrix"]), data["num_vehicles"], data["depot"])
    routing = pywrapcp.RoutingModel(manager)
    
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    
    solution = routing.SolveWithParameters(search_parameters)
    return solution, manager, routing, data

Course Summary

This chapter covers the journey from the classic Traveling Salesman Problem (TSP) to the full Vehicle Routing Problem (VRP).

Chapter Summary

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

Further Reading

• Official documentation and API references
• Open source examples on GitHub
• Technical books and online courses
• Community discussions and tech blogs

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

1. Setup: Configure development environment
2. Data: Prepare required data
3. Implementation: Build core functionality
4. Testing: Verify correctness
5. 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()

Summary

The Vehicle Routing Problem (VRP) optimizes routes for a fleet of vehicles to serve customer demands. It extends the Traveling Salesman Problem (TSP) by adding multiple vehicles, capacity constraints, and time windows. VRP is NP-hard and requires approximation or metaheuristic approaches for practical instances.

Key takeaways:

• VRP = find optimal routes for fleet of vehicles
• Each vehicle starts and ends at a depot
• Each customer is visited exactly once
• Vehicles have capacity limits (CVRP)
• Customers have time windows (VRPTW)
• VRP is NP-hard — use heuristics or metaheuristics
• Real applications: logistics, delivery, waste collection
• Small instances (10-20 customers): exact solvers (OR-Tools)
• Large instances (100+ customers): heuristic approaches

Applications

| Industry | Application | |----------|-------------| | Logistics | Package delivery route optimization | | Food Delivery | Optimize delivery routes for multiple drivers | | Public Transit | Bus route and schedule optimization | | Waste Collection | Optimize garbage truck routes | | Field Service | Route optimization for repair technicians | | Emergency Services | Ambulance and police vehicle routing | | Supply Chain | Distribution and replenishment routing |

VRP vs. TSP

| Aspect | TSP | VRP | |--------|-----|-----| | Vehicles | 1 | Multiple | | Capacity | Unlimited | Limited | | Time Windows | None | Optional | | Depot | Start = End | All start/end at depot | | Complexity | NP-hard | NP-hard (harder) | | Realism | Simplified | Real-world constraints |

CVRP (Capacitated VRP)

Capacitated VRP adds vehicle capacity constraints. Each vehicle has a maximum load it can carry.

# Simple CVRP formulation
# Given:
#   - depot at location 0
#   - n customers with demands d[i]
#   - K vehicles with capacity Q
#   - distance matrix dist[i][j]
# Find:
#   - K routes minimizing total distance
#   - Each route starts and ends at depot
#   - Total demand on each route <= Q
#   - All customers visited exactly once

VRPTW (VRP with Time Windows)

VRPTW adds a time window [e[i], l[i]] for each customer. The vehicle must arrive within this window.

# VRPTW additional constraints:
#   - arrival_time[i] >= e[i] (earliest)
#   - arrival_time[i] <= l[i] (latest)
#   - waiting allowed (arrive early, wait)
#   - service_time[i] at each customer
#   - total route time <= vehicle max time

Solution Approaches

| Approach | Type | Quality | Speed | |----------|------|---------|-------| | Clark-Wright Savings | Heuristic | Good | Fast | | Nearest Neighbor | Heuristic | Fair | Very fast | | OR-Tools CP-SAT | Exact | Optimal | Slow (small only) | | Genetic Algorithm | Metaheuristic | Very good | Medium | | Simulated Annealing | Metaheuristic | Very good | Medium | | Ant Colony Optimization | Metaheuristic | Very good | Slow | | Large Neighborhood Search | Metaheuristic | Excellent | Medium |

Clark-Wright Savings Algorithm

def clarke_wright_savings(depot, customers, capacity):
    """
    Classic savings heuristic for CVRP.
    
    Savings: s[i][j] = dist[depot][i] + dist[depot][j] - dist[i][j]
    Higher savings = more beneficial to combine i and j on one route.
    """
    n = len(customers)
    savings = []
    
    for i in range(n):
        for j in range(i + 1, n):
            saving = (dist[depot][i] + dist[depot][j] - dist[i][j])
            savings.append((saving, i, j))
    
    savings.sort(reverse=True)  # Largest savings first
    
    # Initialize each customer as its own route
    routes = [[i] for i in range(n)]
    route_demand = [demands[i] for i in range(n)]
    
    for saving, i, j in savings:
        # Find which routes contain i and j
        route_i = find_route(routes, i)
        route_j = find_route(routes, j)
        
        if route_i != route_j:
            # Check if merging is feasible
            merged_demand = route_demand[route_i] + route_demand[route_j]
            if merged_demand <= capacity:
                # Merge routes (ensure depot at each end)
                routes[route_i].extend(routes[route_j])
                routes.pop(route_j)
                route_demand[route_i] = merged_demand
                route_demand.pop(route_j)
    
    return routes

Summary

VRP optimizes routes for a fleet of vehicles. CVRP adds capacity constraints, VRPTW adds time windows. Real-world logistics problems are VRP variants. Use simple heuristics (Clark-Wright) for fast solutions, metaheuristics for high quality, and exact solvers (OR-Tools) only for small instances.

Key takeaways:

• VRP = fleet route optimization
• CVRP = capacity-constrained VRP
• VRPTW = VRP with time windows
• Clark-Wright: classic savings heuristic
• VRP is NP-hard — exact solutions only for small instances
• Metaheuristics (GA, SA, LNS) give best quality
• Applications: logistics, delivery, waste collection, field service

What's Next: CVRP (Capacitated VRP)

The next chapter implements the Capacitated VRP with vehicle capacity constraints and route optimization.