Fast Approximation Methods for Sales Force Deployment.
Sales force deployment involves the simultaneous resolution of four interrelated subproblems: sales force sizing, salesman location, sales territory alignment, and sales resource allocation. The first subproblem deals with selecting the appropriate number of salesman. The salesman location aspect of the problem involves determining the location of each salesman in one sales coverage unit. Sales territory alignment may be viewed as the problem of grouping sales coverage units into larger geographic clusters called sales territories. Sales resource allocation refers to the problem of allocating scarce salesman time to the aligned sales coverage units. All four subproblems have to be resolved in order to maximize profit of the selling organization. In this paper a novel nonlinear mixed-integer programming model is formulated which covers all four subproblems simultaneously. For the solution of the model we present approximation methods capable of solving large-scale, real-world instances. The methods, which provide lower bounds for the optimal objective function value, are benchmarked against upper bounds. On average the solution gap, i.e., the difference between upper and lower bounds, is about 3%. Furthermore, we show how the methods can be used to analyze various problem settings of practical relevance. Finally, an application in the beverage industry is presented.
Introduction
In many selling organizations, sales force deployment is a key means by which sales management
can improve profit. In general, sales force deployment is complicated and has attracted
much analytical study. It involves the concurrent resolution of four interrelated subproblems:
sizing the sales force, salesman 1 location, sales territory alignment, and sales resource al-
location. Sizing the sales force advocates selecting the appropriate number of salesmen. The
salesman location aspect of the problem involves determining the location of each salesman
in one of the available sales coverage units (SCUs). Sales territory alignment may be viewed
as the problem of grouping SCUs into larger geographic clusters called sales territories. Sales
resource allocation refers to the problem of allocating salesman time to the assigned SCUs.
Research has yielded some models and methods that can be helpful to sales managers.
The choice of the SCUs depends upon the specific application. SCUs are usually defined
in terms of a meaningful sales force planning unit for which the required data can be ob-
tained. Counties, zip codes, and company trading areas are some examples of SCUs (cp. e.g.
Zoltners and Sinha 1983 and Churchill et al. 1993). Note, it is more meaningful to
work with aggregated sales response functions on the level of SCUs rather than with individual
accounts because then substantially less response functions have to be estimated and
the model size does not explode (cp. e.g. Skiera and Albers 1996).
In literature, a large variety of different approaches are labeled with general terms like
'territory design', `resource allocation' or 'distribution of effort'. Frequently, from a modelling
point of view the multiple-choice knapsack problem is the matter of concern. This knapsack
model covers several important practical settings and - what has been a driving source for
its repeated use - can be solved very efficiently (cp. e.g. Sinha and Zoltners 1979). As
already mentioned 'resource allocation' addresses the question: How much of the available
time should each salesman allocate to the SCUs which are assigned to him?
Early work in this area has been published by e.g. Layton (1968), Hess and Samuels
(1971), Parasuraman and Day (1977), and Ryans and Weinberg (1979), respectively.
Waid et al. (1956) present a case study where the allocation of sales effort in the lamp
division of General Electric is investigated. Fleischmann and Paraschis (1988) study the
1 Note, we avoid the term 'salesperson' in order to make the `his/her' distinction superfluous.
case of a German manufacturer of consumer goods. For the solution of the case problem they
employ a classical location-allocation approach.
Sales resource allocation models consist of several basic components, i.e. sales resources,
sales entities, and sales response functions, respectively. As discussed in, e.g., Zoltners
and Sinha (1980) and Albers (1989), specific definitions for these components render
numerous specific sales resource allocation models. Beswick and Cravens (1977) discuss
a multistage decision model which treats the sales force decision area (allocating sales effort
to customers, designing sales territories, managing sales force, etc.) as an aggregate decision
process consisting of a series of interrelated stages.
The sales force sizing subproblem has been addressed by e.g. Beswick and Cravens
(1977) and Lodish (1980). The sales resource allocation subproblem has been analyzed,
among others, by Lodish (1971), Montgomery et al. (1971), Beswick (1977) and Zolt-
ners et al. (1979). Tapiero and Farley (1975) study temporal effects of alternative procedures
for controlling sales force effort. LaForge and Cravens (1985) discuss empirical
and judgement-based models for resource allocation. Allocation of selling effort via contingency
analysis is investigated by LaForge et al. (1986). The impact of resource allocation
rules on marketing investment-decisions is studied by Mantrala et al. (1992).
Among the four interrelated subproblems, so far the alignment subproblem has attracted
the most attention. For it, several approaches appeared in the literature. These approaches
can be divided between those which depend upon heuristics and those which utilize a mathematical
programming model. Heuristics have been proposed, among others, by Easingwood
(1973), and Heschel (1977). Two types of mathematical programming approaches have
been developed. Shanker et al. (1975) formulated a set-partitioning model. Alternatively,
the models of Lodish (1975), Hess and Samuels (1971), Segal and Weinberger (1977),
Zoltners (1976), and Zoltners and Sinha (1983) are SCU-assignment models. For an
overview see Howick and Pidd (1990).
Some of the papers published so far on the alignment subproblem aimed at aligning sales
territories in a way almost balancing with respect to one or several attributes. The most
popular balancing attributes are sales potential or workload of the salesmen. A detailed
discussion of the shortcomings of the balancing approaches can be found in Skiera and
Albers (1996) and Skiera (1996).
Glaze and Weinberg (1979) address the three subproblems of locating the salesmen, aligning
accounts and allocating calling time. More specific, they present the procedure TAPS
which seeks to maximize sales for a given salesforce size while attempting to achieve equal
workload between salespersons also and in addition minimizing total travel time.
Recently, Skiera and Albers (1994), (1996) and Skiera (1996) formulated a conceptual
model which addresses both the sales territory alignment and the sales resource
allocation problems simultaneously. Conceptual means that the sales territory connectivity
requirement is formulated verbally, but not in terms of a mathematical programming for-
mulation. For the solution of their model they propose a simulated annealing heuristic. The
objective of their model is to align SCUs and to allocate resources in such a way that sales
are maximized.
The remainder of the paper is structured as follows: In x2 the problem setting under consideration
is described as a nonlinear mixed-integer programming model. A fast method for
solving large-scale problem instances approximately is presented in x3. The results of an in-depth
experimental study are covered by x4. x5 discusses insights for marketing management.
A summary and conclusions are given in x6.
Programming Model
The larger the size of the sales force the more customers can be visited which in turn has a
positive impact on sales. On the other hand increasing the sales force size tends to increase
the operational costs per period. In addition, the number of possible calls to customers, the
operational costs and the salesmen's resource (time) which might be allocated to customers
is affected by the location of the salesmen, too. To make things even more complicated, the
alignment decision is very important for all these issues as well. Clearly, we have to take
care of all the mutual interactions of the different factors affecting the quality of the overall
sales force deployment. The aim of what follows is to provide a formal model which relates
all the issues to each other.
Let us assume that the overall sales territory has already been partitioned in a set of J
SCUs. The SCUs have to be grouped into pairwise disjoint sales territories (clusters) in such
a way that each SCU j 2 J is assigned to exactly one cluster and that the SCUs of each
cluster are connected. In each cluster a salesman has to be located in one of the assigned
SCUs, called sales territory center. Note, connected means that we can 'walk' from a location
to each assigned SCU without crossing another sales territory. I ' J denotes the subset of
SCUs which are potential sales territory centers. To simplify notation i 2 I denotes both the
sales territory center i and the salesman located in SCU i.
In practice, selling time consists of both the calling time and the travel time. For notational
purposes let denote z i;j the calling time per period which is spent by salesman i to visit
customers in SCU j. Further, assume b j 2 [0; 1] to denote the calling time elasticity of SCU
scaling parameter. Then
defines expected sales S i;j as a function of the time to visit customers. More
precisely, equation (1) relates z i;j and S i;j for all sales territories i 2 I and SCUs j 2 J .
Hence, via b j it is possible to take care of the fact that firm's competitive edge might be
different in different SCUs. Note, expected sales are defined via concave rather than s-shaped
functions, as is assumed to be the case with individual accounts (cp. Mantrala et al. 1992).
Let denote t i;j the selling time of salesman i 2 I in SCU j 2 J . Note, t i;j includes the time
to travel from SCU i to SCU j, the time to travel to customers in SCU j and the customer
calling time, respectively. Then, p relates the calling time z i;j to the selling t i;j .
Substituting z i;j in equation (1) by p i;j t i;j yields
Note, equation (2) has first been proposed by Skiera and Albers (1994). In equation (2)
the parameter
is introduced. c i;j measures the sales contribution when SCU j is part of sales territory i
where c i;j is a function of p i;j . This is best illustrated as follows: Suppose that for salesman i
the travel times to customers in SCUs j and k are different. Then in general p i;j and p i;k will
be different also. Clearly, this produces different parameters c i;j and c i;k - and puts emphasis
on the location decision.
Now we are ready to state the model formally. We summarize the model parameters
J set of SCUs, indexed by j
I set of SCUs (I ' J) for locating salesmen, indexed by i
set of SCUs which are adjacent to SCU j
fixed cost for locating a salesman in SCU i 2 I
c i;j expected sales if SCU j 2 J is covered by the salesman located in i 2 I
selling time available per period for salesman i 2 I
introduce the decision variables
x i;j =1, if SCU j 2 J is assigned to the salesman located in SCU i 2 I
t i;j selling time allocated by the salesman located in SCU i 2 I to SCU
and then formulate an integrated model for sales force sizing, salesman location, sales territory
alignment, and sales resource allocation as follows:
maximize
i2I
i2I
subject to
i2I
Objective (4) maximizes sales while taking fixed cost of the salesman locations into account
- and hence maximizes profit contribution or profit for short. The salesman i is allowed
to allocate selling time to SCU j only when SCU j is assigned to him (cp. equation (5)).
Equation (6) guarantees that the maximum workload per period (consisting of travel and
call time) and salesman is regarded. Equation (7) assigns each SCU to exactly one of the
salesmen. Equation (8) guarantees that all the SCUs assigned to one sales territory are
connected with each other. Note that these equations work similar to constraints destroying
short cycles in traveling salesman model formulations (an example can be found in Haase
1996). Clearly, it would be sufficient to take care of connected subsets
of SCUs only. Equations (9) and (10) define the decision variables appropriately.
So far we did not mention the following assumption which is covered by our model:
means that SCU i is assigned to the salesman located in sales territory i. In other
words, x does not only tell us where to locate salesman i, it also defines how to
align SCU i. This assumption is justified with respect to practice. Moreover, we assume by
definition of the binary alignment variables x i;j 2 f0; 1g that accounts are exclusively assigned
to individual salesman. Note, this is an assumption in marketing science and marketing
management because of several appealing reasons.
The model (4) to (10) has linear constraints, but a nonlinear objective. Furthermore, we
have continuous and binary decision variables. Therefore, there is no chance to solve this
model with standard solvers. In Haase and Drexl (1996) it is shown how the objective
function can be linearized in order to make the model accessible to mixed-integer programming
solvers (cp. Bradley et al. 1977 also where it is shown how to approximate nonlinear
functions by piece-wice linear ones). This makes it possible to compute upper bounds for
medium-sized problem instances which in turn facilitates to evaluate the performance of the
heuristics.
Clearly, all the parameters of the sales response function (1) have to be estimated. This
can be done as follows if a sales territory alignment already exists since several periods, i.e.
if our concern is to rearrange an already existing sales territory alignment. Then information
for each SCU about the sales, the time to travel to customers as well as the time to visit
the customers is already available. Usually, these informations can be extracted from sales
reports. In this situation b j and g j can be estimated as follows. Transform equation (1) to
equation
and then calculate estimates of b j and g j via linear regression. Finally, for the computation
of c i;j we need estimates of p i;j . In this regard the time to travel from SCU i to SCU j and
the time to visit the customers within SCU j are required. If salesman i has already covered
SCU j in the past we just have to look at his sales reports. Otherwise, we assume that the
time to travel within an SCU is independent from the salesman. Then the only information
required for a salesman k 6= i is the time to travel from k to i. This is easily available e.g.
from commercial databases or simply by assuming that the travel time is proportional to the
travel distance. In the case where the sales territory has to be designed from scratch, more
efforts are neccessary. Unfortunately, going into details is beyond the scope of this paper.
The four interrelated subproblems are addressed in our model by the decision variables
x i;j and t i;j . Let denote x
i;j and t
i;j an optimal solution for a given problem instance:
ffl Apparently, the optimal size of the sales force jIj which corresponds to the optimal number
of sales territories (clusters) is given by the cardinality of the set I = fi j x
1g.
ffl For each of the sales territories in the set I the SCU i with x
is the optimal location
of the salesman, i.e. the optimal sales territory center.
ffl For each sales territory i 2 I the optimal set J i of aligned sales territories or SCUs is
given by J
1g.
Finally, t
is the optimal sales resource allocation for
This interpretation of an optimal solution x
i;j and t
i;j illustrates that the model is 'scarce'
in the sense that two types of decision variables cover all the four subproblems of interest.
This suggests that in fact that the model is a suitable representation of the overall decision
problem. Moreover, it comprises the first step towards a solution of the problem.
The aim of the following section is to present heuristic methods which balance computational
tractability with optimality.
3 Approximation Methods
This section discusses a solution approach which has been developed specifically for the
model. Two reasons led to this development. First, standard methods of mixed-integer programming
seem to lend themselves to solving the linearized version of the model. However,
even for modestly sized problems the formulation translates into very large mixed-integer
programs which in turn result in prohibitive running times (for details see Haase and
Drexl 1996). In fact it is conjectured that - except for smaller problem sizes - no exact
algorithm will generally produce optimal solutions in a reasonable amount of time. Second,
apart from exact methods, so far no heuristic is available for solving the model. The simulated
annealing procedure of Skiera and Albers (1994), (1996) and Skiera (1996) solves
two of our subproblems, i.e. the sales territory alignment and the sales resource allocation.
Unfortunately, it does not tackle the sales force sizing and the salesman location subprob-
lems. In addition, although dealing only with two of the four subproblems in general the
running times of the simulated annealing procedure do not allow to solve large-scale problem
instances in a reasonable amount of time.
Our heuristic may be characterized as a construction and improvement approach. It
consists of the Procedure Construct and the Procedure Improve.
ffl The Procedure Construct determines the sales force size and hence the number of
salesman. In addition, it calls two other procedures: The Procedure Locate which
computes the SCU in which each salesman has to be located and the Procedure Align
which aligns the SCUs to the already existing sales territory centers.
ffl The Procedure Improve systematically interchanges adjacent SCUs of two different
clusters. This way it improves the feasible solution which is the outcome of the Procedure
Construct.
Note that the sales resource allocation subproblem can be solved as soon as all sales
territories are aligned by equation (13) or equation (14). Now, first we describe the procedures
designed to generate feasible solutions followed by the description of equations (13) and (14).
Then the improvement procedure will be presented.
3.1 Compute Feasible Solution
Recall J to denote the set of SCUs, I to be the set of SCUs which are potential
locations, and N j to denote the set of SCUs which are adjacent to SCU j, respectively. In
addition, let denote
S the minimum number of sales territory centers which might be established (S -
S the maximumnumber of sales territory centers which might be established (S - jIj)
s the 'current' number of sales territory centers (S - s - S)
I 1 the set of selected locations (jI
I 0 the set of non-selected locations
locations (i.e. SCUs) of the sales territory centers i 2 I 1
j(i) the SCU j where sales territory center i 2 I 1 is located in
center i to which SCU j is assigned to
J 0 the set of SCUs which are not yet aligned (initially J
J i the set of SCUs which are aligned to sales territory center i 2 I 1
sum of sales contributions of location
LB a lower bound on the optimal objective function value
Based on these definitions the set A i of SCUs which might be aligned to sales territory center
i may be formalized according to equation (12).
Note that the number of sales territory centers equals the number of salesmen (i.e. the sales
force size) which in turn equals the number of locations. Therefore, some of the newly introduced
parameters are superfluous, but this redundancy will be helpful for the description of
the procedures.
In the sequel Z will denote the objective function value of a feasible solution at hand.
Clearly, Z is a function of the decision variables x i;j and t i;j . The algorithms do not operate
on the set of x i;j variables, only the t i;j variables will be used directly. In what follows it is
more convenient to express the x i;j decisions partly also in terms of the number of salesman s,
and in terms of L(I 1
respectively. Redundancy will simplify the formal description and ease
understanding substantially. With respect to this redundancy Z(:::) will be used in different
variants, but from the local context it will be evident what it stands for.
We introduce a global variable lose[h; i]; h 2 I; i 2 I, which is used for locating the
salesmen in the set of potential locations. The variable lose[h; i] is a means for selecting some
elements of a probably large set I quickly. The meaning of lose[h; i] will be explained below
in more detail.
An overall description of the Procedure Construct is given in Table 1. Some comments
shall be given as follows: The Procedure Construct just consists of an overall loop which
updates the current number s of salesmen under consideration. Then it passes calls to Procedure
Locate and to Procedure Align and afterwards evaluates the resource allocation by
equation (13) or (14). Finally, the objective function values Z(s; x; t) and Z(s are
compared with the best known lower bound LB which is updated whenever possible. Note,
the number of salesman s for which search is performed is - without loss of generality -
restricted to the interval S - S.
Table

1. Procedure Construct
Initialize
call Procedure Locate
call Procedure Align (L(I1))
evaluate resources allocation by equation (13) or (14)
When a call to Procedure Locate is passed we start with jI I 1 which
implies I 1 " I I and initialize L(I 1 ). Note that the Procedure Locate uses
as calling parameter only the current number s of locations. A description of the Procedure
Locate is given in Table 2.

Table

2. Procedure Locate
Initialize
WHILE improve DO
update I0 and L(I1)
lose[ik
In the Procedure Locate the for-loop tells us that as starting locations L(I 1 ) the 'first'
j elements of the set I of potential locations are chosen. The procedure stops when within
the for-loop no further improvement of the set of locations can be found. As an outcome we
know the locations L(I 1 ) of the current number s of salesman.
Capitalizing on the definitions given above a compact description of the Procedure Align
is given in Table 3. Within the while-loop one of the not yet aligned SCUs is chosen and
aligned to one of the already existing sales territory centers. The criterion for chosing SCU
h and sales territory center i is motivated below.

Table

3. Procedure Align (L(I1))
Initialize
compute (h; i) such that c h;i =C
update A i
Apparently, as a final step of the overall Procedure Construct the sales resource allocation
subproblem has to be solved. This is done by evaluating equations (13) or (14), where a =
in the case of b
In the general case where b h allocation is done by equation (14).
are used for short, where fi i is the the 'average' elasticity
which has to be calculated by bisection search. Note, it is beyond the scope of this paper to
show how equation (14) can be derived and the reader is referred to Skiera and Albers
(1994).
3.2 Improve Feasible Solution
In general feasible solutions at hand can easily be improved by the following simple Procedure
Improve. For a compact description of the procedure we define two boolean parameters:
ae
connected
FALSE otherwise
ae
connected and j 6= j(i)
FALSE otherwise
The function add(V defines only those alignments to be feasible where we add SCU j to
the sales territory V i such that the newly derived sales territory consists of connected SCUs
only. Similarly, the function drop(V admits only alignments to be feasible where we drop
running into disconnectedness. In other words:
Both functions define those moves of an SCU j to/from a sales territory V i to be feasible
where the outcome does not violate the connectivity requirement. As a consequence, only
those SCUs are suspected move candidates which are located on the border of each of the sales
territories. In this respect the functions add(V are complementary. As a
consequence the Procedure Improve might be characterized as an interchange method, too.
Note that 'add' and `drop' are used in discrete location theory also (cp. e.g. Mirchandani
and Francis 1990 and Francis et al. 1992). Clearly, the resource allocation t i;j has to be
updated with respect to each move by evaluating equation (13) or (14).
A formal description of the Procedure Improve is given in Table 4. For the sake of com-
pactness, the calling parameter denotes the vector of sales territory alignments
currently under investigation and Z(V ) the corresponding objective function value,
respectively. us that the objective function value has to be computed
with respect to the current alignment under investigation where SCU j is subtracted
from sales territory V i(j) while sales territory V i is augmented by SCU j. Clearly, the computation
of the objective function requires an update of the resource allocation t i;j via equation
or (14) also.

Table

4. Procedure Improve (V )
Initialize improve = TRUE,
WHILE improve DO
Finally, we shall explain in more detail how the different procedures work and further
motivate why they are constructed the way they are:
ffl First, without any formal treatment we start off with the observation that - for 'reason-
able' parameters c i;j and f i - the objective function is concave with respect to the sales
force size, i.e. the number of salesman. Therefore, 'gradient search' within the interval
is implemeted in the Procedure Construct.
ffl Second, the global variable lose[h; i] is used in the Procedure Locate like in tournament
selection. The tournament is finished when the 'best' player h (i.e. the one which so
far has lost the least number of games) does not win against any other player k 2 I 1 .
As already mentioned above this is an effective means for selecting some elements of a
probably large set quickly.
ffl Third, the Procedure Align is greedy in the sense that the steepest ascent of the objective
function is used as criterion for the choice of the next SCU to be aligned. More precisely,
the choice depends on the ratios c h;i =C i , i.e. the rational is to take care of the relative
weights of the expected sales contributions.
ffl Fourth, the Procedure Improve belongs to the variety of local search methods (for a
survey of advanced local search methods cp. e.g. Pesch 1994). In order to keep our
explanations as simple as possible we distract our attention from the resource allocation
t i;j . Starting with an incumbent sales territory alignment we search all its
neighboors - x 2 H(x), where H(x) equals the set of feasible solutions which are properly
defined by the functions add(V called neighborhood of x.
Searching over all neighboors -
in a steepest ascent manner may be characterized
as a 'best fit strategy'. By constrast, a `first fit strategy' might by less time consuming
while presumably producing inferior results.
ffl Fifth, the Procedures Construct and Improve comprise deterministic methods. In the
next section we will show that these simple deterministic methods produce already very
promising results. Therefore, there is no necessity to make the methods more sophisticated
(and more complicated) by incorporating either self-adaptive randomization concepts
(cp. e.g. Kolisch and Drexl 1996) or procedure parameter control techniques
adopted from sequential analysis (cp. e.g. Drexl and Haase 1996). Furthermore, if
desired it is straightforward to incorporate simulated annealing randomization schemes
(for a comprehensive introduction into the theory and techniques of simulated annealing
cp. e.g. Johnson et al. 1989, 1991).
Finally, when solving difficult combinatorial optimization problems one is likely going to
be trapped in local optima when searching greedily in a steepest ascent manner only.
Therefore, numerous researchers have devised (less greedy) steepest ascent/mildest descent
procedures which provide the ability to escape from local optima while avoiding
cycling through setting some moves 'tabu' (for a comprehensive introduction into the
theory and techniques of tabu search see e.g. Glover 1989, 1990). While, clearly, there
might be some potential for improvement there seems to be no necessity in this respect
to incorporate tabu search techniques.
4 Experimental Evaluation
The outline of this section is as follows: First, we elaborate on the instances which are used
in our computational study. Second, we describe how to compute benchmark solutions in
order to judge the performance of the methods presented in the preceeding section. Third,
numerical results will be presented.
Even in current literature, the systematic generation of test instances does not receive
much attention. Generally, two possible approaches can be found adopted in literature when
having to come up with test instances. First, practical cases. Their strength is their high
practical relevance while the obvious drawback is the absence of any systematic structure
allowing to infer any general properties. Thus, even if an algorithm performs good on some
practice cases, it is not guaranteed that it will continue to do so on other instances as
well. Second, artificial instances. Since they are generated randomly according to predefined
specifications, their plus lies in the fact that fitting them to certain requirements such as
given probability distributions poses no problems. detailed such procedure for generating
project scheduling instances has been recently proposed by Kolisch et al. 1995). However,
they may reflect situations with little or no resemblance to any problem setting of practical
interest. Hence, an algorithm performing well on several such artificial instances may or may
not perform satisfactorily in practice. Therefore, we decided to devise a combination of both
approaches, thereby attempting to keep the strenghts of both approaches while avoiding their
drawbacks.
4.1 Practical Case
First, we used the data of a case study which have been compiled by Skiera (1996) in order
to evaluate his simulated annealing procedure. This instances are roughly characterized as
follows: The company is located in the northern part of Germany. The sales region covers
the whole area of Germany. The sales territory is partitioned into 95 SCUs (two-digit postal
areas). The number of salesman employed is ten where the location of each salesman, i.e. the
sales territory center is assumed to be fixed. Then the sales force sizing and the salesman
location subproblems are (presumed to be) of no relevance. For the remaining two subproblems
the solutions currently used by the company and the solution computed by Skiera
are available as a point of reference for our procedure. While, clearly, all the data
available are of great practical interest we refrain, however, from the tedious task of citing
all the respective details. 2
4.2 Generation of Instances
Second, we generated instances at random. We assumed that only two instance-related factors
do have a major impact on the performance of the algorithms, viz. the cardinality of the set
I of potential sales territory centers and the cardinality of the set J of SCUs, respectively.
Both factors relate to the 'size' of a problem, hence (I; J) denotes the size of an instance.
When generating instances at random a critical part is the specification of a connected
sales territory. In order to do so we employ the Procedure Generate which is able to generate
a wide range of potential sales territories while preserving connectivity. The basic idea is to
define a set squares located on a grid.
For every unit square (ff; fi) 2 K the set of adjacent unit squares N (ff;fi) or neighbours is
defined as follows:
The Procedure Generate is formally described in Table 5. As calling parameters the set of
sales territory centers I and the set of SCUs J are used. Note that - starting with the 'central'
- the set M is incremented until it equals the set of SCUs J
which have to be generated while preserving connectivity of the sales territory. Similar to the
Procedure Align A denotes the set of those unit squares of the grid which are candidates to
be aligned to the already generated sales territory. In a last step the set of sales territories
I is chosen at random.

Table

5. Procedure Generate (I; J)
Initialize
chose (ff; fi) 2 A at random
chose I ' J sales territories at random
It is easy to verify that the Procedure Generate is capable to produce a large range of
quite different shaped sales territories. Nevertheless, the question is whether this construction
process which basically relies on unit squares and hence on SCUs of equal size does produce
instances which are meaningful for the methods to be evaluated? The answer is 'yes' because
the grouping, i.e. building of larger units is just what the Procedure Align does.
Summarizing the instances treated in the computational study are characterized as follows

ffl The set of SCUs J is given by f50, 100, 250, 500g.
ffl The set of potential sales territory centers I is given by f10, 25, 50g.
ffl The scaling parameter g j is chosen at random out of the interval [10, 210].
ffl The expected sales c i;j equal where the distances d i;j are computed as follows:
ae
2 All the instances used in this study are available on our ftp-site under the path /pub/operations-
research/salesforce via anonymous ftp.
b was set to 0.3 with respect to empirical findings of Albers and Krafft (1992). As a
consequence because of travel times being proportional to travel distances d i;j expected
sales c i;j decrease the longer the distance between i and j is and vice versa.
ffl The fixed cost f i of sales territory centers are drawn at random out of the interval [750,
1,250].
ffl The maximum workload T i per period and salesman is set to 1,300 for all i 2 I. This is
an estimate of the annual average time salesman in Germany have to work (cp. Skiera
and Albers 1994).
ffl The lower bound S for the number of sales territory centers is set to 0 while the upper
bound S equals jIj.
Note, to calculate the scaling parameter g j at random as described above might not be
the best choice whenever the data are spatially autocorrelated. While, certainly, it is not that
difficult to generalize the generator such that autocorrelation is covered also we do not follow
these lines here because of the following reason: The practical case described in Subsection
4.1 has spatially autocorrelated data. Solving the practical case with our procedures is by no
means more difficult than solving the artificial instances (details are provided below). Hence,
we refrain from introducing some more parameters in order to get a more 'realistic' instance
generator.
Clearly, only 'reasonable' combinations of J and I are taken into account (details are
provided below). In addition, due to the computational effort required to attempt all the
sizes only ten instances were considered in the experiment for each instance class (J; I).
4.3 Computation of Benchmarks
Unfortunately, it is not possible to solve the nonlinear mixed-integer programming (NLP-)
model (4) to (10) by the use of a 'standard' solver. Hence, even for small-sized problem
instances there is no 'direct' way to get benchmarks. Consequently, in a companion paper
(cp. Haase and Drexl 1996) the model (4) to (10) has been reformulated as a mixed-integer
linear programming (MIP-) model. In order to do so one has to replace the nonlinear
objective by a piecewise-linear one such that an optimal solution of the MIP-model provides
a lower bound for the NLP-model. Clearly, solving the LP-relaxation of the MIP-model yields
an upper bound of the optimal objective of the NLP-model and, hence, benchmarks.
The LP-relaxation of the MIP-model can be solved directly by the use of one of the
commercially available LP-solvers. This way it is possible to compute upper bounds for
problems having up to territories in a reasonable amount
of time. A more efficient approach uses the MIP-model within a set partitioning/column
generation framework. Going into details is beyond the scope of this paper and the interested
reader is referred to Haase and Drexl (1996).
4.4 Computational Results
The algorithms have been coded in C and implemented on a 133 Mhz Pentium machine
under the operating system Linux. The parameter K of the Procedure Generate is defined
to be used. Note, FAC ? 1 serves to generate
sales territories where not all units form part of the overall sales region, i.e. lakes and other
'non-selling' regions can be included also.

Table

6 provides a comparison of lower and upper bounds. Columns 1 and 2 characterize
the instance class, i.e. problem size under consideration in each row in terms of jJ j and jIj,
respectively. Columns 3 and 4 report the results which have been obtained using the LP-solver
of CPLEX (cp. CPLEX 1995). More specific, column 3 provides the average upper bound
UB which has been obtained by solving the LP-relaxation of the linearized version. Column
4 shows the average CPU-time in sec required to compute UB. Recall that averages over ten
instances for each row, i.e. instance class (J; I), are provided. Columns 5 to 7 with the header
Table

6. Comparison of Lower and Upper Bounds
CPLEX CONIMP
50 13,271.83 49.20 12,736.17 2.60 4.04
50 29,583.04 172.60 28,464.76 13.50 3.73
500 50 133,702.41 3,424.34 130,962.26 626.70 2.05
CONIMP present the results of the Procedures Construct and Improve. More specific, LB
cites the average best feasible solution, i.e. lower bound computed. CPU denotes the average
CPU-time in sec required by the algorithms to compute LB. - 1 denotes that the average
is only an ffl above zero sec. Finally,
UP
measures the average percentage
deviation between upper and lower bound, i.e. the solution gap. Note, GAP covers both
the tightness of the LP-relaxation and the deviations of the lower bounds obtained from the
optimal objective function values. On the average, the solution gap roughly equals
3%. Hence, the feasible solution computed indead must be very close to the optimal one.

Table

7. Comparison of the Procedures Construct and Improve
CON IMP
50 28,416.35 13.40 28,464.76 0.10 0.17
500 50 129,746.85 544.70 130,962.26 82.00 0.94
Now the question shall be answered which of the Procedures Construct or Improve contributes
to which extent to the fact that the lower bounds are very close to the optimum.

Table

7 gives an answer. The header CON groups the information provided with respect
to the Procedure Construct while the header IMP does so for the Procedure Improve. In
the former case LB denotes the lower bound obtained while in the latter one it shows the
additional improvement. In both cases CPU denotes the required CPU-time in sec. AP I
provides the average percentage improvement.
It has already been mentioned that our model is more general than the one of Skiera and
Albers (1996) because it covers the sales force sizing and the salesman location subproblems
also. Consequently, our methods cover the more general case, too. Surprisingly, although
being more general, our methods are more efficient than the simulated annealing method
of Skiera and Albers. While our algorithms solve the practical case close to optimality
in a CPU-time - 1 sec, the simulated annealing method requires up to ten minutes on a
80486 DX-33 machine to do so. Moreover, the solution computed by our algorithms is slightly
better than the one found by the simulated annealing method. Note, suboptimality means
that profit increase is about 5% compared with the alignment used by the company so far.
Clearly, the run-times of the simulated annealing algorithm will become prohibitive when
applied to large-scale problem instances.
Regarding the results reported in Tables 6 and 7 some important facts should be emphasized

Roughly speaking, the solution gap decreases from 4% to 2% while the size of the instance
increases, because of two reasons. First, relaxing the connectivity requirements makes
the LP-bounds for small problem instances weak compared to large ones. Second, the
quality of the piece-wise linear approximation increases with increasing problem size and
hence makes the LP-bounds more tight.
ffl The larger the cardinality of the set I the more time has to be spent in evaluating the
size and the location of the sales force. Clearly, this takes the more CPU-time the larger
I is in relation to J . From another point of view, if there is no degree of freedom with
respect to the size of the sales force and the location of the salesmen, i.e. then the
alignment and the allocation subproblems are solved very effective and very efficient by
our algorithms also. This decidedly underlines the superiority of our approach compared
to the one of Skiera and Albers (1996).
ffl In general, the quality of the solutions computed by the procedure Construct is already
that good that only minor improvements can be obtained subsequently. In other words,
exploiting the degree of freedom on the level of the sizing and the locating decisions
appropriately already gives an overall sales force deployment which is hardly to improve
by realigning some of the SCUs.
The scope of the experiment conducted so far was to show how good our algorithms
work. Seriously this can only be done with respect to the optimal objective function or at
least an upper bound. Therefore, the experiment was limited to include only instances of the
size for which the LP-relaxation of the MIP-model can be solved in reasonable time. Clearly,
there is no obstacle for using the algorithms on larger instances which might become relevant
e.g. in a global marketing context. The CPU-times required by our procedure show that for
really huge instances comprising thousands of SCUs it is possible to compute near-optimal
solutions within some hours of computation. Summarizing there is no obstacle for using the
algorithms even on very large instances.
5 Insights for Marketing Management
In what follows we will discuss managerial implications of our findings. More precisely, we
will state some insights and subsequently assess their validity on basis of experiments.
Insight 1: The results are robust with respect to wrong estimates of parameters.
In order to evaluate insight 1 we took one of the instances with jJ
potential locations. Now assume that b 0:3 and the c i;j which are generated along the
lines described in Subsection 4.2 8j 2 J and i 2 I are the (unknown, but) 'true' values of
the parameters of the sales response function. The parameters - b and - c i;j which are used in
the experiment are then generated via data perturbation as follows: Calculate -
and choose - c i;j 2 [c i;j at random where \Deltac and \Deltab are perturbation
control parameters.

Table

8 presents the results of this study. Across rows and columns we provide the percentage
decrease
OPT
\Delta 100 of profit where OPT denotes the 'optimal' objective
value which has been calculated based upon the 'true' parameter values while ACT
is the one which has been computed with respect to the perturbed parameters. The results
show that even in the case when the parameters are estimated very 'bad' (i.e. all of them are
under- or overestimated drastically) the percentage decrease of profit does hardly exceed 3%.

Table

8. Robustness of the Model
\Deltab -0.10 -0.05 0.00
Insight 2: Profit is not that sensitive with respect to sales force size.
In order to evaluate insight 2 once more we took the instance with jJ
potential locations. Then, the size of the sales force was set to the levels 29, 30,
by fixing accordingly. Table 9 provides the results of this experiment.
OFV denotes the objective function value (normalized to the interval [0; 1]) which has
been computed by our methods with respect to the size s. The results which are typical for
various other experiments not documented here support insight 2 which means that the objective
function is fairly flat near the optimum number of salesmen. Hence, the 'flat maximum
principle' (cp. Chintagunta 1993) is valid also in this context.

Table

9. Profit as Function of Sales Force Size
s OFV
29 0.99577
Insight 3: Profit is sensitive with respect to the location of the salesmen.
Once more we relate to the instance already used twice. Table 10 provides part of the protocol
of a run. More precisely, the outcome of some typical iterations of the Procedure Locate
where potential locations are evaluated systematically is given in terms of normalized objective
function values OFV (s). Similar to Table 9 the size of the sales force is fixed in each row.
Clearly, the process converges to the best found objective function value (hence, OFV
1 in column seven), but the values go up and down depending on the specific old and new
locations under investigation. Hence, the 'flat maximum principle' is not valid with respect
to the location of the salesmen.

Table

10. Profit as Function of Location of Salesmen
s OFV Iterations
29 0.934 0.960 0.947 0.973 0.986 1.000
The insights evaluated in Tables 8, 9 and 10 can be summarized as follows:
ffl For reasonable problem parameters the size of the sales force does not affect firm's profit
that much.
ffl The location of the salesmen in general will affect firm's profit drastically. Consequently,
existing alternatives must be evaluated.
ffl Fortunately, the model is very robust with respect to the estimation of the parameters of
the sales response function. Even in the case when there is a systematic estimation bias
(over- or underestimation of all the parameters) the decision is not that bad in terms
of firm's profit. Usually, there is no systematic bias, hence, the sales force deployment
evaluated by the algorithms will be superb.
6 Summary and Conclusions
In this paper it is shown how four interrelated sales force deployment subproblems can be
modelled and solved simultaneously. These subproblems are: sizing the sales force, salesman
location, sales territory alignment, and sales resource allocation. More specific an integrated
nonlinear mixed-integer programming model is formulated. For the solution of the model we
present a newly developed effective and efficient approximation method.
The methods are evaluated on two sets of instances. The first one stems from a case study
while the second one is based on the systematic generation of a representative set of problem
instances covering all problem parameters at hand. The results show that the method allows
to solve large-scale instances close to optimality very fast.
The methods which provide lower bounds for the optimal objective function value are
benchmarked against upper bounds. On the average the solution gap, i.e. difference between
upper and lower bound, is roughly 3%. Furthermore, it is shown, how the methods can be
used to analyze various problem settings which are of highly practical relevance. Hence,
the methods presented in this paper are effective and efficient and will be very helpful for
marketing management.



--R

Entscheidungshilfen f?
"Steuerungssysteme f?r den Verkaufsau-endienst"
"Allocating selling effort via dynamic programming"
"A multistage decision model for salesforce manage- ment"
Applied Mathematical Programming.
"Investigating the sensitivity of equilibrium profits to adverstising dynamics and competitive effects"
Sales Force Management.
CPLEX Inc.
"Sequential-analysis based randomized-regret-methods for lot-sizing and scheduling"
"A heuristic approach to selecting sales regions and territories"
"Solving a large scale districting problem: a case report"
Facility Layout and Location - An Analytical Approach
"A sales territory alignment program and account planning system (TAPS)"
search - Part I"
search - Part II"
"Deckungsbeitragsorientierte Verkaufsgebietseinteilung und Standortplanung f?r Au-endienstmitarbeiter"
"Sales force deployment by mathematical programming"
"Effective sales territory development"
"Experiences with a sales districting model: criteria and implementation"
"Sales force deployment models"
"Optimization by simulated annealing: an experimental evaluation - Part I: graph partitioning"
"Optimization by simulated annealing: an experimental evaluation - Part II: graph colouring and number partitioning"
"Adaptive search for solving hard project scheduling problems"
"Characterization and generation of a general class of resource-constrained project scheduling problems"
"Empirical and judgement-based sales-force decision models: a comparative analysis"
"Using contingency analysis to select selling effort allocation methods"


"Sales territory alignment to maximize profit"
"A user-oriented model for sales force size, product, and market allocation decisions"
"Impact of resource allocation rules on marketing investement-level decisions and profitability"



Learning in Automated Manufacturing - A Local Search Approach
"Territory sales response"
"Turfing"
"Sales territory design: an integrated approach"
"The multiple-choice knapsack problem"
"Verkaufsgebietseinteilung zur Maximierung des Deckungsbeitrages"
"COSTA: Ein Entscheidungs-Unterst-utzungs-System zur deckungsbeitragsmaximalen Einteilung von Verkaufsgebieten"
"COSTA: Contribution optimizing sales territory alignment"


"Integer programming models for sales territory alignment to maximize profit"
"Integer programming models for sales resource allocation"
"Sales territory alignment: a review and model"

--TR
marketing models;salesman location;Application/Distribution of Beverages;Sales Force Sizing;Sales Territory Alignment;Sales Resource Allocation