Project 4: Delivery Route Optimizer

Build a constrained routing planner that transforms delivery stops into feasible, explainable routes on real road networks.

Quick Reference

Attribute	Value
Difficulty	Level 3: Advanced (The Engineer)
Time Estimate	24-36 hours
Main Programming Language	Python (Alternatives: Java, Rust, Julia)
Coolness Level	Level 4: Hardcore Tech Flex
Business Potential	2. The “Micro-SaaS / Pro Tool”
Prerequisites	Graph algorithms, geocoding basics, constraint modeling
Key Topics	VRP, travel-time matrices, feasibility diagnostics

1. Learning Objectives

Build a routing graph from map data with realistic constraints.
Convert address stops into network-valid nodes with confidence checks.
Compute travel-time matrices and solve constrained routing plans.
Distinguish optimality from feasibility in practical operations.
Generate route artifacts suitable for driver execution.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Directed Network Routing

Fundamentals

Road networks are directed, weighted graphs.
One-way rules and turn constraints change feasible paths.

Deep Dive Routing quality depends on edge costs and constraint realism more than solver complexity. If speeds are unrealistic or directions ignored, solver output may be mathematically elegant but operationally unusable. Always validate a sample of pairwise travel times against observed reality.

2.2 VRP Constraints and Feasibility

Fundamentals

VRP extends shortest path to multi-stop, multi-vehicle planning.
Hard constraints must be satisfied; soft constraints can be penalized.

Deep Dive Infeasibility is normal, not exceptional. Your system should diagnose infeasibility and suggest minimal relaxations (for example, +30 minutes shift or one extra vehicle). This is more useful than returning “no solution” without context.

2.3 Geocoding Confidence and Operational Risk

Fundamentals

Address resolution uncertainty propagates into routing errors.

Deep Dive Treat geocoding confidence as a first-class quality signal. Low-confidence stops should route to review queues, not directly into dispatch manifests. One bad geocode can cascade into missed windows and route failure.

3. Project Specification

3.1 What You Will Build

A routing pipeline that:

ingests stop list and constraints,
geocodes and validates stops,
computes travel-time matrix,
solves VRP,
exports route manifests and map.

Included:

feasibility diagnostics,
unserved stop reporting,
deterministic fixture mode.

Excluded:

live traffic ingestion,
dynamic re-optimization during route execution,
mobile dispatch app.

3.2 Functional Requirements

Parse stops and constraints from CSV/JSON input.
Geocode stops with confidence thresholds.
Build directed travel-time matrix.
Solve VRP for available vehicles and time windows.
Export route plan artifacts and infeasibility report if needed.

3.3 Non-Functional Requirements

Reliability: Must report infeasibility causes.
Interpretability: Route outputs include ETA and constraint status.
Reproducibility: Fixture mode yields deterministic route ordering.

3.4 Data Formats / Schemas

Route output schema:
- vehicle_id
- stop_sequence
- stop_id
- eta_local
- service_minutes
- load_after_stop
- constraint_violations (if any)

3.5 Edge Cases

Low-confidence geocode
Impossible time windows
Disconnected graph segments
Capacity overrun
Duplicate stop IDs

3.6 Real World Outcome

3.6.1 How to Run

$ python run_project4_routes.py --input stops.csv --vehicles 2 --shift-minutes 420

3.6.2 Golden Path Demo

$ python run_project4_routes.py --fixture fixtures/day1_routes.json
[INFO] stops=61 vehicles=2
[INFO] feasible solution found
[INFO] total_travel_minutes=287
[DONE] manifests and map exported

3.6.3 Exact Terminal Transcript (Live)

$ python run_project4_routes.py --input stops.csv --vehicles 2 --shift-minutes 420
[INFO] Loaded stops: 63
[INFO] Geocoding success: 61 unresolved: 2
[INFO] Building travel-time matrix
[INFO] Solving VRP
[INFO] Exporting outputs/route_plan.csv
[INFO] Exporting outputs/route_map.html
[DONE] Completed in 96.2 seconds

4. Solution Architecture

4.1 High-Level Design

Stop Input -> Geocoder -> Graph Matrix Builder -> VRP Solver -> Manifest Generator -> Map Renderer

4.2 Key Components

Component	Responsibility	Key Decision
Geocoder	Resolve addresses	Confidence threshold and fallback
Matrix Engine	Compute pairwise travel costs	Directed graph and impedance model
Solver	Optimize constrained routing	Hard/soft constraint policy
Diagnostics	Explain infeasibility	Relaxation strategy
Exporter	Driver-ready artifacts	Manifest format and map clarity

4.3 Algorithm Overview

Validate and geocode stops.
Build directed network and matrix.
Solve constrained VRP.
Export routes or infeasibility report.

5. Implementation Guide

5.1 Development Environment Setup

$ mamba create -n geo-p04 python=3.11 osmnx networkx ortools geopandas -y
$ mamba activate geo-p04

5.2 Project Structure

project4/
├── src/
│   ├── geocode.py
│   ├── matrix.py
│   ├── solver.py
│   ├── diagnostics.py
│   └── main.py
├── fixtures/
├── outputs/
└── tests/

5.3 The Core Question You Are Answering

“How do we generate routes that can actually be executed under real operational constraints?”

5.4 Concepts You Must Understand First

Directed shortest-path behavior.
Hard vs soft routing constraints.
Geocoding confidence handling.

5.5 Questions to Guide Your Design

What minimum confidence allows auto-dispatch?
How do you prioritize late penalties versus total distance?
Which constraints can be relaxed in fallback mode?

5.6 Thinking Exercise

Given one vehicle, 30 stops, and tight windows, reason feasibility before solving. Identify which single relaxation would likely restore feasibility.

5.7 Interview Questions

Why is VRP harder than shortest path?
How do one-way streets impact matrix correctness?
What should a routing system return when infeasible?

5.8 Hints in Layers

Hint 1: Build a baseline route with no windows first.
Hint 2: Add one constraint category at a time.
Hint 3: Store reason codes for unserved stops.
Hint 4: Validate matrix symmetry assumptions (they often fail).

6. Testing Strategy

Category	Purpose
Unit	Matrix generation, constraint checks
Integration	Full solve and export with fixture day
Edge Case	Infeasible windows, unresolved geocodes

Critical tests:

Infeasible fixture returns structured diagnostics.
Resolved route respects all hard constraints.
Low-confidence stops are routed to review queue.

7. Common Pitfalls & Debugging

Pitfall	Symptom	Fix
Hidden infeasibility	Solver returns no plan	Add pre-solve feasibility bounds
Unrealistic ETAs	Drivers miss windows	Calibrate impedance assumptions
Geocode mismatch	Stops route to wrong region	Enforce confidence threshold + manual review

8. Extensions & Challenges

Add route fairness objective across drivers.
Add emissions-aware cost function.
Add live re-optimization trigger for missed stops.

9. Real-World Connections

Last-mile delivery optimization.
Field-service dispatch planning.
Emergency logistics scheduling.

10. Resources

OSMnx docs: https://osmnx.readthedocs.io/
NetworkX docs: https://networkx.org/documentation/stable/
OR-Tools routing docs: https://developers.google.com/optimization

11. Self-Assessment Checklist

I can explain every hard constraint in my model.
I can diagnose why a scenario is infeasible.
I can justify geocoding confidence policy.
I can produce driver-ready manifests reproducibly.

12. Submission / Completion Criteria

Minimum Viable Completion

Feasible route output for fixture scenario.
Structured infeasibility output for failing scenario.

Full Completion

Includes quality checks for geocoding and matrix integrity.
Includes runbook for constraint tuning.

Excellence

Includes post-route analytics (lateness, idle time, utilization).
Includes alternative objective comparison report.