Dynamic Vehicle Routing Optimizer

🚚 Dynamic Multi-Stop Vehicle Routing Optimizer

Real-time Capacitated Vehicle Routing with Time Windows (CVRPTW) and in-transit rerouting. Hard time windows · Pinned stops · Degraded-mode routing · Invariant-checked plans

---

📖 Overview

Planning a city fleet is an NP-hard problem. Most routing demos stop at "here is an optimal route for tomorrow morning." Real operations don't stop — a rush order lands at 11:40, a truck sits in traffic, a customer cancels.

This project implements a production-shaped CVRPTW engine where the plan is expected to survive contact with reality:

• A Google OR-Tools guided-local-search solver plans multi-stop routes under hard time windows, payload capacity and driver shift limits.
• A dynamic reroute engine re-solves while vehicles are moving, pinning already-visited and in-transit stops as immutable.
• Every plan — batch or dynamic — is re-validated against four mathematical invariants before it leaves the process. A violated plan raises; it never ships.
• The service is built to degrade instead of fail: no OSRM? A synthetic asymmetric road matrix. No Redis or Postgres? In-memory stores, not HTTP 500s.

Scope note. This is an optimizer service and simulation harness, not a dispatching UI. It exposes a REST API, a route benchmark simulator, and a PostGIS schema ready for a map layer.

---

✨ Key Features

---

🏗️ System Architecture

Component breakdown

Trust & resilience boundaries

• Process boundary — everything in the optimizer process shares one trust domain and one Python heap. The active plan and problem are held in module-level dicts keyed by plan_id, so this service is single-replica by design.
• Infra boundary — PostGIS, Redis and OSRM are separate containers reached only over the Compose network; each has a healthcheck and its own degradation path.
• Invariant boundary — the ConstraintValidator is the only component allowed to declare a plan trustworthy. It sits after both the batch solver and the reroute engine, so a merged dynamic plan is validated as a whole, not just its new legs.

---

🔁 Core Workflow — POST /api/v1/routes/optimize

Step by step

1. Intake — POST /api/v1/routes/optimize accepts a validated OptimizationProblem: one Depot, N VehicleConstraints, M Waypoints. Pydantic rejects an inverted time window at the edge (start > end).
2. Matrix resolution — coordinates are hashed to a vrp:matrix:driving:<sha256> key. A Redis hit short-circuits the network; a miss queries OSRM; an OSRM failure permanently flips the client to the synthetic matrix for the process lifetime.
3. Model construction — node 0 is the depot; every vehicle starts and ends there. Demands scale ×100 for integer precision. The Time dimension gets slack_max = 86400 (waiting is allowed) but each stop's cumul variable is range-set to its window (late is not).
4. Search — PATH_CHEAPEST_ARC seeds the first solution, guided local search improves it within time_limit_seconds (default 5 s).
5. Disjunction handling — every waypoint carries a drop disjunction with a 1,000,000 penalty, so a stop that cannot fit is returned in unassigned_waypoints and the plan status becomes UNASSIGNABLE_DUE_TO_CONSTRAINTS rather than failing outright.
6. The invariant gate — the assembled plan is re-checked for payload, hard time window, shift duration and depot start/end. A violation raises ValueError and no plan is returned.
7. Persistence — save_plan writes each vehicle route in a transaction while retaining an in-memory copy, so GET /api/v1/routes/{id} keeps working if Postgres is down.
8. Fan-out — a ROUTE_UPDATED event is published to Redis pub/sub, and the plan plus its problem are cached in-process to enable subsequent reroute calls.

---

🔀 Dynamic Reroute — the insert path

Why this is the hard part. A reroute cannot simply re-solve the whole problem: the truck has already driven somewhere. The engine therefore treats visited and in-transit legs as fixed, derives each vehicle's remaining payload and earliest departure from its last committed stop, solves only the open tail, stitches the two halves back together, and re-validates the merged result as a single plan.

---

🧰 Tech Stack

---

📁 Project Structure

.
├── cmd/                              # Entry points (composition roots)
│   ├── optimizer_service/main.py     # FastAPI app, routers, lifespan, /health
│   └── fleet_tracker/main.py         # Driver-telemetry runner (ETATracker host)
│
├── internal/                         # All business logic (Go-style layout)
│   ├── domain/                       # Pure domain — no I/O
│   │   ├── models.py                 # Depot, Waypoint, VehicleConstraints, RoutePlan
│   │   └── constraints.py            # ConstraintValidator: the 4 hard invariants
│   ├── solver/                       # Optimization
│   │   ├── vrp_solver.py             # OR-Tools CVRPTW model construction & extraction
│   │   ├── callbacks.py              # Distance / demand / transit-duration callbacks
│   │   └── heuristics.py             # Search-parameter builder (GLS)
│   ├── dynamic/                      # Real-time layer
│   │   ├── reroute_engine.py         # Ad-hoc insertion, cancellation, leg re-timing
│   │   └── eta_tracker.py            # Driver GPS pings vs. planned schedule
│   ├── matrix/                       # Travel-time matrices
│   │   ├── osrm_client.py            # OSRM table client + synthetic fallback
│   │   └── distance_cache.py         # Redis matrix cache, memory fallback
│   ├── repository/                   # Persistence
│   │   ├── db.py                     # asyncpg pool (lazy, non-fatal)
│   │   ├── route_repo.py             # Atomic route persistence + memory mirror
│   │   └── spatial_repo.py           # Waypoint spatial clustering (Haversine)
│   └── transport/                    # Edges (framework-facing)
│       ├── api/routes.py             # /optimize, /{id}/reroute, /{id} GeoJSON
│       ├── api/orders.py             # Order CRUD
│       └── events/event_listener.py  # Redis pub/sub dispatcher, memory fallback
│
├── simulator/fleet_simulator.py      # 15-vehicle / 120-stop city fleet benchmark
├── migrations/001_init_logistics_schema.sql   # PostGIS schema bootstrap
├── osrm-data/                        # Drop map.osrm extract here (optional)
├── tests/                            # 6 pytest modules
├── logistics_vrp_optimizer_autonomous_blueprint.md  # Design spec / ADR
├── docker-compose.yml                # db · redis · osrm · optimizer_service
├── Dockerfile                        # python:3.11-slim + uvicorn
├── Makefile                          # up · down · test · run-service · run-simulator
└── pyproject.toml                    # Dependencies + pytest config

---

🚀 Quick Start

1. Clone

git clone https://github.com/Kavryx-Dev/dynamic-multi-stop-vehicle-routing-optimizer.git
cd dynamic-multi-stop-vehicle-routing-optimizer

2a. Full stack with Docker (recommended)

Brings up PostGIS + Redis + OSRM + the optimizer service.

# 2a: defaults work as-is — docker-compose injects its own env
docker compose up -d
docker compose ps

Check it is alive:

curl http://localhost:8000/health
# {"status":"healthy","service":"dynamic-vrp-optimizer","database_connected":true}

OSRM map data is optional. Without an extract in osrm-data/, the OSRM container idles in standby and the client transparently uses the synthetic road matrix — the service stays fully functional.

2b. Local run without Docker

python -m venv .venv
# Windows
.venv\Scripts\activate
# macOS / Linux
source .venv/bin/activate

pip install -e ".[dev]"

Start Postgres and Redis yourself (or skip them — both are optional), then:

uvicorn cmd.optimizer_service.main:app --reload --port 8000

3. Configuration

Every value has a working default; nothing is required.

4. Run the benchmark

make run-simulator      # or: python simulator/fleet_simulator.py

--- SIMULATION BENCHMARK REPORT ---
Vehicles: 15
Stops: 120
Rush Orders: 10
NN Baseline Duration: ...
CVRPTW Duration: ...
Savings: ...%
Time Window Violations: 0
Capacity Violations: 0

Latest measured run (8 vehicles / 40 stops, scaled for CI)

Transit time savings vs nearest-neighbour: 48.70%
Time window violations: 0
Capacity violations:   0

---

🔌 API Reference

Interactive docs are served at /docs while the app is running.

Example — plan a fleet

curl -X POST http://localhost:8000/api/v1/routes/optimize \
  -H "Content-Type: application/json" \
  -d '{
    "problem": {
      "depot": {
        "id": "depot-central", "code": "DEPOT-BLR",
        "lat": 12.9716, "lon": 77.5946,
        "operating_window": { "start": 0, "end": 43200 }
      },
      "vehicles": [
        { "id": "van-01", "vehicle_code": "VAN-01", "depot_id": "depot-central",
          "max_payload_kg": 800.0, "max_shift_seconds": 28800, "start_time": 0 }
      ],
      "waypoints": [
        { "id": "stop-001", "order_number": "ORD-001",
          "lat": 12.9784, "lon": 77.6408, "demand_kg": 42.5,
          "time_window": { "start": 1800, "end": 14400 },
          "service_duration_seconds": 300 }
      ],
      "time_limit_seconds": 5,
      "traffic_multiplier": 1.2
    }
  }'

Example — inject an urgent order in transit

curl -X POST http://localhost:8000/api/v1/routes/$PLAN_ID/reroute \
  -H "Content-Type: application/json" \
  -d '{
    "action": "insert",
    "urgent_waypoint": {
      "id": "rush-01", "order_number": "RUSH-01",
      "lat": 12.9352, "lon": 77.6245, "demand_kg": 30.0,
      "time_window": { "start": 3600, "end": 27000 },
      "service_duration_seconds": 300
    },
    "committed_stop_ids": ["stop-001"],
    "max_solver_seconds": 2.5
  }'

---

🧪 Testing

make test          # or: pytest -v
pytest tests/test_time_window_invariants.py -v

Current status: 16 passing, 1 failing. test_fleet_simulator.py::test_city_fleet_simulation_and_benchmark asserts urgent_stops_inserted > 0; on the seeded 8-vehicle/40-stop fixture the engine correctly refuses every insertion because the merged plan fails the hard time-window check (stop-040: arrival 15186s > latest 14400s). The three invariants it also asserts — zero time-window violations, zero capacity violations and ≥ 18 % savings (48.7 % measured) — all pass. This is a real open item, not a flaky test, and it is tracked honestly rather than asserted as green.

---

🧠 Design Decisions

---

🗺️ Roadmap

• Choose and add a LICENSE file
• Fix the seeded benchmark fixture so urgent insertions are feasible at CI scale
• Multi-depot support (currently one depot per problem)
• Volume (m3) enforced as a second capacity dimension
• Persist active plans so the service can run more than one replica
• Driver app contract for ETATracker pings (currently a standby loop)
• Wire up — or remove — dormant code: SpatialRepository.cluster_waypoints_by_distance, Waypoint.is_pinned and the solver's pinned_routes argument are implemented but not yet on the normal call path

---

🤝 Contributing

Contributions are welcome. Please:

1. Keep internal/domain/ free of I/O and framework imports — it is the testable core.
2. Add a test for new behaviour; tests/ is the contract.
3. Never relax a ConstraintValidator invariant to make a test pass. Fix the planner.
4. Run pytest -v before opening a PR, and be explicit in the PR description about any known failure.

---

📄 License

No LICENSE file has been added yet — see the roadmap. Until one is chosen, all rights are reserved by default. If MIT is intended, add a LICENSE file and flip the badge above.

Diagrams are native Mermaid and render directly on GitHub.