Bounding Procedures and Exact Solutions for a Class of Territory Design Problems

In this chapter, we present and evaluate exact methods and lower and upper bounding procedures for a class of territory design problems. Most territory design problems, as the one studied in this chapter, consider requirements of compactness, contiguity, and balance with respect to one or more activity measures, for example, number of customers and sales volume in the case of commercial territories, voting potential equality in the case of political territories, workload balance when designing service territories, etc. To obtain solutions with compact territories, a minisum objective function equivalent to the objective function of the p-median problem is used. The exact solution methods presented here use different relaxations of integer linear programming formulations of the problem. Additionally, two methodologies to obtain upper bounds (feasible solutions) are presented. The first one uses the relaxation of an integer quadratic programming formulation. The second methodology obtains feasible solutions using a primal heuristic within the framework of a subgradient optimization algorithm to solve a Lagrangian dual that also provides lower bounds for the optimal solution. Instances obtained from the literature are used to evaluate and compare the different methodologies presented.