# Vehicle Routing Problems (VRP)
This document provides a comprehensive overview of Vehicle Routing Problems (VRPs), focusing on the Capacitated VRP (CVRP) and the VRP with Time Windows (VRPTW). It also demonstrates how to solve these problems using Google's OR-Tools library in Python.

## Introduction to Vehicle Routing Problems (VRPs)
Vehicle Routing Problems (VRPs) are a class of optimization problems that focus on finding the most efficient set of routes for a fleet of vehicles to serve a set of customers. These problems arise in a wide range of real-world scenarios, from delivering goods and collecting waste to providing transportation services. At their core, VRPs seek to minimize total travel costs (e.g., distance, time, or fuel consumption) while satisfying various constraints.

### Key Elements of a VRP
* **Customers:** A set of locations that need to be served by the vehicles. Each customer typically has a demand for goods or services.
* **Depots:** One or more central locations where the vehicles start and end their routes.
* **Vehicles:** A fleet of vehicles with potentially different capacities, costs, and characteristics.
* **Road Network:** The underlying transportation network connecting the depots and customers, often represented by a graph with nodes and edges.
* **Constraints:** Limitations and requirements that must be met, such as:
* **Vehicle Capacity:** The maximum amount of goods a vehicle can carry.
* **Time Windows:** Specific time intervals within which customers must be served.
* **Delivery and Pickup:** Some customers may require both delivery and pickup services.
* **Route Duration:** Limits on the total duration or distance of a route.
* **Driver Schedules:** Constraints related to driver working hours and breaks.

### Objective
The primary objective of a VRP is to minimize the total cost associated with serving all customers. This cost can be defined in various ways, including:

* **Total distance traveled**
* **Total travel time**
* **Total fuel consumption**
* **Number of vehicles used**
* **A combination of these factors**

VRPs are computationally complex problems, and finding optimal solutions can be challenging. However, efficient algorithms and optimization techniques have been developed to solve VRPs effectively, leading to significant cost savings and improved efficiency in logistics and transportation operations.

## Mathematical Formulation of VRPs
While the concept of VRPs is easy to grasp, their mathematical representation is essential for applying optimization algorithms. We can formally describe VRPs using graph theory and mathematical notation.

### Graph Representation
A VRP is typically modeled as a directed graph $G = (V, A)$, where:

* $V = \{0, 1, \dots, n\}$ is the set of vertices (nodes).
* Node $0$ represents the depot.
* Nodes $1$ to $n$ represent the customers.
* $A$ is the set of arcs (directed edges) connecting the vertices.
* A non-negative cost, $c_{ij}$, is associated with each arc $(i, j) \in A$, representing the travel cost (distance, time, etc.) from vertex $i$ to $j$.

### Decision Variables
The core decisions in a VRP involve determining which customer is served by which vehicle and in what order. This is often represented using binary variables:

* **Two-index formulation:** $x_{ij}=1$ if a vehicle travels from node $i$ to $j$, and $0$ otherwise. This is commonly used in simpler VRPs.
* **Three-index formulation:** $x_{ijk}=1$ if vehicle $k$ travels from node $i$ to $j$, and $0$ otherwise. This is used when dealing with multiple vehicles and more complex constraints.

### Objective Function
The primary objective is to minimize the total cost of the routes. This is expressed as:

$$
\max \sum_{(i,j) \in A} c_{ij} x_{ij} \quad \text{or} \quad \max \sum_{(i,j) \in A} c_{ij} x_{ijk}
$$

This formula sums the cost of all arcs that are traversed by the vehicles.

### Constraints
Various constraints ensure the feasibility and correctness of the solution:

* **Degree Constraints:** Each customer must be visited exactly once:
\begin{split}
\sum_{(i,j) \in A} x_{ij} = 1 \quad &\text{for all } j \in \{1, \dots, n\} \ &&\text{(incoming to customer j)} \\
\sum_{(i,j) \in A} x_{ij} = 1 \quad &\text{for all } i \in \{1, \dots, n\} &&\text{(outgoing from customer i)}
\end{split}
* **Depot Constraints:** Each vehicle must start and end at the depot:
$$
\sum_{(0,j) \in A} x_{0j} = K \quad (K = \text{number of vehicles leaving the depot})
$$
* **Capacity Constraints (CVRP):** The total demand served by a vehicle on a route cannot exceed its capacity $Q$: $$\sum_{(i,j) \in A} q_j x_{ij} \leq Q \quad \text{for all vehicles}$$ where $q_j$ is the demand of customer $j$.
* **Time Window Constraints (VRPTW):** Each customer $i$ must be served within a specific time window $[a_i, b_i]$. This requires introducing additional variables and constraints to track the arrival time of vehicles at each node.
* **Subtour Elimination Constraints:** These constraints prevent the formation of subtours (cycles that do not include the depot), which are invalid in a VRP solution.

## Types of VRPs
The basic VRP model can be extended in numerous ways to incorporate real-world constraints and complexities. Here are some of the most common types of VRPs:

### Capacitated Vehicle Routing Problem (CVRP)
The CVRP is one of the most fundamental VRP variants. In this problem, each vehicle has a limited carrying capacity (denoted as $Q$), and each customer i has a specific demand for goods $q_i$. The routes must be designed so that the total demand on any route does not exceed the capacity of the vehicle assigned to that route.

### Vehicle Routing Problem with Time Windows (VRPTW)
The VRPTW extends the CVRP by adding time constraints. Each customer $i$ has a specified time window $[a_i, b_i]$ within which the delivery must be made. This adds complexity to the problem, as the routes must consider both travel times between customers and service times at each customer to ensure that all time windows are met.

### Vehicle Routing Problem with Pickup and Delivery (VRPPD)
In the VRPPD, vehicles not only deliver goods to customers but also pick up goods from certain locations. This is common in scenarios like courier services, where packages need to be collected and delivered.

### Vehicle Routing Problem with Multiple Depots (MDVRP)
The MDVRP involves multiple depots from which vehicles can originate. This is relevant for companies with multiple distribution centers or service centers. The problem involves assigning vehicles to depots and then planning routes from those depots.

### Vehicle Routing Problem with Heterogeneous Fleet (HVRP)
In the HVRP, the fleet of vehicles is not identical. Vehicles may have different capacities, costs, speeds, or other characteristics. This adds another layer of complexity, as the selection of the appropriate vehicle for each route becomes a crucial part of the optimization.

### Vehicle Routing Problem with Backhauls (VRPB)
The VRPB involves two types of customers: linehaul customers (who receive deliveries) and backhaul customers (who have goods picked up). This problem often arises in scenarios where vehicles transport goods to customers and then return to the depot with collected items.

### Other Variants
There are many other specialized VRP variants, including:
* **VRP with Open Routes:** Routes don't have to end at the depot.
* **VRP with Stochastic Demands:** Customer demands are uncertain.
* **VRP with Dynamic Routing:** New customer requests arrive during the operation.
* **VRP with Drone Delivery:** Incorporating drones for last-mile delivery.

The choice of which VRP variant to use depends on the specific characteristics and constraints of the real-world problem being addressed.

<font color=red>Add concrete optimization problems</font>

## Solving VRPs with OR-Tools
Google's OR-Tools is a powerful open-source software suite for optimization, providing a flexible and efficient framework for tackling various types of VRPs. It offers solvers for constraint programming, linear programming, and mixed-integer programming, along with dedicated tools for routing problems.

Here's a breakdown of how to use OR-Tools to solve VRPs in Python:

### Installation
Make sure you have the necessary libraries installed:

# Installation
pip install ortools
pip install osmnx  # Optional, for obtaining road network data

### Import Libraries
Import the required modules in your Python script:

# Import Libraries
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import osmnx as ox  # If you're using osmnx for map data
import networkx as nx  # If you're using networkx for graph operations

### Data Preparation
* **Distance Matrix:** Prepare a distance matrix (`distance_matrix`) representing the travel costs between all pairs of locations (depot and customers). You can obtain this data from various sources:
* **Direct Input:** If you have a small number of locations, you can input the distances manually.
* **Road Network Data:** Use libraries like `osmnx` to download road network data and calculate shortest path distances using algorithms like Dijkstra's or Floyd-Warshall.
* **Distance Matrix API:** Utilize services like the Google Maps Distance Matrix API to obtain real-world distances or travel times.
* **VRP Parameters:** Define the parameters specific to your VRP:
* `num_vehicles:` The number of vehicles in your fleet.
* `depot`: The index of the depot location in your `distance_matrix`.
* `demands` (for CVRP): A list of demands for each customer.
* `vehicle_capacities` (for CVRP): A list of capacities for each vehicle.
* `time_windows` (for VRPTW): A list of time windows for each location.
* `time_matrix` (for VRPTW): A matrix of travel times between locations.

### OR-Tools Model Building
#### Create Routing Index Manager

# Create Routing Index Manager
manager = pywrapcp.RoutingIndexManager(len(distance_matrix), num_vehicles, depot)

#### Create Routing Model

# Create Routing Model
routing = pywrapcp.RoutingModel(manager)

#### Register Transit Callback
Define a function (`distance_callback`) that takes two location indices and returns the distance between them. Register this function with the routing model:

# Register Transit Callback
def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return distance_matrix[from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

#### Add Constraints

# Add Capacity Constraints (for CVRP)
def demand_callback(from_index):
    """Returns the demand of the node."""
    from_node = manager.IndexToNode(from_index)
    return demands[from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index,
    0,  # null capacity slack
    vehicle_capacities,  # vehicle maximum capacities
    True,  # start cumul to zero
    'Capacity'
)

# Add Time Window Constraints (for VRPTW)
routing.AddDimension(
    transit_callback_index,
    30,  # allow waiting time
    30,  # maximum time per vehicle
    False,  # Don't force start cumul to zero.
    'Time'
)
time_dimension = routing.GetDimensionOrDie('Time')

# Add time window constraints for each location except depot
for location_idx, time_window in enumerate(time_windows):
    if location_idx == depot:
        continue
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

#### Set First Solution Strategy
Choose a heuristic to find an initial solution:

# Set First Solution Strategy
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)

## Solution and Visualization
Once you've solved a VRP using OR-Tools, the next steps are to extract the solution details and visualize the results. This helps in understanding the optimized routes, analyzing their efficiency, and communicating the solution to stakeholders.

### Solution Extraction
After solving the routing model, you'll have a `solution` object. You can use this object to retrieve information about the routes assigned to each vehicle. Here's an example of how to extract the routes and their associated costs:

# Extract Solution
if solution:
    print(f"Total distance of all routes: {solution.ObjectiveValue()}m")
    for vehicle_id in range(num_vehicles):
        index = routing.Start(vehicle_id)
        route_distance = 0
        route = []
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route.append(node_index)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        route.append(manager.IndexToNode(index))  # Append the depot to complete the route
        print(f"Route for vehicle {vehicle_id}:\n {route}\nDistance of the route: {route_distance}m")
else:
    print('No solution found!')

This code snippet iterates through each vehicle and extracts the sequence of nodes visited on its route. It also calculates the total distance traveled by each vehicle.

### Visualization with `osmnx`
Visualizing the solution on a map provides a clear and intuitive representation of the routes. The `osmnx` library is a valuable tool for this purpose. Here's how you can use it:

# Visualization with osmnx
# Assuming you have a map object called 'map' and a list of routes
routes_nodes = [[nodes[i] for i in route] for route in routes]

# Plot the routes on the map
fig, ax = ox.plot_graph_routes(map, routes_nodes, route_colors=['r', 'g', 'b', 'c'])
plt.show()

This code snippet uses `ox.plot_graph_routes()` to overlay the routes on the map. You can customize the appearance of the routes by specifying different colors or line styles.

### Advanced Visualization
You can further enhance the visualization by:

* **Adding markers:** Place markers on the map to indicate the depot and customer locations.
* **Displaying route information:** Show route distances, travel times, or other relevant details on the map.
* **Interactive maps:** Create interactive maps using libraries like `folium` to allow users to zoom, pan, and explore the routes in more detail.

By combining solution extraction with effective visualization techniques, you can gain valuable insights into the optimized routes, identify potential areas for improvement, and effectively communicate the results of your VRP analysis.

## Reference
<font color=red>Add reference</font>