Project 01 / Operations Research

FairRoute Optimizer

A constraint-based vehicle routing system implementing the Vehicle Routing Problem with Time Windows (VRPTW) using Google OR-Tools. The system optimizes multi-robot pickup routes while enforcing fairness constraints to ensure equitable service distribution across heterogeneous urban zones.

Problem Class NP-Hard Combinatorial Optimization
Solver OR-Tools CP-SAT + Guided Local Search
Complexity O(n! / (n-k)!) worst case
Interactive Demo Source Code
01

Problem Definition

Formal Problem Statement

The Vehicle Routing Problem with Time Windows (VRPTW) is defined on a complete directed graph G = (V, A) where V = {0, 1, ..., n} represents n customer nodes plus a depot node 0, and A represents arcs between all node pairs with associated costs and travel times.

Objective Function:

minimize Σk∈K Σ(i,j)∈A cij · xijk

Minimize total travel cost across all vehicles k in fleet K

Subject to:

  • Σk∈K Σj∈V xijk = 1, ∀i ∈ V\{0} — Each customer visited exactly once
  • Σi∈V di · yik ≤ Qk, ∀k ∈ K — Vehicle capacity constraints
  • ei ≤ si ≤ li, ∀i ∈ V — Time window constraints
  • Σj∈V x0jk = Σj∈V xj0k = 1, ∀k ∈ K — Route continuity

Computational Complexity

VRPTW belongs to the NP-hard complexity class. The search space grows factorially with problem size, making exact solutions intractable for instances beyond ~25 nodes. Our implementation uses metaheuristic approaches to find near-optimal solutions within practical time bounds.

Fairness Extension

Traditional VRPTW optimizes purely for efficiency. Our extension introduces zone-based penalty coefficients that prioritize historically underserved areas, transforming the single-objective problem into a weighted multi-objective formulation balancing efficiency and equity.

System Parameters

Parameter Value Unit Description
Vehicle Capacity (Q) 25 kg Maximum payload per robot before returning to depot
Battery Range (Dmax) 9,000 meters Maximum travel distance before recharge required
Fleet Size (|K|) 4 vehicles Number of homogeneous robots in fleet
Service Time (τ) 5 minutes Fixed duration for each pickup operation
Operating Window 06:00 - 20:00 hours Daily operational time bounds
Solver Time Limit 30 seconds Maximum computation time for metaheuristic
02

Algorithm Architecture

1

Model Construction

Build routing model with distance matrix, demand vector, and constraint dimensions

2

Initial Solution

Generate feasible starting solution using PATH_CHEAPEST_ARC heuristic

3

Metaheuristic Search

Iterative improvement via Guided Local Search with penalty-based diversification

4

Solution Extraction

Parse optimized routes, compute metrics, generate visualization

Guided Local Search (GLS)

GLS is a penalty-based metaheuristic that escapes local optima by augmenting the objective function. When trapped in a local minimum, GLS penalizes solution features (arcs) that appear frequently, encouraging exploration of alternative routes.

Objective Value Best Found Penalty Applied
Python solver_ortools.py 
def configure_search_parameters(time_limit: int = 30):
    """Configure metaheuristic search parameters."""
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    
    # Initial solution: greedy arc insertion
    search_params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    
    # Improvement: Guided Local Search
    search_params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    
    # Termination criteria
    search_params.time_limit.seconds = time_limit
    
    return search_params

Constraint Dimensions

OR-Tools models cumulative constraints through "dimensions" that track resource consumption along routes. Each dimension enforces bounds at every node.

Capacity Dimension

18kg 25kg

Tracks cumulative load. Service denied if adding demand exceeds vehicle capacity.

routing.AddDimensionWithVehicleCapacity(demand_callback, 0, [25]*4, True, 'Capacity')

Time Dimension

10:48
06:00 20:00

Tracks arrival time. Enforces time window [ei, li] at each stop.

time_dim.CumulVar(index).SetRange(tw_start, tw_end)

Distance Dimension

5.2km 9km

Tracks cumulative distance. Prevents routes exceeding battery range.

routing.AddDimension(distance_callback, 0, 9000, True, 'Distance')

Fairness Mechanism

Service equity is enforced through disjunction penalties—the cost incurred when a stop cannot be served. Higher penalties for underserved zones force the solver to prioritize those locations.

Zone Classification Penalty Multiplier Drop Penalty Rationale
Standard Service Area 1.0x 1,000 Baseline penalty for normal service areas
High Priority Zone 1.5x 1,500 Areas with recent service complaints
Underserved Zone 2.0x 2,000 Historically disadvantaged neighborhoods
Critical Priority 3.0x 3,000 Emergency or time-critical pickups
Python solver_ortools.py 
def add_fairness_constraints(routing, manager, stops):
    """Add zone-based fairness penalties."""
    for idx, stop in enumerate(stops):
        node_index = manager.NodeToIndex(idx + 1)  # +1 for depot offset
        
        # Determine penalty based on zone classification
        zone = stop.get('zone', 'standard')
        penalty = {
            'standard': 1000,
            'high_priority': 1500,
            'underserved': 2000,
            'critical': 3000
        }.get(zone, 1000)
        
        # Allow dropping stop, but at significant cost
        routing.AddDisjunction([node_index], penalty)
03

Interactive Demonstration

Configure parameters and observe the optimization process in real-time. The visualization shows stop locations, computed routes, and live performance metrics.

Configuration

25
4
25
50%

Live Metrics

Status Ready
Iteration 0
Total Distance --
Stops Served --
Gini Index --
Robot 1 --
Robot 2 --
Robot 3 --
Robot 4 --

Algorithm Comparison

Greedy Nearest Neighbor

Baseline
-- Total Distance
-- Stops Served
-- Compute Time
vs

OR-Tools VRPTW

Optimized
-- Total Distance
-- Stops Served
-- Compute Time
Configure parameters and run optimization to see comparison results
04

Performance Benchmarks

Empirical evaluation across varying problem sizes, constraint configurations, and solver time limits. All benchmarks conducted on Apple M1 Pro with 16GB RAM.

Scalability Analysis

Solver performance as a function of problem size (number of pickup stops) with fixed fleet size of 4 vehicles.

O(n2) Practical Complexity
~100 stops 60s Time Limit
25-50 stops Optimal Range

Solution Quality Over Time

Objective value improvement as solver runtime increases. Demonstrates diminishing returns beyond 30 seconds for typical problem sizes.

~25% Initial Gap
~10% Gap at 5s
<3% Gap at 30s

Detailed Performance Metrics

Comprehensive comparison between greedy baseline and OR-Tools optimized solution for a 25-stop, 4-vehicle instance.

Metric Greedy Baseline OR-Tools (GLS) Improvement
Total Distance 18.42 km 14.18 km -23.0%
Stops Served 23 / 25 25 / 25 +8.7%
Max Route Length 6.21 km 4.12 km -33.7%
Max Vehicle Load 24.5 kg 22.1 kg -9.8%
Workload Gini 0.182 0.078 -57.1%
Zone Fairness Score 0.721 0.912 +26.5%
Time Window Violations 3 0 -100%
Computation Time 0.018 s 12.4 s +688x

Fleet Workload Distribution

Comparison of distance and load balance across the robot fleet. Lower Gini coefficient indicates more equitable workload distribution.

Baseline

R1
5.8 km
R2
6.2 km
R3
3.6 km
R4
2.8 km
Gini: 0.182

Optimized

R1
3.9 km
R2
3.6 km
R3
4.1 km
R4
3.2 km
Gini: 0.078
05

Implementation Details

System Architecture

Input Layer
generate_data.py

Synthetic data generation with configurable zone distributions

demand_forecast.py

RandomForest-based demand prediction

Optimization Layer
solver_ortools.py

Core VRPTW solver with constraint handling

baseline_greedy.py

Nearest-neighbor heuristic baseline

Output Layer
metrics.py

Gini coefficient and fairness calculations

viz.py

Route visualization and comparison charts

Dependencies

ortools 9.10.4067

Google OR-Tools constraint programming solver

numpy ≥1.24.0

Numerical computing for distance matrices

pandas ≥2.0.0

Data manipulation and result aggregation

matplotlib ≥3.7.0

Route visualization and performance charts

scikit-learn ≥1.3.0

Demand forecasting with RandomForest

scipy ≥1.11.0

Spatial distance and statistical functions

Quick Start

1

Installation

git clone https://github.com/your-repo/fairroute-optimizer.git
cd fairroute-optimizer
pip install -r requirements.txt
2

Run Experiment

python src/run_experiment.py --stops 25 --robots 4 --time-limit 30
Expected Output: 
Generating 25 stops across 4 zones...
Running baseline (greedy) solver...
Running OR-Tools VRPTW solver...

=== RESULTS ===
Baseline: 18.42 km | 23/25 served
Optimized: 14.18 km | 25/25 served
Improvement: 23.0% distance reduction
3

Programmatic API

from solver_ortools import VRPTWSolver
from generate_data import generate_stops

stops = generate_stops(num_stops=50, seed=42)
depot = {'x': 0.5, 'y': 0.5}

solver = VRPTWSolver(
    num_vehicles=4,
    vehicle_capacity=25,
    max_distance=9000,
    time_limit_seconds=30
)

solution = solver.solve(stops, depot)
print(f"Distance: {solution.total_distance:.2f} km")

Command Line Interface

Option Type Default Description
--stops int 25 Number of pickup stops to generate
--robots int 4 Number of robots in fleet
--time-limit int 30 Solver time limit in seconds
--capacity int 25 Vehicle capacity in kg
--max-distance int 9000 Maximum distance per robot (meters)
--seed int None Random seed for reproducibility