Cluster Delivery Addresses into Zones

Problem Given a large set of delivery addresses as lat/long points, group them into cohorts or polygons — e.g. to define delivery zones for planning and rider assignment.

Functional requirements

• Produce geographically coherent, contiguous zones from raw address coordinates.
• Keep zones reasonably balanced by order volume, not just by area.
• Emit a usable boundary per zone (polygon) plus a fast point-in-zone lookup for new addresses.
• Recompute zones as demand shifts, without reshuffling every zone on each run.

Non-functional requirements

• Tens of millions of historical address points nationally; hundreds of thousands of distinct delivery points in a large city.
• Zone lookup at order time in single-digit milliseconds, ~5-10k lookups/sec at peak.
• Zone recomputation is an offline batch job run weekly or monthly, not per-order.
• Zones must stay stable enough that rider familiarity and ops planning are not invalidated every week.

Key components

• Ingestion and cleaning of coordinates: dedup, geocoding noise, and obviously bad points.
• Clustering layer: k-means or DBSCAN over lat/long (projected, or using haversine distance), or grid/H3-hex binning followed by agglomeration of adjacent cells.
• Boundary derivation: convex hulls or alpha-shapes around each cluster to yield polygons.
• Balancing pass that merges or splits zones to equalize order volume and rider load.
• Serving: polygons in a spatial index (R-tree/PostGIS) or an H3 cell-to-zone map for near-constant-time point-in-zone lookup.

Deep dives / trade-offs

• DBSCAN vs. k-means: density-based clustering handles the wildly irregular density of urban delivery demand and finds non-spherical shapes, but needs eps/minPts tuning and leaves noise points unassigned; k-means forces spherical, equal-ish clusters and needs k chosen up front.
• Grid/H3 binning as the pragmatic alternative: cheap, deterministic, trivially incremental — at the cost of arbitrary boundaries that ignore real geography.
• Geographic compactness vs. operational fairness: the most compact zones are rarely the most load-balanced; how to trade rider load against travel distance.
• Boundary handling: addresses falling between clusters, and roads/rivers that make two nearby points operationally far apart — why straight-line distance misleads.