Page 14 - 33-3

Optimal Allocation of Capacitated Facilities Considering Time-Dependent User Preference for User Number
Maximization

2. Literature Review

A facility location problem is a problem where a decision maker decides where to
locate facilities and how to assign customers to those built. While many facility location

problems take facility capacity into consideration (see, e.g., Ho (2015) and Gadegaard,
Klose, and Nielsen (2018) and the references therein), none of these works include
customers’ self-selection based on their preferences.
Traditionally, to put customer into a model, researchers usually formulate the problem

as a bi-level program. In such a program, the upper-level problem is for the decision
maker to decide locations to build facilities, and the lower-level one is for customers to
choose facilities to visit. To solve these bi-level programs, reformulating them into single-
level programs is typical. Three reformulations of the uncapacitated bi-level problem

using sets to express customer are proposed by Hanjoul and Petters (1987) where two
greedy-based heuristic algorithms are also presented. Some other researchers, e.g.,
Hansen, Kochetov, and Mladenovi (2004), Cánovas, García, Labbé, and Marín (2007), and
Vasil’ev, Klimentova, and Kochetov (2009), reformulate the model using similar ideas.

More recently, Camacho-Vallejo, Cordero-Franco, and González-Ramírez (2014) present
two reformulations. Using the primal-dual relationship and complementary slackness of
the lower level, they obtain two linearized single-level facility location models.
As the reformulation methods adopted in the above works prove to be not so efficient,

researchers have invented other approaches. In particular, Berman, Drezner, Tamir, and
Wesolowsky (2009), and Espejo, Marín, and Rodríguez-Chía (2012) both propose the so-
called “closest assignment constraints” to turn the bi-level model into a single-level one;
Camacho-Vallejo, Casas-Ramírez, and Miranda-Gonzalez (2014) further apply this idea to

facility location problems with customers. Their computational result shows that the new
reformulation requires less time compared to those previous reformulation methods. Thus,
in this study, we borrow the idea from Camacho-Vallejo, Casas-Ramírez, and Miranda-
Gonzalez (2014) and add capacity and time-dependent preference constraints to formulate

our model.
There are some more recent works regarding customers in facility location problems.
Based on the models designed by Camacho-Vallejo, Cordero-Franco, and González-
Ramírez (2014) and Camacho-Vallejo, Casas-Ramírez, and Miranda-Gonzalez (2014),

6