(1) Graduate Program in Systems Engineering
Department of Mechanical and Electrical Engineering
Universidad Autónoma de Nuevo León, Mexico
(2) Department of Industrial and Mechanical Engineering
Universidad de las Américas Puebla, Mexico
Abstract: In this work, we present a dual bounding scheme for a commercial territory design problem. This problem consists of 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 a binary search over a range of coverage distances. For each coverage distance a Lagrangian relaxation of a maximal covering model can be used effectively. Moreover, empirical evidence show that the bounding scheme provides tigher 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.