Project 4: Delivery Route Optimizer

Build a routing tool that optimizes delivery routes using real road networks and constraints.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 2-3 weeks
Language Python
Prerequisites Graph theory basics, optimization concepts
Key Topics geocoding, routing graphs, VRP, constraints
Output Optimized route map + CSV

Learning Objectives

By completing this project, you will:

  1. Geocode addresses into coordinates with caching.
  2. Build a road network and compute travel-time matrices.
  3. Solve a TSP/VRP with constraints (time windows, capacity).
  4. Visualize the optimized route on a map.
  5. Compare route quality against a naive baseline.
  6. Explain trade-offs between solution quality and compute time.

The Core Question You’re Answering

“How do I compute an efficient delivery route using real roads and real constraints?”

This is the core logistics problem for delivery companies, field services, and routing platforms.

Concepts You Must Understand First

Concept Why It Matters Where to Learn
Geocoding Addresses must become coordinates GeoPy docs
Routing graphs Roads are graphs of nodes/edges OSMnx docs
TSP/VRP Optimization problem definition OR-Tools docs
Constraints Real delivery needs limits OR-Tools examples
Distance matrix Solver input format Routing tutorials

Key Concepts Deep Dive

  1. Geocoding Reliability
    • Address parsing is imperfect; cache results and allow manual fixes.
  2. Road Network vs Euclidean Distance
    • Straight-line distance is misleading for cities with rivers, highways, and one-ways.
  3. VRP vs TSP
    • TSP: one vehicle, minimize distance.
    • VRP: multiple vehicles, time windows, capacity.

Theoretical Foundation

Routing Pipeline

Addresses -> Geocode -> Road Graph -> Travel Matrix -> VRP Solver -> Route Map

Why Constraints Matter

A route optimized for distance may violate time windows or overload a vehicle. Real-world routing must balance cost, time, and capacity.

Project Specification

What You Will Build

A tool that takes a CSV of delivery stops, computes an optimized route, and outputs a map and ordered stop list.

Functional Requirements

  1. Read CSV with addresses and optional time windows.
  2. Geocode addresses with caching and error handling.
  3. Build a travel-time matrix using road network distances.
  4. Solve a TSP or VRP with OR-Tools.
  5. Output ordered stops, total distance, and travel time.
  6. Render route map with numbered stops.

Non-Functional Requirements

  • Reliability: Handle failed geocodes gracefully.
  • Transparency: Print solver assumptions and constraints.
  • Reproducibility: Cache geocoding results.

Example Usage / Output

$ python route_optimizer.py --input data/stops.csv --start "123 Main St, Springfield"
Optimized route saved to output/route.html
Total distance: 28.4 km
Estimated travel time: 52 min

Real World Outcome

You open output/route.html and see:

  1. A polyline showing the optimized route.
  2. Numbered markers for each stop.
  3. A summary box listing total distance and time.
  4. A CSV of stops in optimized order.

Solution Architecture

High-Level Design

CSV -> Geocode -> Graph -> Distance Matrix -> OR-Tools -> Map

Key Components

Component Responsibility Key Decisions
Geocoder Address to coordinate Provider + rate limits
Router Build graph + distances OSMnx vs external API
Solver Optimize route TSP vs VRP
Visualizer Map output Folium styling

Data Structures

list[tuple]   # coordinates
list[list]    # distance matrix

Algorithm Overview

  1. Geocode addresses to coordinates.
  2. Build road graph for bounding area.
  3. Compute travel time matrix between all stops.
  4. Solve TSP/VRP using OR-Tools.
  5. Render route on map and export CSV.

Complexity

  • Distance matrix: O(n^2)
  • VRP solving: NP-hard, heuristic approach.

Implementation Guide

Development Environment Setup

python -m venv geo-env
source geo-env/bin/activate
pip install osmnx geopy ortools folium

Project Structure

project-root/
├── data/
│   └── stops.csv
├── src/
│   ├── geocode.py
│   ├── routing.py
│   └── solver.py
├── output/
│   ├── route.html
│   └── route.csv
└── README.md

The Core Question You’re Answering

“How do I minimize travel cost while respecting real-world constraints?”

Concepts You Must Understand First

  1. Shortest paths: Dijkstra or A* on road graphs.
  2. Matrix building: Pairwise travel times.
  3. Constraints: Time windows, depot location, capacity.

Questions to Guide Your Design

  1. How will you handle failed geocodes?
  2. What is a good fallback for large datasets?
  3. What constraints matter most for your use case?
  4. How will you compare your solution to a naive route?

Thinking Exercise

Take 5 addresses and estimate a naive route order. Compare to a solver output. How much improvement do you see?

Interview Questions

  1. What is the difference between TSP and VRP?
  2. Why do you need a distance matrix?
  3. How do you handle geocoding errors?
  4. Why is Euclidean distance misleading for routing?
  5. What constraints are most common in routing problems?
  6. How would you scale this to 1000 stops?

Hints in Layers

  • Hint 1: Start with 5-10 stops and a TSP.
  • Hint 2: Cache geocodes to avoid rate limits.
  • Hint 3: Use bounding boxes to reduce graph size.
  • Hint 4: Compare results to a naive route for validation.

Books That Will Help

Topic Book Chapter
Routing OR-Tools docs Routing section
Graphs “Grokking Algorithms” Dijkstra
Geocoding GeoPy docs Geocoding

Implementation Phases

Phase 1: Geocoding and Graph (4-5 days)

  • Parse CSV and geocode addresses.
  • Build road network for region.

Checkpoint: Stops plotted on a map.

Phase 2: Distance Matrix and Solver (5-7 days)

  • Compute travel time matrix.
  • Solve TSP or VRP.

Checkpoint: Ordered route produced with totals.

Phase 3: Visualization and Output (3-4 days)

  • Render route polyline.
  • Export CSV and HTML.

Checkpoint: Map and route report ready.

Key Implementation Decisions

Decision Options Recommendation Rationale
Routing data OSMnx, external API OSMnx No API key needed
Solver exact, heuristic heuristic Scales better
Constraints none, time windows minimal first Reduce complexity

Testing Strategy

Category Purpose Examples
Geocoding Address resolution Check coordinates
Matrix Size correctness n x n matrix
Solver Route validity No duplicate stops

Critical cases:

  • Invalid address.
  • Duplicate stops.
  • Large stop counts.

Common Pitfalls and Debugging

Pitfall Symptom Solution
Rate-limited geocoding Errors Add caching and delays
Wrong coordinate order Route off-map Verify lon/lat ordering
Huge matrix Memory error Limit stops or chunk

Extensions and Challenges

  • Add multiple vehicles and capacity limits.
  • Add live traffic weighting.
  • Build a web UI for dispatchers.

Real-World Connections

  • Logistics and last-mile delivery.
  • Field service routing and scheduling.

Resources

  • OR-Tools: https://developers.google.com/optimization
  • OSMnx: https://osmnx.readthedocs.io/
  • GeoPy: https://geopy.readthedocs.io/

Self-Assessment Checklist

  • I can compute routes using road networks.
  • I can explain VRP constraints.
  • I can validate route quality against a baseline.

Submission / Completion Criteria

Minimum Viable Completion

  • Geocode stops and compute a TSP route.

Full Completion

  • VRP with at least one constraint + map output.

Excellence

  • Multi-vehicle routing and traffic integration.

This guide was generated from GEOSPATIAL_PYTHON_LEARNING_PROJECTS.md. For the complete learning path, see the parent directory GEOSPATIAL_PYTHON_LEARNING_PROJECTS/README.md.