Traffic OD Estimator & Vehicle Routing Pipeline

A complete pipeline for estimating Origin-Destination (OD) matrices from traffic sensor counts and solving Capacitated Vehicle Routing Problems (CVRP) using those estimates — with full hyperparameter tuning, robustness testing, and error propagation analysis.

---

Table of Contents

• Overview
• The Problem
• Methodology
  • Phase A: OD Estimation
  • Phase B: Vehicle Routing (CVRP)
  • Phase C: Hyperparameter Tuning
• Key Findings
  • L1 vs L2 Regularization
  • Error Propagation to Routing
• Performance Summary
• Setup & Usage
• Project Structure

---

Overview

In transportation planning, we rarely know the actual travel demand between locations. What we do have are traffic sensor counts on road segments. This project tackles the inverse problem: given traffic counts on links, estimate where people are actually traveling from and to, and then route a delivery fleet based on those estimates.

The pipeline covers:

1. Network simulation — Random city graph generation with configurable noise
2. OD estimation — Convex optimization with L1/L2 regularization
3. Hyperparameter tuning — K-Fold Cross-Validation on link counts
4. Fleet routing — Capacitated VRP via Google OR-Tools
5. Robustness testing — Across seeds, noise levels, regularization weights, and network scales

---

The Problem

OD estimation is a severely underdetermined system. The number of unknown OD pairs ($n^2$) far exceeds the number of observed link counts. Mathematically:

$$P \times OD = \texttt{link counts}$$

where $P$ is the assignment matrix mapping OD flows to links via shortest paths. Because the system is underdetermined, infinitely many OD matrices produce the exact same sensor readings. This means:

Matching the sensors perfectly does not mean you have found the true traffic pattern.

We prove this by computing the Singular Value Decomposition (SVD) of $P$, revealing a non-trivial null space — any vector in this null space can be added to a valid solution without changing the observed traffic counts.

---

Methodology

Phase A: OD Estimation

We formulate OD estimation as a constrained convex optimization problem using cvxpy:

$$\min_{OD} ; \lVert P \cdot OD - c \rVert_2^2 + \lambda \cdot R(OD) \quad \textrm{s.t.} \quad OD \geq 0$$

where $R(OD)$ is the regularization term:

• L1 (Lasso): $R(OD) = \lVert OD \rVert_1$ — promotes sparsity
• L2 (Ridge): $R(OD) = \lVert OD \rVert_2^2$ — promotes smoothness

Solver selection is delegated to cvxpy's auto-detection. L1 creates a Second-Order Cone Program (solved by ECOS), while L2 creates a Quadratic Program (solved by OSQP). This ensures optimal solver-problem matching without hardcoding.

Baseline (un-tuned, λ=0.5): True vs Estimated OD trips under L1 and L2, in low-noise and high-noise environments.

After CV tuning: L2 error drops significantly (21.4% → 14.6% in low noise), while L1 remains unchanged.

Phase B: Vehicle Routing (CVRP)

The estimated OD matrix feeds into a Capacitated Vehicle Routing Problem. Destination demands are computed by summing incoming trips (column sums of the OD matrix). The solver uses Google OR-Tools with three initial heuristic strategies tested in parallel:

Strategy	Description
Path Cheapest Arc	Greedy nearest-neighbor extension
Savings	Clarke-Wright savings algorithm
Christofides	Approximation algorithm for TSP-like problems

Each strategy is refined with Guided Local Search metaheuristics. The best solution across all strategies is returned.

Fleet routes planned by the CVRP solver on the simulated city network.

Phase C: Hyperparameter Tuning

Instead of guessing $\lambda$, we find it automatically using K-Fold Cross-Validation on observed link counts:

1. Split sensor edges into $K$ train/test folds
2. Estimate OD using only training edges for each candidate $\lambda$
3. Measure Mean Absolute Error (MAE) on held-out test edges
4. Select the $\lambda$ that minimizes test MAE

This approach requires no access to the true OD matrix — it tunes purely from observable data.

---

Key Findings

L1 vs L2 Regularization

We discovered a critical asymmetry between L1 and L2 regularization under cross-validation tuning:

Scenario	Regularization	Naive Error (λ=0.5)	Tuned Error	Improvement
Low Noise	L1 (Lasso)	14.8%	14.8%	0.0%
Low Noise	L2 (Ridge)	21.4%	14.6%	+6.8%
High Noise	L1 (Lasso)	46.1%	45.9%	+0.2%
High Noise	L2 (Ridge)	33.0%	34.7%	-1.7%

Why L1 cannot be tuned via CV:

Under the non-negativity constraint ( $OD \geq 0$ ), the L1 penalty simplifies to a linear sum $\lambda \sum OD_{ij}$, acting purely as volume shrinkage. This makes the CV objective monotonically decreasing in $\lambda$, forcing the tuner to always select the smallest possible value. The regularization effectively cannot be tuned — we call this the Non-Negative Monotonicity Trap.

The pragmatic trade-off:

• L1 is naturally suited to sparse real-world traffic and outperforms L2 with default parameters
• L2 can be automatically tuned via CV to dynamically adapt to any noise environment, making it the only regularization that scales robustly across operating conditions

Average OD estimation error across 5 randomly simulated cities: un-tuned (λ=0.5) vs CV-tuned.

Error Propagation to Routing

OD estimation errors propagate directly into fleet routing decisions. Under high noise with binding vehicle capacities:

Scenario	Planned Distance	Realized Distance	Capacity Overflows	Penalty
Ideal (True OD)	161	161	0	Baseline
Tuned L2 (λ=0.4281)	170	170	0	+5.6%
Naive L2 (λ=0.5000)	155	188	1	+16.8%

When the estimator underestimates demand, the VRP solver plans an optimistic route that looks cheaper than ideal. But in the field, trucks hit capacity limits, forcing unplanned depot returns — exploding the realized cost by +16.8%. Proper tuning avoids this entirely, saving 10.6% in total fleet distance.

Hyperparameter tuning is not just a mathematical refinement — it directly prevents costly operational failures in routing.

---

Performance Summary

Across the robustness test suite (varying seeds, noise, regularization, and scale):

Metric	Average Result	Description
Reconstruction Error (MAE)	~1.5 – 2.5 cars	Match quality against observed sensors
True OD Error (Relative)	~15% – 25%	Accuracy against hidden ground truth
Logistics Penalty (VRP Cost)	~5% – 15% worse	Extra fleet distance from estimation errors

---

Setup & Usage

Requirements

• Python 3.9+

Install Dependencies

pip install -r requirements.txt

Run the Notebook (Main Entry Point)

jupyter notebook main.ipynb

Open in browser and run all cells (Kernel > Restart & Run All).

Run Headless Robustness Tests

# Without VRP (fast)
python tester.py

# With VRP solver included (slower)
python tester.py --vrp

---

Project Structure

File	Description
main.ipynb	Main entry point. Full pipeline with interactive visualizations.
generator.py	Random city graph, True OD matrix, and sensor link count generation.
estimator.py	OD estimation via L1/L2 regularized convex optimization (cvxpy).
hyperparameter_tuner.py	K-Fold Cross-Validation for automatic λ selection.
vrp_solver.py	Capacitated VRP solver using Google OR-Tools with multi-strategy heuristics.
tester.py	Headless robustness test suite across seeds, noise, regularization, and scale.
requirements.txt	Python dependencies.