A dual bounding scheme for a territory design problem

In this work, we present a dual bounding scheme for a commercial territory design problem. This problem consists of finding a p-partition of a set of geographic units that minimizes a measure of territory dispersion, subject to multiple balance constraints. Dual bounds are obtained using binary search over a range of coverage distances. For each coverage distance a Lagrangian relaxation of a maximal covering model is used effectively. Empirical evidence shows that the bounding scheme provides tighter lower bounds than those obtained by the linear programming relaxation. To the best of our knowledge, this is the first study about dual bounds ever derived for a commercial territory design problem.