Competitive Location and Pricing on
Networks
Daniel Serra

Dept. of Economics and Business
Universitat Pompeu Fabra
and
Charles ReVelle
Dept. of Geography and Environmental Engineering
The Johns Hopkins University
Abstract
In this paper we consider a location and pricing model for a retail rm
that wants to enter a spatial market where a competitor rm is already
operating as a monopoly with several outlets. The entering rms seeks
to determine the optimal uniform mill price and its servers' locations
that maximizes prots given the reaction in price of the competitor rm
to its entrance. A tabu seach procedure is presented to solve the model
together with computational experience.
Key words : competitive location, discrete network location, spatial pricing
Journal of Economic Literature classication: C61, R32,L81,R12

Corresponding author: Daniel Serra, Department of Economics and Business,
Universitat Pompeu Fabra, Trias Fargas 25-27, Barcelona 08005, Spain. Tel: 34-3-
5421666, Fax: 34-3-5421746, e-mail: serra@upf.es
1 Introduction
Hotelling's work on two rms competing in a linear market with consumers
distributed uniformly along the line (also known as the ice{cream vendor prob-
lem) set the foundations of what is today the burgeoning eld of competitive
location. Competitive location is not only important from a practical point
of view. It is also intriguing because, as Eiselt and Laporte (1989) point out,
by modifying the original assumptions of the model the results obtained may
dier signicantly from Hotelling's conclusions: \relatively small changes in
the model assumptions result in dramatic changes in the outcome" (p.237).
During the late thirties and early forties, several papers using the same
spatial representation as Hotelling but modifying some of the economic as-
sumptions appeared in the economic literature (Hoover (1936), Lerner and
Singer (1937), and Smithies (1941)). There followed several decades of stag-
nation in the contribution of new insights in the eld of competitive location
in linear markets. Since the late seventies however, a myriad of dierent
models have appeared in the literature of spatial economics and industrial or-
ganization. Useful reviews can be found in Ponsard (1983), Graitson (1987),
Gabszewicz and Thisse (1991), and Eiselt and Laporte(1989).
Much of the eort in the new evolving literature has aimed at developing
insights concerning the equilibrium pattern of competitive location and pric-
ing. Nevertheless, \although these models (linear models) are rich in their
1
theoretical insights about spatial competition and have greatly enhanced our
understanding of locational interdependence, they provide very little guid-
ance for developing practical approaches to facility location in competitive
environments." (Ghosh and Craig (1984)).
Parallel to the development of this body of literature, a new eld on lo-
cation modeling was growing in the late sixties and seventies at a fast rate,
namely facility location analysis. This eld of research, coming basically from
the elds of operations research, regional science and geography, dealt with
the problem of locating new facilities in a spatial market in order to opti-
mize one or several geographical and/or economic criteria. These criteria
included overall distance minimization and transport and manufacturing cost
minimization. The literature in facility location analysis is extensive: good
sources of references can be found in Domschke and Drexl (1985), who iden-
tied over 1500 references on the subject, Love et al. (1988), and Chhajed
et al. (1993). Although most of these models used more realistic spatial rep-
resentations than the line, such as networks and planes, most of them dealt
exclusively with non-competitive situations, and little attention was paid to
the characterization of market equilibria.
From the late seventies, considerations on the interaction between compet-
ing facilities in discrete space have been developed following several dierent
approaches. An extensive bibliographic survey with over 100 citations on
competitive location can be found in Eiselt et al. (1993).
2
One of the rst of the questions that is addressed by several authors is
whether or not a set of locations in the vertices of a network exist that will
ensure a Nash equilibrium, that is, a position where neither rms have incen-
tives to move. Wendell and McKelvey (1981) considered the location of two
competitive rms with one server each and tried to nd a situation where a
rm would capture at least 50% of the market regardless of the location of
its competitor. Results showed that there was not a general strategy for the
rm that would ensure this capture if locations were restricted to vertices of
the network. They did not develop a generic algorithm for nding solutions,
but they looked at the possible locational strategies. They also examined the
problem in a tree. Hakimi (1986) also analyzed extensively the problem of
competitive location on vertices and proved that, under certain mathematical
conditions such as concave transportation costs functions, that there exists a
set of optimal locations on the vertices of the network.
A similar problem was studied by Lederer and Thisse (1990). Their prob-
lem not only looked at the specication of a site but also at the setting of
a delivered price. They formulated the problem as a two-stage game, where
in the rst stage both rms choose locations and in the second stage they
simultaneously set delivery prices schedules, and the result is that there is
sub-game perfect Nash equilibrium. As Hakimi did, they also proved that if
rm's transport costs are strictly concave, then the set of locational choices
of the rm is reduced to the vertices of the network. As a consequence, the
3
location problem can be reduced to a 2-median problem if social costs are
minimized.
A similar result was obtained by Labbe and Hakimi (1991). They devel-
oped a two-stage game in which two rms with one server each rst select
their location and then the quantities they will oer to each market. They
proved that a sub-game perfect Nash equilibrium exists and that the locations
occur on the vertices if transport costs are concave.
The problem of two rms competing in a spatial market has also been
studied in the case where the market is represented by a tree. Eiselt (1992)
proved that in such a case there is not a sub-game perfect Nash equilibrium
if both prices and locations are to be determined. Eiselt and Laporte (1993)
extended the problem to the location of 3 facilities in a tree. They found that
the existence of equilibria depended on the distribution of weights. In both
models, rms were allowed to locate on the edges of the network.
The game-theoretical models presented so far restrict themselves to the
location of rms with one facility each that compete against each other. Tobin
and Friesz (1986) examined the case of a prot-maximizing rm that entered
a market with several plants. They considered price and production eects on
the market, since the increase in the overall production level from the opening
of new plants in a spatial market stimulates reactions in the competitors.
These reactions might aect not only production levels, but also prices and
locations.
4
Tobin and Friesz developed two models: (1) a spatial price equilibrium
model which determines equilibria in prices and production levels for a given
number of rms, and (2) a Cournot-Nash oligopolistic model in which a few
prot maximizing rms compete in spatially separated markets. They used
both models to analyze the case of an entering rm that is going to open
several new plants in spatially separated markets, and knows that its policy
will have impact on market prices. Since prots depend on location and price-
levels and these depend on the reaction of the competitors, it is not possible
to use a standard plant location model. To tackle the problem, they used
sensitivity analysis on variational inequalities to relate changes in production
to changes in price to obtain optimal locations. The model was solved using
a heuristic procedure where in the rst step a spatial competitive equilibrium
model was obtained and, in the second step, a sensitivity analysis of prot
to production changes was done using an integer non-linear program to select
locations and production levels likely to maximize total prots. This model
was generalized by Friesz et al. (1989) to allow the entering rm to determine
not only production levels and the sites of its plants, but also its shipping
patterns, and to examine dierent market strategies that can occur in the
market (Miller et al. (1991)). Due to the mathematical complexity of these
models, Miller et al. (1992) developed several heuristic methods to tackle
the problem using the approach of variational inequalities (see, among others,
Harker (1984) and Nagurney (1993)).
5
Price-location modeling has been studied in a non-competitive model by
Hanjoul et al. (1990). They develop three uncapacitated plant location mod-
els where dierent alternative spatial price policies are considered (uniform
mill and delivered pricing, spatial discriminatory pricing). The models were
solved using a heuristic procedure that combined price and location settings.
Another body of literature on competitive location deals with the siting of
retail convenience stores. This type of store is characterized by (1) a limited
and very similar product oering across outlets, (2) similar store image across
rms, and (3) similar prices. Therefore, location is a major determinant of
success.
Ghosh and Craig (1984) considered the location of several retail facilities
by two servers. The problem is to locate retail facilities in a competitive
market knowing that a competing rm will also enter this market. They used
a minimax approach, where the entering rm maximizes its prot given the
best location of the competitor. Potential locations were restricted to the
vertices of the network. The rm's objective is to maximize the net present
value of its investment over a long-term planning horizon. The model did not
allow location at the same site for both rms and did not examine the issue
of ties. Ghosh and Craig used a heuristic algorithm to obtain solutions. The
algorithm is as follows: for each possible set of locations of rm A, the best
siting strategy is found for rm B. The nal result is the set of locations where
Firm A's objective is maximum given the best reactive location strategy of its
6
competitor. A Teitz and Bart hill-climbing heuristic was used to determine
the sites for both rms. The model is adapted to examine other strategies
such as preemption, i.e., the identication of locations that are robust against
competitive action. Other modications included the relaxation of the number
of stores that could be opened by each rm, and collusion by both servers.
In a similar model, Dobson and Karmarkar (1987) introduced the notion
of stability in the location of retail outlets by two prot maximizing rms in a
competitive market. Several integer programming models were developed to
identify stable locations such that no competitors can enter the market and
have prots given some rules on the competitive strategies. The models were
solved using enumeration algorithms.
Most competitive location models assume that consumers patronize the
closest shop. Karkazis (1989) considered two criteria that customers may use
to decide which shop to patronize: a level criterion based on the preferences
of a customer on the size of the facility and a distance criterion based on
closeness to the store. He developed a model that would determine the lo-
cation and number of servers to enter the market when there are other rms
already operating in the market by maximizing the prot subject to a budget
constraint. The problem was solved in a dynamic fashion since there is a
trade-o between both criteria.
Another model that examines competition among retail stores in a spatial
market was developed by ReVelle (1986). The Maximum Capture Problem
7
(MAXCAP) has formed the foundation of a series of models. These models
include issues such as the strategies that competing rms may adopt or the
uncertainty that characterizes some situations. The MAXCAP model, based
on the classical Maximal Location Covering Problem of Church and ReVelle
(1974), consists of the location of servers by an entering rm so as to max-
imize its market share capture in a market in which competitor servers are
already in position. Its integer linear formulation together with the maxi-
mum client capture objective has been the starting point for several location
problems. Eiselt and Laporte (1989) modied the MAXCAP formulation to
include attraction parameters based on gravity models and Voronoi diagrams.
ReVelle and Serra (1991) extended the formulation to allow relocation of ex-
isting servers as well as the location of new servers. The MAXCAP model
has also been adapted to consider facilities that are hierarchical in nature and
where there is competition at each level of the hierarchy (Serra et al. (1992)).
Another extension of the MAXCAP problem deals with the issue of a loca-
tion and allocation game for two competitor rms, A and B, that each seek to
locate p facilities in a network: Firm A wants to locate its p facilities so that
B, which enters also with p facilities after Firm A has located its facilities,
will capture the minimum market value possible. That is, Firm A wishes to
pre-empt Firm B in its bid to capture market share to the maximum extent
possible (Serra and ReVelle (1994)). This preemptive model also has been
adapted to the situation where Firm A does not even know how many new
8
servers Firm B will locate (Serra and ReVelle (1995)). Another modication
of the MAXCAP problem considered scenarios with dierent demands and/or
competitor locations (Serra and ReVelle (1996)).
In this paper a new competitive model addresses the issue of location of
several retail outlets by a rm and the xing of a price in order to maximize
prots, given the presence of a competitor rm. First, in section 2 the formu-
lation model will be presented. In section 3 a heuristic method to solve it will
be proposed. Computational experience and an example will be developed.
Finally, some remarks and conclusions will be oered.
2 The MaximumCapture Problem with Prices
The original Maximum Capture Problem (MAXCAP) sought the location of
a xed number of outlets belonging to a rm in a spatial market with outlets
from other rms already competing for clients. Competition was exclusively
based on distance: a market was \captured" by a given server if there was
no other server closer to it. If two servers from competing rms had a local
market at the same distance, then they divided in equal part the capture of
that market, as in a Hotelling's game. The objective of the entering rm was
to maximize its market capture. This objective, given the assumptions on
the characteristics of the retail stores, was almost equivalent to maximizing
prots (Hansen et al. (1987)). A very similar problem was stated by Hakimi
(1986). The main dierence in the assumptions is that Hakimi did not allow
9
half capture. In case of equal distances to the outlets from a node, the demand
was fully allocated to the existing rm. In this paper we will use Hakimi's
assumptions.
Now consider a spatial market where there is an existing rm (from now on,
Firm B) operating with q outlets. A new rm (Firm A) wishes to enter with
p servers and compete with rm B on the basis of price and locations. Both
rms are prot maximizing. The product sold in this industry is homogeneous,
in the sense that it is dicult to dierentiate it among stores belonging to
dierent rms. The space is discrete and is dened by a connected graph.
On each vertex of the graph there is a local market with a given number of
consumers that generates a demand for the product. Each consumer buys
only one unit of the good in the \cheapest" outlet, where cheapest is dened
momentarily.
Let i and I be the subindex and the set of local markets that are located
on the vertices of the graph. Outlets are allowed to locate only on the vertices
of the graph. Dene j and J as the subindex and set of potential locations
for Firm A's outlets, and J
B
the set of actual locations of the outlets of
Firm B. Both rms follow a uniform mill pricing policy, so customers bear
transportation costs. Therefore, the consumer's decision on patronizing a
store is based on transportation costs and price. Consumers always go the
outlet with the lowest total price, regardless of its ownership.
Let d
ij
be the network distance between local market i and an outlet in
10
j, and t the unit transport cost. Both rms charge a mill price p
A
and p
B
to its customers irrespective of their location. We assume that prices do not
change across outlets. Therefore, the price 
i
faced by consumers in each local
market i can be written as 
i
= p + td
ib
i
, where b
i
is the closest outlet to i.
The demand of local market i is a function of the market's characteristics and
the price it faces and is denoted as D
i
(
i
). Let D
i
(p + td
ib
i
) be the demand
for the local market i, shopping at its closest outlet. Therefore, the demand
function for each local market i for Firm A is dened as follows: if b
A
i
is the
closest Firm A's server to i and b
B
i
the closest Firm B's server, then:
D
A
i


A
; 
B

=
8
<
:
D
i
(
A
) if p
A
+ td
ib
A
i
< p
B
+ td
ib
B
i
0 if p
A
+ td
ib
A
i
 p
B
+ td
ib
B
i
(1)
that is, Firm A will capture the demand of local market i if the total price 
A
i
(mill price plus transport costs to the closest A outlet) faced by consumers is
lower than the total price 
B
i
re
ecting the price set by the competitor rm
and transport cost.
Assume that production entails for each outlet a xed set-up cost that
varies with location, f
j
, and a constant marginal cost, , so that for each
outlet costs are given by f
j
+ q, where q is the amount of production at the
site. If J
A
is the set of actual outlet locations (J
A
 J), then prots for rm
A can be written as follows:

A
= (p
A
 )
X
i2I
D
A
i
(
A
; 
B
)
X
j2J
A
f
j
(2)
11
The problem for rm A consists of determining the sites out of locations
set J
A
and the price p
A
that maximizes prots. These prots also depend
on other model parameters such as the location and prices of the competitor
rm and the demand function of consumers among others.
If the demand function of the local markets is totally inelastic with respect
to prices, it can be written as D
i
= a
i
, where a
i
is the total quantity that
market i will purchase, then the PMAXCAP problem can be stated as follows:
Max = (p
A
 )(
X
i2I
a
i
y
i
)
X
j2J
f
j
x
j
(3)
subject to:
y
A
i

X
j2N
i
(
b
B
i
)
x
A
j
8i 2 I (4)
n
X
j=1
x
A
j
= n
A
(5)
y
A
i
; x
A
j
= (0; 1) 8i 2 I;8j 2 J
where additional notation is:
N
i
(b
B
i
) = f8j 2 J; p
A
+ td
ij
< p
B
+ td
ib
B
i
g
n
A
= number of Firm A outlet servers.
and variables are dened as follows:
y
A
i
=
8
<
:
1, if Firm A captures demand node i
0, otherwise
x
A
j
=
8
<
:
1, if rm A locates a server at node j
0, otherwise
12
where PMAXCAP is the problem which maximizes prot capture as opposed
to population captured.
The rst set of constraints (4) depends on the set N
i
(b
B
i
), which is known
a priori. Each one of the demand nodes i has an associated set N
i
(b
B
i
) which
contains all the potential nodes at which Firm A can locate a server and
capture the demand of local market i. Therefore, if one of the variables x
A
j
belonging to the corresponding constraint is equal to 1 (i.e., a facility is located
within the capture area of node i), then capture variable y
A
i
is allowed to be
1, which indicates that node i has been captured by Firm A. Finally, the
second constraint sets the number of servers that Firm A is going to locate.
The objective denes the total prots that Firm A can achieve with the
siting of its n
A
servers. For each local market, there is demand a
i
to be
captured. If y
A
i
= 1, then (p
A
 v)a
i
is added to the revenues. Fixed costs
are multiplied by x
j
, so if an outlet opens in j, its associated xed cost is
substracted from the objective.
Observe that the last constraint (that limits the number of outlets to be
located by Firm A) can be eliminated if xed or opening costs are considered
(f
j
> 0). If prots are maximized, two forces act in opposite directions:
increasing revenues by opening more outlets closer to the demand, but that
in turn increases costs.
The basic dierence between the MAXCAP problem and the PMAXCAP
problem formulation presented relies (a) on the sets N
i
in restriction (1) re-
13
spectively, (b) in the objective function, and (c) in the lack of any consid-
eration of potential ties in capture (i.e., equal delivered prices). Eliminating
a consideration of ties is reasonable because the likehood of ties in price +
transport cots is very small.
The N
i
set contains all candidate nodes where consumers in local market
i would purchase from rm A, since the nal price 
A
faced by them is lower
than the nal price of the closest competitor outlet b
B
i
. While in the MAXCAP
problem these sets were known a priori, in the PMAXCAP model this is not
so since p
A
is not known, and therefore constraints (1) cannot be written
extensively. On the other hand, the objective function is nonlinear, since
variables p and y
i
are unkown.
If the demand function is not completely inelastic, then the PMAXCAP
problem has to reformulated using a P-median-like approach (PMAXMED):
max =

p
A
 v

X
i2I
X
j2J
D
A
i


A
; 
B

x
ij

X
j2J
f
j
z
j
(6)
subject to:
X
j2J
x
ij
= 1 8i 2 I (7)
x
ij
 z
j
8i 2 I;8j 2 J (8)
X
j2J
z
j
= n
A
(9)
x
ij
; z
j
= (0; 1) 8i 2 I;8j 2 J
14
where x
ij
is 1 if demand area i is assigned to an outlet belonging to Firm A
and z
j
indicates that there is a facility at node j when its value is equal to 1;
otherwise, its value is set to 0. Constraint (7) assigns each demand area i to
only one outlet. For the assignment to be possible, j needs to have an outlet.
Constraint (8) controls this feature: i cannot assign to j unless there is an
outlet at j. The last constraint (9) limits the number of servers that rm A
will locate.
Again, this formulation of the PMAXCAP problem cannot be solved us-
ing standard linear programming relaxation and branch and bound when
needed since (1) the objective is non linear, and (2) local demand functions
D
A
i
(
A
; 
B
) depend on the price p
A
, which is unknown a priori.
In the following section a solution method for both formulations is pro-
posed.
3 A Bi-Level Heuristic Procedure to solve the
PMAXCAP Problem
Both problems can be solved using a two stage procedure where rst locations
are found using the original MAXCAP problem and then optimal prices are
computed. Nevertheless, as Hanjoul et al. (1990) note, this is not acceptable
since outlets locations \must be chosen conditionally upon clients' demand
which, in turn, depends on prices. Conversely, it is readily apparent that the
rm's optimal price relies heavily on its location choices. Hence, separating
15
location and price decisions leads to sub-optimality."
The bilevel heuristic proposed in this paper combines a one opt procedure
to obtain locations with a search method to nd prices. Basically, in each
possible exchange of the location of an outlet the price that gives maximum
prots for Firm A is computed.
The Price Search Heuristic
This heuristic searches the price that maximizes prots for a rm that has
several xed outlets given the locations and price of the competitor rm.
Observe that, given the price and locations of the competitor rm, and given
the locations of the entering rm's servers, prots as a function of its price
may present local optima. Suppose that p
B
is the price set by the competitor
rm and the entering rm xes a price p
A
, where prots are 
A
= 
A
(p
A
; p
B
).
If the entering rm now increases its price by a small amount , p
A
0
= p
A
+ ,
two opposite eects may act on prots. For a given node i, where p
A
+td
ib
A
i
<
p
B
+ td
ib
B
i
(i.e., i is captured by Firm A):
 if p
A
0
+td
ib
A
i
< p
B
+td
ib
B
i
,node i is still captured by the closest server b
A
i
.
Therefore, local prots at node i will increase if (p
A
 )D
i
(
A
; 
B
) <
(p
A
0
 )D
i
(
A
0
; 
B
) or, in other terms if the demand is inelastic. On
the contrary, if (p
A
 )D
i
(
A
; 
B
) > (p
A
0
 )D
i
(
A
0
; 
B
) or, if the
demand is elastic, prots obtained from node i will be reduced.
 On the other hand, if p
A
0
+ td
ib
A
i
> p
B
+ td
ib
B
i
,node i is lost to the
16
competitor with the corresponding decrease in Firm A's prots relative
to demand node i.
Therefore, two eects act on Firm A's prots as prices p
A
is increased. On
the one hand, prots may experience a reduction since (1) some nodes may be
lost to the competitor because the price 
i
paid by consumers at the closest
competitor facility becomes lower than the one paid at Firm A's; and (2) even
if the node remains captured by the entering rm after the increase in prices,
prots may be reduced since the increase in price does not compensate for the
decrease in quantity demanded. On the other hand, local prots in a given
demand node may increase since the increase in prices more than compensates
for the reduction in quantity demanded at other nodes.
As the price p
A
increases, it may happen that some local optimum may
appear. Therefore, the prot function may not be unimodal. In the computa-
tional experience this characteristic of the prot function dependent on price
will be shown.
The heuristic to determine the price that maximizes prots for Firm A
given sets J
A
(the location of A's outlets) and J
B
(the location of B's outlets),
and given B's price p
B
proceeds as follows:
First, lower and upper bounds p
l
and p
u
for the price for Firm A are found.
Then, a price p
c
within the range is chosen and prots are computed. Then
p
c
is decreased by a small value  and the new prot is computed. If it is
better that the previous one, it is stored as the best current solution. If not,
17
it is discarded. The procedure is done until the lower bound p
l
is reached
or until the prots found are lower that a percentage tolerance level  of the
best prots found so far. Now it is necessary to do the same for the range
[p
c
,p
u
]. The procedure starts again from the price found at the beginning and
in each step the current price p
c
is increased by , prots are computed and
compared to the best solution found so far. The procedure stops when p
u
is
reached or if the prots found are lower than  times the best prots found.
The upper bound is found by computing the highest price that Firm A
can set before having 0 revenues. This is computed as follows: for each local
market i, nd the consumer price to the closest Firm B outlet (p
B
+ td
ib
B
i
)
and the transportation costs to the closest Firm A outlet (td
ib
A
i
). If p
A
=
p
B
+ td
ib
B
i
 td
ib
A
i
both rms divide the local market revenues. If p
A
is larger,
all local revenues in i will be lost to the competitor. Therefore:
p
u
= max(p
B
+ td
ib
B
i
 td
ib
A
i
; i 2 I)
i.e., the level at which no one patronizes Firm A.
The lower bound is found by setting p
l
= v.
A more formal description of the heuristic follows:
Initial stage:
Given a set of locations for Firm A and Firm B and p
B
Set p
A
l
 v. set
p
u
 max(p
B
+ td
ib
B
i
 td
ib
A
i
; i 2 I) Choose an initial price p
A
0
within the
18
interval [p
l
; p
u
] and compute initial prots 
0
for Firm A.
Iterative stage:
Phase 1: Set t 1. Set p
A
t
 p
A
t1
+  and compute 
t
. If 
t
> 
t1
then
set
^
 
t
and p^ p
A
t
as the current best solution. Set t t+1 repeatedly
until rst stopping rule applies. Then start Phase 2.
Phase 2: Reset t  1. Set p
A
t
 p
A
t1
  and compute 
t
. If 
t
> 
t1
then set
^
 
t
and p^  p
A
t
as the current best solution. Set t t+1 until
second stopping rule applies.
First stopping rule: 
t
< 
^
 or p
A
t
= p
A
l
.
Second stopping rule: 
t
< 
^
 or p
A
t
= p
A
u
.
So far, we have shown how to nd the best value of p
A
given the pre-
specied locations of A and B, and B's prices. Now we are ready to start the
procedure to nd optimal prices and locations.
The Location Heuristic
The PMAXCAP heuristic procedure is iterative, and the rst iteration
has two phases. In the rst phase, Firm A locates p servers using a greedy
adding procedure, where in each iteration the vertex with the best prot level
is added to the set of locations, until n
A
is reached.
In the second phase, Firm A will try to nd a better solution by relocating
one or more of the n
A
outlets using a vertex-substitution procedure. At each
iteration, FirmAwill relocate one of its servers and then use the price heuristic
19
to obtain the optimal price and prots. If the relocation has provided a set
of positions and prices that is better than before the one-opt trade, i.e., Firm
A's prots are higher, it will keep the new set of locations as the best so far.
Otherwise, Firm A will ignore the relocation and will restore the previous
solution. The one-opt trade will be done for all nodes and Firm A servers and
repeated until no cycle results in an improvement.
Since the second phase only considers vertices that improve the objective,
the heuristic may end in a local optimum.
In order to avoid being trapped in a local optimum, a tabu search proce-
dure is developed, similar to the one presented by Benati and Laporte (1994).
In essence, this tabu search explores a part of the solution space by repeat-
edly examining all neighbors of the current solution, and moving to the best
neighbor even if this causes the objective function to deteriorate. To avoid
cycling, recently examined solutions are inserted in a constantly updated tabu
list. The heuristic proceeds as follows:
Price-Location Heuristic
Phase 1
1. Set J
A
0
 ;, p
A
0
 p
B
and i 1.
2. Set J
A
k
 J
A
k1
[ v
k
, where v
k
represents index of the vertex with the
largest increase in capture:
20
max
v
k
2V
h
(J
A
k1
[ v
k
; p
A
)(J
A
k1
; p
A
)
i
3. Set k  k + 1 and repeat step 2 until k = n
A
.
Phase 2
1. Set J
A
 J
A
n
A
,
^
 (J
A
n
A
; p
A
) and p
A
 p
A
.
2. Set t 0 and 
0
 
^

3. Set J
A
t
 J
A
t1
 v
k
+ v
l
, where v
k
2 J
A
p
and v
l
2 (J  J
A
t1
).
4. If (J
A
t
; p
A
t
) >
^
; J
A
 J
A
t
, ^  (J
A
t
; p
A
) and p
A
 p
A
t
. Repeat
step 3 until all vertices and outlets have been exchanged.
5. If
^
 > (J
A
0
; p
A
0
), set 
0
 
^
, p
A
0
 p
A
and goto step 3. If not, go to
phase 3.
Phase 3
1. Reset t 0.
2. Set 
0
 
^
 and p
A
0
 p
A
. No vertex is tabu.
3. Consider all solutions J
A;i
t
of J
A
t
given by adjacent nodes, obtained ex-
changing an outlet from v
0
i
2 J
A
t
to v
00
i
2 J  J
A
t
. Relabel all J
A;i
t
solutions in decreasing order of (J
A;i
t
; p
A;i
t
). Relabel all vertices ac-
cordingly. Set i i+ 1.
21
4. If (J
A;i
t
; p
A;i
t
) >
^
 or if v
00
i
is not tabu, set J
A
t+1
 J
A;i
t
,
^
  (J
A;i
t
),
declare v
0
i
tabu until t+ , where  is a pre-xed value, and go to step
5. Otherwise, set i i + 1. If i is larger than the number of adjacent
solutions, set i equal to the index of the vertex v
00
i
with the lowest tabu
tag t+  and lift the tabu status of v
00
i
. Repeat step 3.
5. Set t  t+ 1. If t is less than a pre-xed upper bound T , go to step 2
in phase 3. Otherwise, stop
The main dierence between this heuristic and the one developed by Be-
nati and Laporte is that their starting solution is obtained by a greedy adding
procedure. In ours, the initial solution is obtained by a vertex substitution
procedure, and therefore the initial solution will be near-optimal or even op-
timal (see, for example, Rosing and ReVelle 1997). After nishing the proce-
dure, Benati and Laporte re-start it by using a diversication step: a broader
exploration of the solution space is obtained by starting from the least visited
vertices. In our heuristic, as it will be shown in the computational experience,
this seems unnecessary.
So far it has been assumed that Firm B will not react to Firm A's entry
and to the price that A chooses. This is unlikely to occur. Suppose that Firm
A now knows that its competitor will react to its entry by changing prices so
as to maximize prots given the locations of Firm A's outlets and its price.
Now Firm A's objective is to nd the optimal location and prices that will
22
optimize A's prots given the reaction in prices by its competitor. In this
sense, it is a leader-follower game where Firm A is the leader.
This problem can be solved as follows: given a set of locations for both
rms, price reaction functions can be computed for each one of them. By
reaction function it is meant what the best price is (the price that maximizes
prots) given the price of the competitor. The reaction function of Firm A
is such that p
A
= f
A
(p
B
), where for each p
B
there is a p
A
that maximizes

A
. Similarly, there is a reaction function f
B
(p
A
) for Firm B given p
A
. Since
reactions functions are known for both rms, rm A can use Firm B's reac-
tion function to nd the price that will maximize its prots given rm B's
reaction. Firm A can use the price heuristic to determine its best policy.
In each step of the iterative stage where p
A
t
is determined, Firm A can use
the price heuristic for rm B to obtain the price that Firm B will set given
p
A
t
. Once p^
B
t
is determined, Firm A can compute prots 
A
t
. A will choose
the p^
A
t
that will maximize its prots. More formally, the heuristic is as follows:
Price Competitive heuristic
Initial stage: Given a set of locations for both Firms and p
B
, set p
A
l
 v.
set p
A
u
 max(p
B
+ td
ib
B
i
 td
ib
A
i
; i 2 I). Choose an initial price p
A
0
within
the interval [p
A
l
; p
A
u
]. Compute the best price p^
B
0
for Firm B using the price
heuristic given p
A
t
. Obtain 
A
t
(p
A
0
; p^
B
0
)
23
Iterative stage:
Phase 1: Set t  1. Set p
A
t
 p
A
t1
+ . Compute the best price p^
B
t
for Firm B using the price heuristic given p
A
t
, and then 
A
t
(p
A
t
; p^
B
t
). If

A
t
(p
A
t
; p^
B
t
) > 
A
t
(p
A
t1
; p^
B
t1
) then set
^

A
 
A
t
and p^
A
 p
A
t
as the cur-
rent best solution. Set t t+ 1 until rst stopping rule applies. Then start
Phase 2.
Phase2: Reset t 1. Set p
A
t
 p
A
t1
. Compute the best price p^
B
t
for Firm
B using the price heuristic given p
A
t
, and then 
A
t
(p
A
t
; p^
B
t
). If 
A
t
(p
A
t
; p^
B
t
) >

A
t
(p
A
t1
; p^
B
t1
) then set
^

A
 
A
t
and p^A p
A
t
as the current best solution.
Set t t+ 1 until second stopping rule applies.
First stopping rule: 
A
t
< 
^

A
or p
A
t
= p
A
u
.
Second stopping rule: 
A
t
< 
^

A
or p
A
t
= p
A
l
.
Now the price heuristic used within the one-opt procedure can be replaced
by the price-competitive heuristic in steps 2 and 4. Firm A will evaluate each
one-opt trade based on the best prots it can get given the price reaction of
B. Firm A will choose the set of locations and the price that will maximize
its prots given Firm B's price reaction.
By using the Competitive Price Location Heuristic (CPLH) Firm A can
achieve a situation that will maximize its prots given the reaction of its
competitor. Since for each p
A
the optimal Firm B's price p
B
is computed, at
24
the end of the procedure prices p
A
; p^
B
and prots 
A
;
^

B
are known. Observe
that 
B
is the best prot that rm B can achieve given its locations and the
price and locations of Firm A.
4 Computational Experience
Computer programs have been written in FORTRAN 77 in order to solve the
competitive price location problem described above. The program was run on
4 test problems generated in the following way. 15, 30, 50 and 70 points were
randomly chosen in a 100 by 100 square for each test problem. Each point is
at the same time the location of a local market and the potential site for an
outlet. Transportation costs between points are equal to Euclidean distances.
All weights associated to each vertex have been set equal to 100. A linear
demand function has been selected, and the slope  has been chosen between
0.5 and 3.0, depending on the number of vertices. The xed and variable
production costs were set to 0. The tolerance level  has been chosen equal
to 0.8 and the price parameter  was set to 0.5.
For all generated networks, the locations of Firm B were obtained by
using the price heuristic together with a vertex substitution (Teitz and Bart)
heuristic, as if there were no competitors in the market. Each one-opt trade
was valued using the price heuristic. In this sense the locations and price found
for rm B correspond to the optimal or near-optimal monopolistic solution:
Firm B maximizes prots by xing prices and locations without competition.
25
Therefore, in each scenario Firm B starts with a good positioning of its servers.
Once the initial locations for Firm B were obtained, the price-location
heuristic was used to obtain the nal solutions for Firm A, using the price-
competitive heuristic to compute the objective value. That is, in all runs Firm
A considered that Firm B would react in prices.
First, in order to test the eciency of the heuristic algorithm, 100 15-node
networks were generated for  = 0.5, 1 and 1.5 respectively. For each network,
optimal solutions were obtained by enumerating all locations for the entering
rm and, for each set of locations, computing the competitive-price heuristic
to obtain optimal prices. Results are presented in Table 1. Computing times
are presented in Table 2.
The price-location heuristic achieved in most cases the optimal solution.
The vertex substitution procedure (phase II) obtained at least in 75% of the
runs the optimal solution. When phase II did not obtain the optimum, phase
III achieved in at least 50% of the runs the optimal solution. In general,
the price-location heuristic performed better in terms of optimal solutions
found as the slope of the demand function increased. This is also the case for
computing times.
5 An Example
In this section the PMAXCAP model is applied to a 55-node network (Swain
1974, see Table 4 and Figure 1). Four dierent scenarios are examined with
26
regard to the number of outlets to be located and the slope of the demand
function. Firm B is operating as a monopoly in the market with several
outlets. The demand function in each local market is linear and the same,
except for the intercept, that is equal to the weight of the vertices. These
intercepts are shown in table 2 of the appendix.
The locations and the price for Firm B have been obtained using the
method described in the last section for the monopoly situation. That is , as a
monopolist, Firm B has a good positioning in the market. Unit transportation
costs are linear with distance and equal to 1. Fixed and variable costs are set
to 0.
Firm A knows that Firm B will react in prices, so it will use the price-
competitive heuristic in phase II and III to obtain what price it has to set to
maximize prots given Firm B's reaction. Results are presented in Table III.
In the rst column the number of outlets for Firm A and Firm B and the
slope of the demand function are presented. In the second column the initial
scenario Firm B as a prot maximizer monopolist is presented. Then, results
found in the dierent phases of the algorithm are shown. In none of the four
runs phase III of the algorithm improved the solution found in phase II.
As mentioned before, given p
B
, J
A
and J
B
, prots as a function of prices,
given the price of the competitor may present some local optima. These can
be seen in Figure 2, where the prot function corresponds to Firm B's nal
solution where n
A
= 3, n
B
= 3 and  = 0:3, and where p
A
= 65:0.
27
6 Conclusions
In this study, market entry by a rm with several outlets has been studied
within a competitive locational framework. In a system where two rms that
oer the same good or service seek to enter a market, the location of their
servers together with the setting of prices play a dominant role in the nal
prots that can be achieved.
A duopoly model that seeks to locate servers and set mill prices to maxi-
mize the market capture by a rm has been presented. The model, based on
the MAXCAP problem, is quite ecient in obtaining solutions, even though
no exact algorithm has been found to obtain optimal locations and prices.
A feature of the heuristics presented is that there is no need to make
assumptions on the demand functions, production and transportation cost
functions. The CPLH method can be used with any non-linear specication
of these functions, and regardless of convexity or concavity properties.
The models proposed specify the number of servers p that rm A is going
to locate. This assumption can be relaxed by applying the heuristic for p =
1; 2; : : : ; n and choosing p as the one that gives higher prots.
As seen in the computational experience, the price heuristic can be used
to nd the locations and price of a rm that enters with several outlets in a
spatial market without competition. This is an alternative method to the one
proposed by Hanjoul et al. (1990) if p is not specied.
28
The CPLH heuristic can be applied to dierent competitive situations.
For example, suppose that Firm B is operating in the market and knows that
Firm A will enter to compete. Firm B might want to nd what its best price
is given the Firm A's entry. Therefore, Firm B can use the CPLH and the
PLH heuristics as follows: In the iterative stage of the PLH heuristic, Firm
B would use the CPLH heuristic to nd, given its price, where Firm B will
locate and what price it will set. Firm B will choose the price that maximizes
its prot given the locations and price of Firm A. In this sense, Firm B will
nd a price that will try to pre-empt Firm A in its bid to capture market
share to the maximum extent possible.
The problem that remains to be solved relies on the competitive behavior
of both rms. Recall that, once the optimal solution is found, while Firm B
has no incentive to change its price since it is the best one given the entrance
of Firm A in the market, this one can improve its prot levels by using the
price heuristic. This situation leads to a sequential price war, where in each
stage rms alternatively nd the price that maximizes prots given the price
xation of the competitor in the previous stage.
It may be the case that by entering a price war, both rms will never nd
a better prot level than the one achieved at the end of the price-location
heuristic. If both rms know this fact (by applying the price-competitive
heuristic), they may cooperate by not entering a price war. In this sense, it
can be dened as a sort of cooperative equilibrium.
29
On the other hand, since reaction functions are known for a given set
of locations for both rms, non-cooperative equilibria may also be identied
applying the standard approach used in Industrial Organization Theory. This
can been seen in Figure 3. In this graphic the reaction functions in prices for
both rms are depicted, corresponding to the nal solution obtained in the
last section with n
A
= 3, n
B
= 3 and  = 0:3. The intersections of both
functions may imply non-cooperative equilibria, even though these may not
be stable and some cycling could occur. Further research can be developed to
try to examine cooperative and non-cooperative equilibria in networks using
the modelling approach presented here.
Finally, in this paper, a uniform mill pricing policy has been considered.
The model can be adapted to other forms of pricing, such as uniform delivered
pricing and spatial discriminatory pricing.
30
7 Acknowledgements
This research was partially done under DCIGYT grants PB95-0980 and PB95-
0978, Ministry of Education, Spain. The authors gratefully acknowledge the
comments of Andreu Mas-Colell and Walter Garcia-Fontes on early versions,
as well as the suggestions received from the participants in the Applied Eco-
nomics Workshop at UPF. All remaining errors are of our own responsibility.
31
References
Benati, S. and G. Laporte, 1994, \Tabu search algorithms for the (rjx
p
)
medianoid and (rjp) centroid problems," Location Science, 2(4):193{204.
Chhajed, D., R.L. Francis, and T.J. Lowe, 1993, \Contributions of
operations research to location analysis," Location Science, 1(4):263{287.
Church, R. and C. ReVelle, 1974, \The maximal covering location prob-
lem," Papers of the Regional Science Association, 32:101{118.
Dobson, G. and U.S. Karmarkar, 1987, \Competitive location on a
network," Operations Research, 35(4):565{574.
Domschke, W. and A. Drexl, 1985, \Location and layout planning: An
international bibliography, " in Lecture Notes in Economics and Mathe-
matical Systems, volume 238. (Springer, Berlin).
Eiselt, H., 1992, \Hotelling's duopoly on a tree," Annals of Operations
Research, 40:195{207.
Eiselt, H. and G. Laporte, 1989, \Competitive spatial models," European
Journal of Operational Research, 39:231{242.
1993, \The existence of equilibria in the 3-facility hotelling model in
a tree," Transportation Science, 27(1):39{43.
32
Eiselt, H., G. Laporte, and J.F. Thisse, 1993, \Competitive loca-
tion models: A framework and bibliography," Transportation Science,
27(1):44{54.
Friesz, T., L. Tobin, and T. Miller, 1989, \Existence theory for spa-
tially competitive network facility location models,"Annals of Operations
Research, 18:267{276.
Gabszewicz, J. and J.F. Thisse, 1991, \Location, " in Auman, R. and
S. Hart, editors, Handbook of Game Theory with Economic Applications.
(North-Holland).
Ghosh, A. and C.S. Craig, 1984, \A location allocation model for facility
planning in a competitive environment,"Geographical Analysis, 16(1):39{
51.
Graitson, D., 1987, \Spatial competition a la hotelling: A selective survey,"
Journal of Industrial Economics, 31:13{25.
Hakimi, S., 1986, \p-median theorems for competitive location," Annals of
Operations Research, 5:79{88.
Hanjoul, P., P. Hansen, D. Peeters, and JF. Thisse, 1990, \Unca-
pacitated plant location under alternative spatial policies," Management
Science, 36(1):41{57.
33
Hansen, P., M. Labbe, D. Peeters, , and J.F Thisse, 1987, \Facility
location analysis, " in Arnott, R., editor, Systems of Cities and Facility
Location, pages 1{70, (Harwood Academic Publishers).
Harker, P., 1984, \A variational inequality approach for the determination
of oligopolistic market equilibrium,"Mathematical Programming, 30:105{
111.
Hoover, E., 1936, \Spatial price discrimination," Review of Economic Stud-
ies, 4:182{191.
Karkazis, J., 1989, \Facilities location in a competitive environment: A
promethee based multiple criteria analysis," European Journal of Opera-
tional Research, 42:294{304.
Labbe, M. and S.L. Hakimi, 1991, \Market and location equilibrium for
two competitors," Operations Research, 39(5):749{756.
Lederer, P. and J.F. Thisse, 1990, \Competitive location on networks
under delivere pricing," Operations Research Letters, 9:147{153.
Lerner, A. and H.W. Singer, 1937, \Some notes on duopoly and spatial
competition," Journal of Political Economy 39, pages 145{186.
Love, R., J.G. Morris, and G.O. Wesolovsky, 1988, Facilities Loca-
tion: Models and Methods. (North Holland, New York).
34
Miller, T., T.L. Friesz, and R.L. Tobin, 1992, \Heuristic algorithms for
delivered price spatially competitive network facility location problems,"
Annals of Operations Research, 34:177{202.
Miller, T., R.L. Tobin, and T.L. Friez, 1991, \Stackelberg games on
a network with cournot-nash oligopolistic competitors," Journal of Re-
gional Science, 31:435{454.
Nagurney, A., 1993, Network Economics: A Variational Inequality Ap-
proach. (Kluwer Academic Publishers, Boston).
Ponsard, C., 1983, A History of Spatial Economic Theory. (Springer-Verlag,
Berlin).
ReVelle, C., 1986, \The maximum capture or sphere of in
uence problem:
Hotelling revisited on a network," Journal of Regional Science, 26(2):343{
357.
ReVelle, C. and D. Serra, 1991, \The maximumcapture problem includ-
ing relocation," Information and Operations Research, 29(2):130{138.
Rosing, K. and C. ReVelle, 1997, \The heuristic concentration for p-
median problems," Forthcoming in European Journal of Operational Re-
search.
35
Serra, D., V. Marianov, and C. ReVelle, 1992, \The hierarchical
maximum capture problem," European Journal of Operational Research,
62(3).
Serra, D. and C. ReVelle, 1994, \Market capture by two competi-
tors: The preemptive capture problem," Journal of Regional Science,
34(4):549{561.
1995, \Competitive location in discrete space, " in Drezner, Z., editor,
Facility Location: A survey of methods and applications, Springer series
in Operations Research, pages 367{386. (Springer, New York).
1996, \The maximum capture problem with uncertainty," Environ-
ment and Planning B, 62:49{59.
Smithies, A., 1941, \Optimum location in spatial competition," Journal of
Political Economy, 49:423{439.
Swain, R., 1974, \A parametric decomposition algorithm for the solution of
uncapacitated location problems," Management Science, 21:189{198.
Tobin, R. and T.L. Friesz, 1986, \Spatial competition facility location
models: denition, formulation and solution approach," Annals of Oper-
ations Research, 6:49{74.
36
Wendell, R. and R.D. McKelvey, 1981, \New perspectives in competi-
tive location theory," European Journal of Operational Research, 6:174{
182.
37
752
50
53
46
40
55
43
34 45
8
44
13
11
47
5 1
9 4
2
3
30 33
16
32
38
54
22
27
14
12
17
28
23
19
29
18
26
31
15
36
35
48
25
41
49
20
1021
37
51
24
39
6
42
Figure 1: 55-node network
38
Table 1
(n
A
; n
B
)  % of optimal solutions found non-opt.
Phase I Phase II Phase III solutions
(2,2) 0.5 0 90% 7% 3%
1.0 0 95% 3% 2%
1.5 0 96% 2% 2%
(3,3) 0.5 0 75% 15% 10%
1.0 0 81% 15% 4%
1.5 0 92% 4% 4%
Table 2
(n
A
; n
B
)  Average Computer time (seconds)
Phase I Phase II Phase III
(2,2) 0.5 0.27 20.35 139.98
1.0 0.24 8.89 54.22
1.5 0.11 5.64 35.12
(3,3) 0.5 0.34 44.27 218.14
1.0 0.11 20.21 93.76
1.5 0.24 9.56 63.02
39
Table 3: Results, 55-node network
Firm B's Firm A's results
Monopoly Phase 1 Phase 2 Phase 3
 = 0:3 
A
41,113 53,460 53,460
(3,3) 
B
107,414 40,720 55,661 55,661
p
A
40.0 65.0 65.0
p
B
119.5 60.0 86.5 86.5
J
A
2,9,16 5,17,41 5,17,41
J
B
4,22,31 4,22,31 4,22,31 4,22,31
 = 1:0 
A
8,673 9,974 9,974
(3,3) 
B
17,948 12,324 11,633 11,633
p
A
29,5 30.5 30.5
p
B
40.5 40,5 40,5 40,5
J
A
1,6,30 1,6,7 1,6,7
J
B
3,5,9 3,5,9 3,5,9 3,5,9
 = 0:3 
A
48,351 68,881 68,881
(5,5) 
B
122,577 35,606 58,583 58,583
p
A
35.0 64.5 64.5
p
B
114.8 52.5 93.0 93.0
J
A
4,13,17,18,34 4,16,17,30,41 4,16,17,30,41
J
B
5,20,22,24,31 5,20,22,24,31 5,20,22,24,31 5,20,22,24,31
 = 1:0 
A
10,734 13,760 13,760
(5,5) 
B
22,282 13,740 14,260 14,260
p
A
21.0 43.0 43.0
p
B
43.0 43.0 43.0 43.0
J
A
4,13,15,21,30 1,2,3,6,11 1,2,3,6,11
J
B
5,7,8,9,10 5,7,8,9,10 5,7,8,9,10 5,7,8,9,10
40
Table 4: 55-node Network demand intercepts and coordinates
node coord node coord node coord
x y x y x y
1 32 31 20 25 14 39 46 51
2 29 32 21 29 12 40 50 40
3 27 36 22 24 48 41 23 22
4 29 29 23 17 42 42 27 30
5 32 29 24 6 26 43 38 39
6 26 25 25 19 21 44 36 32
7 24 33 26 10 32 45 32 41
8 30 35 27 34 56 46 42 36
9 29 27 28 12 47 47 36 26
10 29 21 29 19 38 48 15 19
11 33 28 30 27 41 49 19 14
12 17 53 31 21 35 50 45 19
13 34 30 32 32 45 51 27 5
14 25 60 33 27 45 52 52 24
15 21 28 34 32 38 53 40 22
16 30 51 35 8 22 54 40 52
17 19 47 36 15 25 55 42 42
18 17 33 37 35 16
19 22 40 38 36 47
41