# Route Optimization — IoT SmartBin

## Overview

The route-service provides heuristic-based route optimization for garbage collection vehicles. Given a set of smartbins with fill levels and GPS coordinates, it generates optimized collection routes for multiple vehicles.

## Algorithm: Heuristic Geolocation Router (Phase 1)

### Pipeline

```
Input bins → Filter by fill% → Cluster → Route per cluster → Optimize → Output
```

### Step 1: Filter Bins
- **Primary:** `fill_percent >= 80` (FULL) — must collect
- **Secondary:** `fill_percent >= 50` (MEDIUM) — optional, include if nearby (configurable threshold)
- Bins below threshold are excluded from routes

### Step 2: Cluster Bins per Vehicle
- **Algorithm:** Greedy geographic split
  1. Compute centroid of all eligible bins
  2. For k vehicles, use k-means clustering (lightweight implementation)
  3. Each cluster is assigned to one vehicle
  4. Respect `maxStopsPerVehicle` constraint — overflow bins assigned to nearest under-capacity cluster

### Step 3: Route per Vehicle (TSP Approximation)
- **Initial route:** Nearest-neighbor heuristic
  1. Start from depot
  2. Visit nearest unvisited bin
  3. Repeat until all bins visited
  4. Return to depot
- **Improvement:** 2-opt local search
  1. For each pair of edges, check if swapping would shorten total distance
  2. Repeat until no improvement found (or max iterations reached)

### Step 4: Calculate Metrics
- Total distance per route (km, using Haversine formula)
- Estimated time (ETA) based on average speed assumption (default: 15 km/h in city)

---

## API Endpoint

### POST `/api/v1/tenants/:tenantId/routes/optimal`

**Request Body:**
```json
{
  "siteId": "jakarta-utara",
  "depot": { "lat": -6.1, "lon": 106.9 },
  "vehicleCount": 2,
  "maxStopsPerVehicle": 30,
  "fillThreshold": 80,
  "bins": [
    { "deviceId": "bin-001", "lat": -6.12345, "lon": 106.98765, "fill_percent": 82 },
    { "deviceId": "bin-002", "lat": -6.13000, "lon": 106.99000, "fill_percent": 91 },
    { "deviceId": "bin-003", "lat": -6.11500, "lon": 106.97500, "fill_percent": 55 },
    { "deviceId": "bin-010", "lat": -6.14000, "lon": 106.96000, "fill_percent": 95 }
  ]
}
```

**Response:**
```json
{
  "optimizedAt": "2025-01-15T10:30:00Z",
  "fillThreshold": 80,
  "totalBinsEligible": 3,
  "routes": [
    {
      "vehicle": 1,
      "stops": ["bin-001", "bin-002"],
      "distance_km": 5.2,
      "eta_min": 21
    },
    {
      "vehicle": 2,
      "stops": ["bin-010"],
      "distance_km": 7.1,
      "eta_min": 28
    }
  ]
}
```

---

## Distance Calculation

Uses Haversine formula for great-circle distance:

```
a = sin²(Δlat/2) + cos(lat1) × cos(lat2) × sin²(Δlon/2)
c = 2 × atan2(√a, √(1−a))
d = R × c
```

Where R = 6371 km (Earth's radius).

---

## Configuration

| Parameter | Default | Description |
|-----------|---------|-------------|
| `fillThreshold` | 80 | Minimum fill% to include bin in route |
| `avgSpeedKmh` | 15 | Average vehicle speed for ETA calculation |
| `maxStopsPerVehicle` | 30 | Maximum bins per vehicle route |
| `twoOptMaxIter` | 100 | Maximum 2-opt improvement iterations |

---

## Limitations & Future Upgrades

### Current (Phase 1 — Heuristic)
- Simple nearest-neighbor + 2-opt
- No traffic/road network awareness
- Euclidean/Haversine distance (not road distance)
- No time windows or vehicle capacity constraints

### Phase 2 — Enhanced Heuristic
- Use OSRM or Google Maps Distance Matrix API for real road distances
- Add time window constraints (collection hours)
- Priority-based routing (FULL first, then MEDIUM)

### Phase 3 — VRP Solver
- Integrate Google OR-Tools for proper Vehicle Routing Problem (VRP)
- Capacitated VRP (vehicle tonnage limits)
- Time-windowed VRP
- Dynamic re-routing based on real-time fill level updates

---

## Usage Example

```bash
# Get optimal routes for a site
curl -X POST http://localhost:3002/api/v1/tenants/tenantA/routes/optimal \
  -H "Content-Type: application/json" \
  -d '{
    "siteId": "jakarta-utara",
    "depot": {"lat": -6.1, "lon": 106.9},
    "vehicleCount": 2,
    "maxStopsPerVehicle": 30,
    "bins": [
      {"deviceId":"bin-001","lat":-6.12345,"lon":106.98765,"fill_percent":82},
      {"deviceId":"bin-002","lat":-6.13000,"lon":106.99000,"fill_percent":91},
      {"deviceId":"bin-010","lat":-6.14000,"lon":106.96000,"fill_percent":95}
    ]
  }'
```