Page 13 - 33-3

NTU Management Review Vol. 33 No. 3 Dec. 2023

capacitated facility location problem considering customer. We further extend the model to
incorporate multiple activity sessions and allow preferences to be time-dependent.
Given that the problem is NP-hard, in many cases a heuristic algorithm is more
realistic. In Kang et al. (2023), a heuristic greedy algorithm is designed based on the

maximum flow model. However, there are two drawbacks of this algorithm. First, the time
dependency of preference is ignored. Second, the algorithm is computationally inefficient
due to the fact that the benefits of two neighboring solutions are evaluated by solving two

independent problems. In this study, we extend the algorithm to take time dependency into
consideration and speed it up by utilizing some properties among neighboring solutions.
Choosing locations to build facilities is difficult in practice, especially when
customers’ preference is time-dependent. To take time-dependent preference into
consideration, for each construction plan, one needs to be able to calculate (or at least

estimate) the number of customers that may be served in each activity sessions. However,
even considering capacity limitation and customer together is already difficult enough
(given the fact that there is almost no academic literature studying these two issues at

the same time; see Section 2 for more details), not to mention time dependency. Two
simplified strategies that practitioners typically adopt are: (1) to consider only the activity
session that has the most demand (if demand varies a lot among sessions); (2) to consider
the average demand per session (if demand variation is not large). However, these
strategies make the evaluation of a construction plan imprecise in general. On the contrary,

the maximum flow-based algorithm proposed in this study allows one to precisely
calculate the number of customers that may be served in each activity session for any
construction plan. Our proposed algorithm therefore possesses a unique value.

The remainder of this study is organized as follows. In the next section, we review
some related works. In Section 3, a bi-level model is presented first. Then a single-level
reformulation is proposed by using auxiliary variables and constraints. In Section 4, we
propose a greedy-based heuristic algorithm for solving the problem. A numerical study
is conducted to demonstrate and compare the performance of the two proposed solution

approaches in Section 5. Finally, we make conclusions in Section 6.

5