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

Juan A. Díaz (), Dolores E. Luna () and María G. Sandoval ()
Additional contact information
Juan A. Díaz: Ex Hacienda Santa Catarina Mártir
Dolores E. Luna: Ex Hacienda Santa Catarina Mártir
María G. Sandoval: Ex Hacienda Santa Catarina Mártir

Chapter Chapter 5 in Optimal Districting and Territory Design, 2020, pp 77-103 from Springer

Abstract: Abstract 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.

Keywords: Lower bounds; Upper bounds; Territory design; Compactness; Contiguity; Balance; p-median problem; Relaxation; Exact optimization method; Integer quadratic programming; Heuristic; Subgradient optimization; Lagrangian dual; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-030-34312-5_5

Ordering information: This item can be ordered from
http://www.springer.com/9783030343125

DOI: 10.1007/978-3-030-34312-5_5

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().