3. Sequential Competitive Facility Location Problems

The formalization of this class of problem and the fundamental complexity results were established by Hakimi [28]. Following the game introduced by von Stackelberg [76], Hakimi [28] presented the two basic problems in sequential location analysis, the centroid and medianoid problems. These two problems are faced by the leader and the follower, respectively. The leader attempts to locate p( ≥ 1) facilities knowing that a follower will in turn locate his r( ≥ 1) facilities based on the leader’s chosen locations; this is the (r | p)-centroid problem. The follower knows the set X _p that indicates where the leader’s facilities are located, and solves an (r | X _p )-medianoid problem. Customers choose among the facilities according to a function of the distance between themselves and the facilities, preferring always the closest. This is the so-called binary customer choice. The formulation of the problems is based on the assumption that co-location is not allowed and if, by any chance the distance from a customer to the closest facility of the two competitors is the same, the customer always prefers the leader’s facility. The demand of the customer is also considered to be inelastic with respect to the distance traveled.