Incorporating Road Networks into Territory Design
This work addresses territory design for urban planning or logistics, but it appears incremental as it modifies existing graph partitioning methods.
The paper tackles the territory design problem by developing graph theoretic models that incorporate road networks, and it tests and compares algorithms on real-world instances to optimize objectives like balance and compactness.
Given a set of basic areas, the territory design problem asks to create a predefined number of territories, each containing at least one basic area, such that an objective function is optimized. Desired properties of territories often include a reasonable balance, compact form, contiguity and small average journey times which are usually encoded in the objective function or formulated as constraints. We address the territory design problem by developing graph theoretic models that also consider the underlying road network. The derived graph models enable us to tackle the territory design problem by modifying graph partitioning algorithms and mixed integer programming formulations so that the objective of the planning problem is taken into account. We test and compare the algorithms on several real world instances.