Route Optimization Engine for Delivery Services

An algorithmic engine that solves the Vehicle Routing Problem (VRP) for last-mile delivery optimization. Takes a list of delivery addresses and fleet parameters, and outputs optimal routes for each driver while respecting real-world constraints.

Features

• Distance Matrix Calculation using Haversine formula (great-circle distance)
• TSP Solver (single vehicle) with Nearest Neighbor heuristic and Google OR-Tools
• CVRP Solver (Capacitated VRP) for multi-vehicle routing with load constraints
• VRPTW Solver (VRP with Time Windows) for time-constrained deliveries
• Interactive Map Visualization using Folium with color-coded vehicle routes
• Cost-Benefit Analysis comparing optimized routes against naive baselines

Installation

pip install -r requirements.txt

Usage

Basic VRP (Capacity Constraints)

python main.py --csv data/deliveries.csv --vehicles 8 --capacity 25

VRP with Time Windows

python main.py --csv data/deliveries.csv --vehicles 5 --capacity 25 --time-windows

TSP Only (Single Vehicle)

python main.py --csv data/deliveries.csv --tsp-only

All Options

--csv           Path to CSV file with delivery locations (default: data/deliveries.csv)
--vehicles      Number of vehicles in the fleet (default: 8)
--capacity      Maximum capacity per vehicle (default: 25)
--time-windows  Enable time window constraints (VRPTW)
--tsp-only      Only solve TSP (single vehicle)
--output-dir    Output directory for results (default: output)
--time-limit    Solver time limit in seconds (default: 30)
--unit          Distance unit: km or miles (default: km)

CSV Format

The input CSV must include these columns:

Column	Description
order_id	Unique identifier (row 0 = depot)
latitude	Delivery latitude
longitude	Delivery longitude
demand	Number of units to deliver
time_window_start	Earliest delivery time (HH:MM)
time_window_end	Latest delivery time (HH:MM)

Output

The engine produces three deliverables:

1. output/optimized_route_map.html - Interactive Folium map with color-coded routes
2. output/baseline_route_map.html - Naive baseline routes for comparison
3. output/analysis_report.txt - Cost-benefit analysis with distance/fleet savings

Project Structure

route-optimization-engine/
├── main.py                  # CLI entry point
├── data/
│   └── deliveries.csv       # Sample delivery dataset (30 NYC locations)
├── src/
│   ├── distance_matrix.py   # Haversine distance computation
│   ├── tsp_solver.py        # TSP: Nearest Neighbor + OR-Tools
│   ├── vrp_solver.py        # CVRP and VRPTW solvers
│   ├── baseline.py          # Naive routing baselines
│   ├── visualizer.py        # Folium map generation
│   └── report.py            # Cost-benefit analysis report
└── requirements.txt

Algorithms

Distance Matrix

Uses the Haversine formula to calculate great-circle distances between GPS coordinates, accounting for Earth's curvature.

TSP (Traveling Salesman Problem)

• Nearest Neighbor Heuristic: Greedy algorithm that always visits the closest unvisited node
• OR-Tools with Guided Local Search: Meta-heuristic that iteratively improves the solution

CVRP (Capacitated Vehicle Routing Problem)

Uses Google OR-Tools to assign deliveries to vehicles while respecting maximum load capacity per vehicle.

VRPTW (VRP with Time Windows)

Extends CVRP by adding time constraints - each delivery must occur within a specified time window. Includes 5-minute service time per stop.

Technologies

• Python 3.12+
• Google OR-Tools - Combinatorial optimization solver
• Pandas / NumPy - Data handling and matrix computation
• Folium - Interactive map visualization
• NetworkX - Graph operations