Skip to content

v1.md

Latest commit

 

History

History
210 lines (149 loc) · 7.44 KB

v1.md

File metadata and controls

210 lines (149 loc) · 7.44 KB

Spotter v1 — Technical Documentation

Endpoint

POST /api/v1/navigate/

Request:

{
  "start": "New York, NY",
  "end": "Los Angeles, CA"
}

Response:

{
  "fuel_stops": [
    {
      "station_id": 12345,
      "name": "Pilot Travel Center",
      "lat": 40.123,
      "lng": -80.456,
      "distance_from_start": 320.5,
      "price_per_gallon": 3.19,
      "gallons": 32.05,
      "cost": 102.24
    }
  ],
  "total_fuel_cost": 487.32,
  "total_distance": 2790.4,
  "total_gallons": 279.04,
  "encoded_polyline": "a~l~Fjk~uOwHJy@..."
}

Pipeline (5 steps)

User request
  │
  ▼
┌──────────────┐     ┌────────────────┐     ┌─────────────────────┐
│ 1. Geocode   │────▶│ 2. OSRM Route  │────▶│ 3. Station          │
│   start/end  │     │   A → B        │     │   Nearest-Point     │
│              │     │   (1 API call)  │     │   Projection        │
└──────────────┘     └────────────────┘     └─────────┬───────────┘
                                                      │
                                                      ▼
                     ┌────────────────┐     ┌─────────────────────┐
                     │ 5. Return      │◀────│ 4. DP Optimizer     │
                     │   Response     │     │   (Forward DP)      │
                     └────────────────┘     └─────────────────────┘

Functions

1. geocoding.geocode(location_string) → (lat, lng)

Converts a place name (e.g. "Chicago, IL") into GPS coordinates using the Nominatim geocoder (via GeoPy).

  • Retries up to 3 times with exponential backoff on rate-limiting (HTTP 429/509).
  • Raises ValueError if the location cannot be found.
  • Raises RuntimeError if Nominatim is still rate-limiting after all retries.

2. provider_call.get_route(start_lat, start_lng, end_lat, end_lng) → dict

Makes a single OSRM API call to get the driving route from A to B.

OSRM call:

GET /route/v1/driving/{start_lng},{start_lat};{end_lng},{end_lat}?overview=full&geometries=polyline

Returns:

Key Type Description
encoded_polyline str Compressed polyline geometry of the route
points list[(lat, lng)] Decoded polyline as coordinate pairs
cumulative_distances list[float] Cumulative haversine distance (miles) at each polyline point
total_distance_miles float Total route distance in miles (OSRM meters → miles)

How cumulative_distances is computed:

The compute_cumulative_distances() helper walks the decoded polyline point by point. For each consecutive pair it computes the haversine (great-circle) distance and keeps a running total:

cumulative[0] = 0.0
cumulative[i] = cumulative[i-1] + haversine(point[i-1], point[i])

This gives every polyline point a mile-marker value from the start.

3. stations.get_stations_along_route(route_points, cumulative_distances) → list[dict]

Finds gas stations near the route and assigns each one a distance_from_start.

Algorithm — Nearest-Point Projection

  1. Bounding box — Compute min/max lat/lng of all route points, expand by 0.5° (~35 miles) of padding.

  2. Database query — Use PostGIS location__within=bbox to get all stations inside the bounding box. This is fast spatial-index lookup, no Python distance computation needed.

  3. Sub-sample — The decoded polyline can have 50,000+ points. Sub-sample down to ≤2,000 evenly spaced points (always including the last point) to keep the search fast.

  4. Nearest-point search — For each station, iterate through the sampled route points:

    • Pre-filter: skip points where |Δlat| > 0.4° or |Δlng| > 0.5° (fast rectangular check).
    • Compute haversine distance to remaining points.
    • Track the closest route point and its cumulative distance.

  5. Distance filter — Keep the station only if the closest route point is within MAX_STATION_DISTANCE_FROM_ROUTE_MILES (default 25 mi).

  6. Sort by distance_from_start.

Output per station:

Key Type Description
id int OPIS station ID
name str Station name
lat, lng float Station coordinates
price float Retail fuel price ($/gallon)
distance_from_start float Cumulative distance of the nearest route point (miles)
distance_from_route float Haversine distance from station to nearest route point (miles)

Limitation

The station's distance_from_start snaps to the nearest sampled point's cumulative distance. If a station sits between two widely-spaced sample points, there's a rounding error. V2 improves this with segment projection.

4. optimizer.optimize_fuel_stops(stations, total_distance) → dict

Finds the globally cheapest set of fuel stops using forward dynamic programming.

Short-route fast path

If total_distance ≤ max_range (default 500 mi), the truck can complete the trip on a single tank. Returns zero stops, zero cost, and the total gallons consumed.

Node construction

Build an ordered list of nodes:

[Start(0 mi, price=0)] → [Station₁] → [Station₂] → ... → [Destination(total_distance, price=0)]

Start and Destination are virtual nodes (price=0). They participate in the DP but are never included in the output as fuel stops.

Forward DP

For every pair of nodes (i, j) where j > i:

gap = distance[j] - distance[i]

if gap > max_range:
    break  (all further j are even farther)

fuel_needed = gap / mpg
fuel_cost   = fuel_needed × price[i]

if dp[i] + fuel_cost < dp[j]:
    dp[j] = dp[i] + fuel_cost
    parent[j] = i
  • dp[i] = minimum fuel cost to reach node i from Start.
  • parent[i] = which node we came from on the optimal path.
  • The break on gap > max_range works because nodes are sorted by distance — once the gap exceeds the tank, all subsequent nodes are unreachable from i.

Time complexity: O(n²) where n = number of nodes (stations + 2). In practice n is a few hundred, so this runs in milliseconds.

Back-trace

Walk parent[] backwards from Destination to Start to recover the optimal path. For each leg i → j:

gap       = distance[j] - distance[i]
gallons   = gap / mpg
cost      = gallons × price[i]

Only real stations (not Start/Destination) are included in the output.

Why Start has price = 0

The start node doesn't sell fuel. Since fuel_cost = gallons × price[start] = gallons × 0 = 0, the first leg (Start → first station) is free in cost terms. This models the assumption that the truck starts with a full tank.

Configuration

Defaults in spotter/settings.py under FUEL_OPTIMIZER:

Setting Default Meaning
MAX_RANGE_MILES 500 Truck's max range on a full tank
MPG 10 Fuel efficiency (miles per gallon)
MAX_STATION_DISTANCE_FROM_ROUTE_MILES 25 Max distance a station can be from the route
OSRM_BASE_URL OSRM public API Routing service endpoint