A Districting System for Sales Territory Design

The rapid growth of the Online-to-Offline (O2O) economy necessitates precise operational management, particularly in supply-side tasks such as merchant acquisition and maintenance. A critical challenge is the division of urban areas into districts for sales representatives, known as the Sales Territory Design Problem (STDP). The STDP involves partitioning a city into connected, balanced, and compact districts, promoting equitable workload distribution for sales teams. We address this challenge by formulating it as the Balanced Connected (k)-Partition Problem (BCPk ), a well-known NP-hard problem, with an added compactness objective. Existing approaches often struggle to scale effectively in large cities with large k. In this paper, we propose an efficient districting system for STDP comprising a hierarchy-aware map segmentation module and a block aggregation module. The map segmentation module partitions large geographic areas into small blocks using hierarchical road networks and other physical boundaries. The block aggregation module introduces a novel Mixed-Integer Programming (MIP) formulation of O(|V|) size, incorporating a global Polsby-Popper score to enhance district compactness. Our system demonstrates substantial improvements in computational efficiency and solution quality, and has been effectively deployed in real-world production environments.