An Enterprise-Grade Vehicle Routing Problem (VRP) Solver with Time Windows & Heterogeneous Fleet Constraints
This repository implements a production-grade daily route optimization engine for a heterogeneous last-mile delivery fleet. It models and solves a Capacitated Vehicle Routing Problem with Soft Time Windows and Heterogeneous Fleet (CVRP-STW-HF) — a well-studied, NP-hard class of Operations Research problem — using PyVRP's Hybrid Genetic Search metaheuristic.
Given a morning's orders, a fleet roster, and a set of business rules (vehicle capacities, customer time windows, restricted-zone rules, driver hours-of-service limits), the engine produces a complete, cost-minimized dispatch plan: which truck serves which orders, in what sequence, with what timing — exported to a full Excel dispatch pack, and explorable through an interactive Streamlit dashboard with a live GIS map.
Note: every dataset in this repository is synthetic. See the Disclaimer & Context section at the bottom.
| Data Setup & Fleet Hub | Optimization Engine | Executive Control Tower |
|---|---|---|
 |
 |
 |
- Dynamic Territory Planning — for large instances (200+ orders), the problem is automatically decomposed via weighted K-Means clustering into independent geographic zones. Each zone is solved as its own sub-VRP with a proportional share of the fleet, followed by a rescue round that re-attempts any cross-zone leftovers with unused capacity — keeping solve times tractable without sacrificing solution quality.
- Strict Constraint Enforcement — hard business rules are enforced by
construction, not by hope:
- Restricted-zone / trailer-ban compatibility — large trailers are only routed to geographically eligible ("outside-zone") customers, modeled via per-vehicle-class edge profiles with prohibitive-cost edges into incompatible stops.
- Hours-of-service limits — each driver's cumulative time across all trips in a day (not per-trip) is capped at a configurable shift limit, with overtime priced explicitly, not silently absorbed.
- Multi-trip / depot reload logic — vehicles can run multiple trips per day, with real reload time charged at the depot between trips.
- Vehicle–customer compatibility — capacity, forklift availability, and truck-type requirements are respected per stop.
- Date-Aware, Priority-Weighted Dispatch — orders overdue by 2+ days are automatically promoted to mandatory status (a boosted prize in the objective), so the solver defers them only when truly unavoidable, while future-dated orders are excluded from the current day's run entirely.
- Prize-Collecting Order Acceptance — when total demand exceeds fleet capacity, orders become optional "prizes" the solver may decline to serve, weighted by customer priority — so capacity shortfalls are resolved by the algorithm, not by an ad-hoc cutoff.
- Interactive GIS Dashboard — a filterable Streamlit + Pydeck map renders every route with directional arrows, per-zone/per-trip coloring, and a live-updating KPI panel (OTIF, cost breakdown, utilization, fulfillment rate) that recomputes from whatever slice of the plan is currently filtered.
- Graceful Data-Quality Handling — a 3-tier missing-data cascade (derive sensible defaults → ask the user → skip-and-continue a single bad row) means one malformed row never blocks the entire day's plan.
The objective function jointly minimizes dispatch and operating cost while rewarding service coverage, weighted by a prize-collecting mechanism so the solver can make a principled trade-off between "serve this order" and "the cost of serving it":
Min Z = Σ dispatch_cost × vehicles_used
+ Σ fuel_cost × distance_km
+ Σ labor_cost × regular_hours
+ Σ overtime_cost × overtime_hours
+ Σ (1 / priority) × late_penalty × [late]
− Σ serve(order) × prize(order) (skipping an order forfeits its prize)
| # | Constraint | Type |
|---|---|---|
| C1 | Each order served by exactly one vehicle, no split delivery | Hard |
| C2 | Vehicle pallet capacity | Hard |
| C3 | Customer time windows | Soft (live search penalty + reported cost) |
| C4 | Driver maximum working hours (cumulative across all trips) | Hard |
| C5 | Trailers restricted to outside-zone customers only | Hard |
| C6 | Multi-trip reload time at depot | Hard |
| C7 | Orders are optional; every order left unserved forfeits its prize | Hard (cost structure) |
| C8 | 2+ day overdue orders get a boosted prize, deferred only when unavoidable | Soft (near-hard) |
Full derivation: docs/MATHEMATICAL_MODEL.md.
Solver: PyVRP 0.13+, a Hybrid Genetic Search (HGS) metaheuristic purpose-built for VRP variants — chosen after an OR-Tools CP-SAT implementation proved unable to converge on this problem's multi-trip continuity constraint at the target problem scale (see docs/CHANGELOG.md for the full technical writeup).
| Component | Technology |
|---|---|
| Solver / OR engine | PyVRP (Hybrid Genetic Search) |
| Backend | Python, pandas, NumPy, geopy |
| Frontend | Streamlit, Plotly, Pydeck (GIS map) |
| Clustering | scikit-learn (K-Means) |
| Data I/O | openpyxl, xlsxwriter |
# 1. Clone the repository
git clone <YOUR_REPO_URL>
cd last-mile-logistics-optimizer
# 2. Install dependencies
pip install -r requirements.txt
# 3. Launch the app
streamlit run app.pyUpload data/sample/LastMile_Sample_Data.xlsx when the app opens — it
solves in a few seconds and demonstrates the full workflow, including
overdue/mandatory order prioritization.
For a Territory Planning demo (200+ orders, multiple geographic zones),
upload data/sample/LastMile_StressTest_Sample.xlsx instead — this is a
genuinely large instance, so expect the solve itself to take several
minutes.
Both sample workbooks are fully synthetic and regeneratable:
python scripts/generate_sample_data.py # 100 orders, 50 customers, 12 vehicles
python scripts/generate_stress_test.py # 2,500 orders, 300 customers, 75 vehiclesOrder dates are generated relative to today, so re-running either script refreshes the demo's overdue/mandatory scenario to the current date.
├── app.py # Streamlit entry point
├── src/pipeline.py # Core: data loading, model building, solving (backend, no Streamlit imports)
├── ui/ # Streamlit pages (data setup, optimizer, dashboard) + shared state/branding
├── data/sample/ # Anonymized, regeneratable demo datasets
├── scripts/ # Sample/stress-test data generators
├── docs/ # Technical docs, user guide, math model, changelog
└── assets/ # Screenshots
- Technical Documentation — Architecture, API reference, constraint implementation
- User Guide — Step-by-step operations manual
- Mathematical Model — Full formulation
- Changelog — Version history
MIT License — see LICENSE for details.
Disclaimer & Context: This project was developed as an independent portfolio piece, inspired by the practical logistical challenges and operational scale observed during a cooperative training program at Tania Water Company. All datasets, coordinates, customer names, and cost parameters included in this repository are entirely 100% synthetic dummy data generated for demonstration purposes. This repository does not contain any proprietary source code, confidential operational data, or internal systems. It is a strictly educational showcase of Industrial Engineering and Operations Research concepts applied to Last-Mile Logistics.