Geoscience Reference
In-Depth Information
require facilities to be located at the nodes of the tree, but allow a customer's
demand to be linearly decreasing in the distance to the closest facility. Both firms are
assumed to locate a single facility. Characterizations of the solutions, especially with
respect to the median(s) of the tree are described. Hansen and Labbé (
1988
)present
a polynomial algorithm for the (1
j
1) centroid problem on tree networks. García
et al. (
2003
) follow the analysis of Eiselt (
1992
, Annals) and determine all von
Stackelberg solutions on a tree with parametric, but possibly different, prices. They
also discuss the “first entry paradox” (see Ghosh and Buchanan
1988
), according to
which the leader in a von Stackelberg game would typically have the advantage.
ReVelle (
1986
) was the first to formulate the highly influential MAXCAP
problem on networks, i.e., the problem, in which the follower locates facilities.
By modifying the objective, he reduced the formulation to a
p
-median problem. In
follow-up papers, Serra and ReVelle (
1994
,
1995
) present the PRECAP problem that
solves the leader's (
r
j
p
) centroid problems. The authors design heuristic algorithms
for the (bilevel) problem of the leader, and report computational experience.
The main contribution in the Hakimi (
1990
) topic chapter is the introduction of
three allocation rules: binary (i.e., winner-take-all), partially binary (a customer
distributes his demand proportional to the inverse distances to the closest facilities
of the two firms), and the (fully) proportional rules, in which customers allocate
their demand inversely proportional to the distances to the facilities. The authors
also presents results with these allocation rules with respect to the node property.
Suárez-Vega et al. (
2004
) expand on Hakimi's discussion of the three allocation
rules for essential and unessential demand at the nodes of the network. The authors
also derive finite dominating sets, including those for concave capture functions.
Serra et al. (
1999
) discuss the usual MAXCAP problem, but with an additional
constraint that ensures that each facility has at least a market share of a certain size.
This is done so as to guarantee the viability of the firm. Some computational testing
with two rules is provided; on rule, which checks viability first, then locates and
reallocated demand, and the second rules that does not do the checking. It appears
that Rule 2 has some advantages.
Spoerhase and Wirth (
2008
) tackle the notoriously difficult problem of (
r
j
p
)
centroids. In order to obtain any results (as Beckmann
1972
stated: “As everyone
knows, in location theory one is forced to work with simple assumptions in order
to get any results at all”), they restrict themselves to paths and trees. Along similar
lines, Eiselt (
1998
) investigates a von Stackelberg problem on a tree, given that the
perceptions of leader and follower regarding the demands at the nodes are different.
Solutions to the bimatrix game (in which each player has full knowledge about the
perception of his opponent) and the hypergame (in which neither competitor knows
about the perception of his competitor) are characterized. In general, if a firm can
assume that its competitor has researched the demand diligently, it can gain little
by finding out about the exact perception of its competitor. Marianov et al. (
1999
)
extend the MAXCAP to the location of hubs by a follower firm, assuming that
passengers choose the airline which offers the shortest route (distance) between
their origin and destination. Marianov and Taborga (
2001
) address the problem of
locating public health centers competing with private ones for affluent customers,
