HMIP Model for a Territory Design Problem with Capacity and Contiguity Constraints

HMIP Model for a Territory Design Problem with Capacity and Contiguity Constraints

Fabian Lopez (Universidad Autónoma de Nuevo León (CEDEEM), México)
DOI: 10.4018/978-1-61350-086-6.ch011
OnDemand PDF Download:


Small geographic basic units (BU) are grouped into larger geographic territories on a Territory Design Problem (TDP). Proposed approach to solve a TDP is presented through a study case developed on a large soft drinks company which operates in the city of Monterrey, México. Each BU of our TDP is defined by three activity measures: (1) number of customers, (2) sales volume and (3) workload. Some geographic issues about contiguity and compactness for the territories to be constructed are considered. An optimal solution is obtained when the constructed territories are well balanced taking into consideration each activity measure simultaneously. In particular, contiguity is hard to be represented mathematically. All previous research work indicates that this NP-Hard problem is not suitable for solving on large-scale instances. A new strategy which is based on a hybrid-mixed integer programming (HMIP) approach is developed. Specifically, our implementation is based on a Cut-Generation Strategy. We take advantage from territory centers obtained through a relaxation of a P-median based model. This model has a very high degree of connectivity. Thus, small number of iterations to find connected solutions is required. The authors detail out their methodology and then they proceed to its computational implementation. Experimental results show the effectiveness of our method in finding near-optimal solutions for very large instances up to 10,000 BU’s in short computational times (less than 10 minutes). Nowadays, this model is being used by the firm with important economical benefits.
Chapter Preview

Background And Some Applications For Territory Design

The criteria for defining a meaningful territory design lie in the purpose of the studies and depend mainly on each particular case. These criteria are often guided by the problem specifications or even more restricted by the available data. For a sales territory context, well–planned decisions enable an efficient market penetration and lead to decreased costs and improved customer service. By the other hand in terms of political districting, an algorithmic approach protects against politically motivated manipulations during the territory design process. Either way, the most commonly used set of criteria includes contiguity, compactness and balanced territories. We can define Compactness as the spatial property of being close and firmly united (i.e. having the minimum distance between all the entities of a given area). We define Contiguity as a continuous connection of a group of entities throughout an unbroken sequence and sharing a common border. Researchers and practitioners have put diverse opinions on what other design criteria to consider. These include:

Complete Chapter List

Search this Book: