|
In
the classical facility location models there is one decision maker
only. As a rule, this person is a top manager which selects sites for
facilities to service the clients. The set of possible sites I
= {1,…, n} and the set of
clients J = {1,…, m} are given. The decision maker can open p > 0 facilities and knows the production–transportation costs cij
³
0 for each pair (i, j),
iÎI, jÎJ. The
problem is to find a subset S
Ì
I, | S
| = p of opening facilities in order to minimize the total cost for
servicing all clients, i.e.
Note
that for given set S, each client is
serviced from the cheapest facility. It is regular for a centralized economy.
But in the market economy, each client can select a facility according to own
preferences. For this case, the mathematical model can be represented as a two
persons game. The first decision maker is the top manager of the firm. He (she)
is a Leader and makers decision at first. The second decision maker (Follower)
is a person which represents the clients. He (she) knows the set S of opening facilities and selects a provider for each client.
These models are known as Stakelberger games [4].
Let (dij)
denote the client preferences for the set of facilities. If 
then client j prefers the facility i1. For simplicity we assume
that all elements dij are
different in each column jÎJ. Otherwise, we have to introduce optimistic and
pessimistic strategies and consider cooperative and noncooperative games [2,
4]. So, the goal of Leader is to
service all clients with minimal total cost, but now the Leader has to take
into account the client preferences.
Let us introduce two sets
of variables:
Leader:
Follower:
Now the mathematical
model can be presented as the bilevel programming problem [1, 3, 4]:
s.t.
xi
Î
{0,1},
iÎI,
where xij*(xi)
is the optimal solution of the
Follower problem:
s.t.
xij £
xi,
iÎI, jÎJ;
xij Î
{0,1},
iÎI, jÎJ.
As before, the objective
function of the Leader defines the total cost for servicing all clients. The
difference from the classical model consists of in new definition of the
feasible domain. Now it is described by the standard restrictions: Boolean
variables (correspond to S Ì I)
and number of opening facilities is p
(| S | = p) and extremal restriction: optimization problem of the Follower.
In this auxiliary problem the vector xi
is given [3].
The first facility
location models with client preferences were considered in [6]. There are
different reductions of this bilevel programming problem to the integer
programming problem [2, 4, 5]. It is known that the problem can be rewritten
as a minimization problem for pseudo–Boolean function or the selection rows
problem for the pair of matrices [1, 2]. Polynomially solvable cases are
founded in [2]. If cij = dij,
iÎI, jÎ J then this problem coincides
with the classical p-median problem.
References
-
Beresnev V.L.
Discrete
location
problems and polynomial s in Boolean variables.
Novosibirsk
.
Sobolev Institute Press. 2005. (in Russian)
-
Gorbachevskaya L.E. Polynomially solvable and NP-hard
bilevel standardization problems. PhD Thesis,
Sobolev Institute of Mathematics.
Novosibirsk
. 1998. (in Russian)
-
Kochetov Yu.A. The bilevel facility location problems.
Proceedings of ICM&MG.
Informatics. V. 6. 2006. (in
Russian)
-
Moulin
H. Théorie des Jeux Pour L’économie et la politique. Hermann.
Paris
. 1981.
-
Hansen
P., Kochetov Yu., Mladenovic N. Lower bounds for the uncapacitated facility
location problem with user preferences. Proceedings of Discrete Optimization
Methods in Production and Logistics (DOM'2004) 2nd International
Workshop,
Omsk
. 2004. P. 50–55.
-
Hanjoul
P., Peeters D. A facility location problem with clients' preference
orderings, Regional Science and Urban Economics. 1987. v. 17, P. 451–473.
|
Benchmarks Library