A reactive GRASP for a commercial territory design problem with multiple balancing requirements

https://doi.org/10.1016/j.cor.2007.10.024Get rights and content

Abstract

In this paper we present a reactive GRASP approach to a commercial territory design problem motivated by a real-world application in a beverage distribution firm. The mathematical framework includes, as planning criteria, minimizing a measure of territory dispersion, balancing the different node activity measures among territories and territory contiguity. The proposed GRASP approach incorporates several features such as reactivity, by allowing self-adjustment of the restricted candidate list quality parameter, and filtering, which avoids executing the local search phase in unpromising bad solutions generated by the construction phase. The algorithm has been tested in several data sets. The results show the effectiveness of the proposed approach. It was observed that the reactivity and the filtering proved very useful in terms of feasibility with respect to the balancing constraints, and find more robust solutions when tested over the basic GRASP. The local search scheme proved to be very effective as well. Moreover, the proposed approach obtained solutions of much better quality (in terms of both its dispersion measure and its feasibility with respect to the balancing constraints) than those found by the firm method in relatively fast computation times.

Introduction

The sales territory design problem (TDP) may be viewed as the problem of grouping small geographic sales coverage units (SCUs) into larger geographic clusters, called sales territories, in a way that the territories are acceptable (or optimal) according to relevant planning criteria. This problem belongs to the family of districting problems that have a broad range of applications like political districting and the design of sales and services territories. The recent paper by Kalcsics et al. [1] is an extensive survey on approaches to territory design that gives an up to date state of the art and an unifying approach to the topic.

The problem addressed in this paper is motivated by a real-world application from a beverage distribution firm in the city of Monterrey, Mexico, and may be viewed as a sales TDP, where rather than placing salesmen in territories we are interested in locating centers for the purpose of modeling the compactness measure. To make a clear distinction between a sales TDP and our problem, we call ours a commercial TDP, meaning the interest is placed on providing customers with a commercial service by the firm. Although several sales territory design approaches have appeared in the literature [2], [3], [4], [5], [6], the specific features present in this concrete problem make it very unique, and not addressed before to the best of our knowledge. The firm wishes to partition the area of the city into disjoint territories that are suitable for their commercial purposes. In particular, the firm wants to design territories that are balanced (similar in size) with respect to each of three different activity measures (number of customers, product demand, and workload). There are in addition several requirements that are posed by the firm, which are derived from their planning criteria and from regulations and agreements with the work force. They are: (i) contiguity of each territory, so that SCUs can reach each other by traveling within the territory, (ii) territory compactness, so that customers within a territory are relatively close to each other, and (iii) a fixed number of territories.

The characteristics of the problem together with the fact that the number of territories is given have led us to model the problem as a p-center problem where we are interested in locating p centers, one for each territory. It is clear that for modeling this problem in principle it is not needed to associate a center with each territory. However, this gives us a simple tool for defining a compactness measure and for formulating the contiguity requirements. We chose a center (minsum) objective function rather than a median (sum) one, since this is the type of objective function that is typically used in discrete location when it is sought that no customer be “too” far away from the facility it is assigned to. In our opinion this gives us an appropriate measure for modeling compactness, even if one can always build examples where the median would also be suitable.

In this work, we present and discuss a modeling framework for this NP-hard combinatorial optimization problem, and we propose a solution algorithm based on GRASP (greedy randomized adaptive search procedure) to construct high-quality solutions. We have taken a distance-based dispersion measure of the territories as the objective for the proposed model.

The specification that the territories be simultaneously balanced with respect to all the three measures has been modeled by requiring that each territory be within a threshold of a target value for each activity measure. This is motivated by the fact that for a given instance a solution where all the territories are simultaneously balanced with respect to all three measures may not exist.

GRASP is a well-known metaheuristic that has been widely used for successfully solving many combinatorial optimization problems. Broadly speaking, GRASP usually gives a good compromise between the quality of the obtained results and the required computational effort. For the problem that we address we chose GRASP for several reasons: First, since the problem corresponds to a real application, we were interested in implementing a simple efficient algorithm that could be easily understandable by the firm and required as little tuning as possible, for future applications by the firm to possibly different data. Also, to the best of our knowledge, this type of approach has not been considered before for general TDPs with distance-based dispersion measures.

It is true that more sophisticated heuristic methods (like Tabu Search, Scatter Search, or Path Relinking) can outperform the basic versions of GRASP algorithms, but it is also true that they require more sophisticated data structures and their computational requirements tend to be higher. It is also true that the performance of basic GRASP versions can be improved by incorporating additional features that to some extent take into account specific characteristics of the problem or the history of the search process.

In our case the basic version of GRASP has been improved with several additional features. On the one hand, since the local search phase typically increases considerably the required computation time of any GRASP algorithm, we have included a filtering mechanism according to which the local search phase is only applied to those solutions that, based on the history of the search, seem likely to produce a good quality improved solution. On the other hand, we have implemented a reactive GRASP (R-GRASP) algorithm that, by taking also into account the history of the process, does not require tuning the parameter that regulates the size of the restricted candidate list (RCL) in the constructive phase, which is crucial to the success of the process. In addition, all the versions of the GRASP that we propose allow for strategic oscillation, since the capacity constraints are relaxed, and incorporated to the objective function via a penalty term.

We have run a series of computational experiments to assess the efficiency of the proposed GRASP algorithms, and to evaluate the behavior of our approach when compared to current industry practices. In particular, in these experiments we have analyzed the effect on the obtained solutions of different threshold values for the balancing constraints. Given that the most time consuming phase of the procedure is its local search, we have also studied the impact of applying a filter to avoid executing this phase in unpromising bad solutions generated by the construction phase. The obtained results are very satisfactory since we obtain solutions of much better quality than that of the solutions obtained by the firm method when applied to the same set of instances. The proposed approach runs in relatively small computation times.

The paper is structured as follows. In Sections 2 and 3 we describe the problem and we present the model that we follow, respectively. Section 4 gives an overview of some previous related work. Section 5 gives the elements of our algorithm, and Section 6 describes the experiments that we have run and the obtained results. We end the paper in Section 7, with some conclusions and final comments.

Section snippets

Problem description

The problem is modeled by a graph G=(V,E), where a city block or SCU i is associated with a node, and an arc connecting nodes i and j exists if blocks i and j are adjacent to each other. Now each node iV has several associated parameters such as geographical coordinates (cix,ciy), and three measurable activities. Let wia be the value of activity a at node i, where a=1 (number of customers), a=2 (product demand), and a=3 (workload). A territory is a subset of nodes VkV. The number of

MILP formulation

Indices and sets

nnumber of blocks (SCUs)
pnumber of territories
i,jblock indices; i,jV={1,2,,n}
aactivity index; aA={1,2,3}
kterritory index; kK={1,2,,p}
Eedge set of adjacent blocks
Ni(={jV:(i,j)E(j,i)E}) set of nodes which are adjacent to node i; iV
Parameters
wiavalue of activity a in node i; iV, aA
dijEuclidean distance between i and j; i,jV
τarelative tolerance with respect to activity a; aA, τa[0,1]
Computed parameters
wa(B)(=jBwja) size of set B with respect to a; aA, BV
μa(=wa(V)/

Related work

The grouping of small geographical units into larger geographical clusters according to some specified planning criteria is referred to in the literature as districting or territory design. Many authors have investigated districting problems and developed models and algorithms in several contexts, most importantly: design of sales territories [1], [3], [4], [5] and design of political districts [8], [9], [10], [11], [12], [13]. Other applications include turfing in telecommunications [14],

Solving the TDP by GRASP

GRASP [19], a fairly well-known metaheuristic that captures good features of both pure greedy algorithms and random construction procedures, has been widely used for successfully solving many combinatorial optimization problems. This type of approach has not been considered before for general TDPs as far as we know.

A GRASP is an iterative process in which each major iteration consists typically of two phases: construction and post-processing. The construction phase attempts to build a feasible

Empirical work

In this section we present experimental results obtained with a C++ implementation of the GRASP for this TDP. The procedure was compiled with the Sun C++ compiler workshop 8.0 under the Solaris 9 operating system and run on a SunFire V440. For the experiments, randomly generated instances based on real-world data provided by the industrial partner were generated. Two different data sets are considered, namely DS and DT.

Data set DS: For this set each instance topology was randomly generated as a

Conclusions

In this paper we have presented a GRASP approach to a sales territory design problem with multiple node balance requirements. The problem that is motivated by a real-world application in the beverage industry includes several planning criteria such as compactness, balancing among territories, contiguity, and connectivity. Each of the GRASP components was fully evaluated over a range of instances randomly generated according to real-world scenarios. The reactive GRASP with filtering was very

Acknowledgments

The research of the first author was supported by the Spanish State Secretary for Universities and Research under its Visiting Scholar Program (grant SAB2004–0092), the Mexican National Council for Science and Technology under its Basic Research Program (Grant SEP-CONACYT 48499–Y), and Universidad Autónoma de Nuevo León under its Scientific and Technological Research Support Program (Grant UANL-PAICYT CA1478–07). The second author was supported by Grant MTM2006–14961–C05–01 of the

References (21)

There are more references available in the full text version of this article.

Cited by (0)

View full text