A dual bounding scheme for a territory design problem

作者：Elizondo Amaya Monica G^*; Rios Mercado Roger Z; Diaz Juan A

来源：Computers & Operations Research, 2014, 44: 193-205.

DOI：10.1016/j.cor.2013.11.006

• Commercial territory design
• Discrete location
• Lagrangian relaxation
• Dual bounding scheme

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.

• 出版日期2014-4