Engineering

Optimizing Delivery Routes at Scale: GPS Tracking & Zone-Based Routing

/5 min read

At Tajir, we deliver to over 100,000 retail stores across Pakistan. When I joined the logistics team, route planning was largely manual — dispatchers would eyeball a map, group nearby stores, and assign routes based on intuition. It worked at small scale. At our scale, it was bleeding money.

The numbers told the story: fuel costs were our second-largest expense, vehicles were spending 40% of their time idle or backtracking, and delivery windows were being missed in dense urban areas like Lahore and Karachi. We needed to engineer a proper solution.

The Architecture

We built a three-layer system:

  1. Real-time GPS ingestion — tracking every vehicle at 10-second intervals
  2. Zone-based pre-clustering — dividing service areas into delivery zones
  3. Route optimization — solving the Vehicle Routing Problem (VRP) within each zone
┌─────────────┐     ┌──────────────┐     ┌─────────────────┐
│  GPS Devices │────▶│  Ingestion   │────▶│   TimescaleDB   │
│  (10s pings) │     │  (Go service)│     │  (time-series)  │
└─────────────┘     └──────────────┘     └────────┬────────┘
                                                   │
┌─────────────┐     ┌──────────────┐              │
│  Dispatcher │◀────│    Route     │◀─────────────┘
│   Console   │     │   Optimizer  │
└─────────────┘     │  (Python)    │◀──── Zone Definitions
                    └──────────────┘      + Order Data

GPS Ingestion

Each delivery vehicle has a GPS tracker that pings our servers every 10 seconds. That's roughly 8,600 data points per vehicle per day, and with 200+ active vehicles, we're ingesting over 1.7 million location records daily.

We chose TimescaleDB (PostgreSQL extension for time-series data) over dedicated time-series databases because:

  • Our team already knew PostgreSQL
  • We needed to join location data with order/vehicle tables
  • TimescaleDB's hypertable compression brought storage costs down significantly

The ingestion pipeline is a lightweight Go service that validates coordinates, deduplicates stale pings, and writes in batches:

type LocationPing struct {
    VehicleID  string    `json:"vehicle_id"`
    Latitude   float64   `json:"lat"`
    Longitude  float64   `json:"lng"`
    Speed      float64   `json:"speed"`
    Heading    float64   `json:"heading"`
    RecordedAt time.Time `json:"recorded_at"`
}
 
func (s *Service) ingestBatch(pings []LocationPing) error {
    // Filter out stale pings (device buffer flush)
    fresh := filterFresh(pings, 30*time.Second)
 
    // Deduplicate by vehicle + time window
    deduped := deduplicateByWindow(fresh, 5*time.Second)
 
    // Batch insert via COPY protocol
    return s.db.CopyFrom(ctx, "vehicle_locations", locationColumns, deduped)
}

Zone-Based Pre-Clustering

Solving VRP for an entire city at once is computationally intractable at our scale. Instead, we divide each city into delivery zones — contiguous geographic areas that a single vehicle can service in one shift.

Zones are defined using a combination of:

  • Historical delivery density — areas with more stores get smaller zones
  • Road network topology — we respect natural boundaries (rivers, highways, rail lines)
  • Vehicle capacity — zone size is bounded by what one truck can carry

We represent zones as H3 hexagonal grids (Uber's spatial indexing system) at resolution 7 (~5km² per hex). Each hex is assigned to a zone, and orders are clustered by zone before route optimization runs.

import h3
 
def assign_zone(lat: float, lng: float, zone_map: dict[str, str]) -> str:
    hex_id = h3.latlng_to_cell(lat, lng, 7)
    return zone_map.get(hex_id, "unassigned")

Route Optimization

Within each zone, we solve a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The constraints:

  • Each vehicle has a maximum weight/volume capacity
  • Each store has a preferred delivery window (morning vs. afternoon)
  • Driver shift length is capped at 10 hours
  • Certain roads are one-way or have time-based restrictions

We use Google's OR-Tools library with a custom distance matrix built from actual road network distances (not Euclidean). The distance matrix is pre-computed nightly using OSRM (Open Source Routing Machine) running on OpenStreetMap data for Pakistan:

from ortools.constraint_solver import routing_enums_pb2, pywrapcp
 
def optimize_routes(zone_orders, vehicles, distance_matrix):
    manager = pywrapcp.RoutingIndexManager(
        len(zone_orders), len(vehicles), depot_index
    )
    routing = pywrapcp.RoutingModel(manager)
 
    # Distance callback
    def distance_callback(from_idx, to_idx):
        from_node = manager.IndexToNode(from_idx)
        to_node = manager.IndexToNode(to_idx)
        return distance_matrix[from_node][to_node]
 
    transit_callback = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback)
 
    # Capacity constraint
    def demand_callback(idx):
        node = manager.IndexToNode(idx)
        return zone_orders[node].weight
 
    demand_callback_idx = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_idx, 0,
        [v.max_weight for v in vehicles],
        True, "Capacity"
    )
 
    # Time window constraints
    routing.AddDimension(transit_callback, 30, 600, False, "Time")
    time_dimension = routing.GetDimensionOrDie("Time")
 
    for i, order in enumerate(zone_orders):
        idx = manager.NodeToIndex(i)
        time_dimension.CumulVar(idx).SetRange(
            order.window_start, order.window_end
        )
 
    # Solve
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_params.time_limit.FromSeconds(30)
 
    solution = routing.SolveWithParameters(search_params)
    return extract_routes(manager, routing, solution)

Results

After three months in production:

  • 23% reduction in fuel costs — vehicles drive fewer total kilometers
  • 31% improvement in on-time delivery rate — time window constraints are respected
  • Dispatcher planning time dropped from 2 hours to 15 minutes — zones and routes are pre-computed overnight

The most surprising win was in vehicle utilization. By properly packing orders across fewer vehicles per zone, we reduced the active fleet size by 12% while handling the same delivery volume. Those vehicles were redeployed to underserved areas, expanding coverage.

Lessons Learned

Start with data, not algorithms. We spent the first month just instrumenting GPS tracking and building dashboards. Seeing the actual movement patterns revealed problems we hadn't considered — like drivers taking personal detours, or vehicles idling at certain warehouses due to loading dock bottlenecks.

Good enough beats optimal. Our VRP solver runs with a 30-second time limit. A longer solve time produces marginally better routes but delays the morning dispatch. Operations cares about "routes ready by 6 AM," not "globally optimal routes ready by 6:30."

The human element matters. Drivers initially resisted prescribed routes — they knew their areas and had their preferences. We added a feedback mechanism where drivers can flag route issues, and the system learns from their corrections. Adoption went from 60% to 95% after that change.

This system now handles routing for our entire fleet across five cities. The architecture has held up well — the main scaling challenge is keeping the OSRM distance matrices current as new roads are built and neighborhoods expand. But that's a good problem to have.