公开(公告)号：US12229712B1

公开(公告)日：2025-02-18

申请号：US17747866

申请日：2022-05-18

Applicant: Amazon Technologies, Inc.

Inventor： Daniel Esteban Merchan ,  Dipal Patel Gupta ,  Jatin Arora ,  Bhargav Kunkulagunta ,  Julian Enrique Pachon ,  Rohit Malshe

IPC: G06Q10/0835 ,  G01C21/00

Abstract: Techniques for dividing a geographical area into districts are described herein. Geospatial vector data, barrier geospatial vector data, road infrastructure data, and historical delivery demand data for a geographical area may be obtained. A plurality of clusters from a stratified sampling of data points for the delivery demand data and barrier penalties from a barrier-aware road graph are generated. A first set of polygons for the plurality of clusters may be generated using a concave hull algorithm. A second set of polygons may be generated using a barrier constrained network Voronoi algorithm that uses the barrier-aware road graph and the first set of polygons as seeds. The second set of polygons may be modified using a bounded Voronoi algorithm that uses a raster cost allocation based on barrier penalties. Coordinates for each polygon of the modified second set of polygons are determined that divide the geographical area.