Page 22 - 33-3

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

facilities are parks, courts, and sporting centers for residents to exercise there, one day
should be a good candidate of a time period. The length of an activity session should then
be determined with the following consideration. First, a customer’s preference of visiting
a facility should be roughly the same within the same activity session. It is thus not a

good idea to split one day into only two activity sessions “midnight to noon” and “noon to
midnight”, because one’s preference to jog on streets around 7 AM and 11 AM should be

4. Algorith
Analysis
s and
4. Algorithms and Analysis
m
significantly different. Second, the length of an activity session should also be long enough
so that it is reasonable for one to distinguish two different activity sessions. For example,

splitting a day into 24 or even 48 activity sessions when consideing customers’ visiting to section, we propose an iterative greedy heuristic algorithm for our problem.
In this In this section, we propose an iterative greedy heuristic algorithm for our problem.
sport facilities can be a bad idea.
In short, the length of an activity session should be chosen so that the estimation of
4.1 Greedy Selection Algorithm with Maximum Flo w (GSAM F)
4.1 Greedy Selection Algorithm with Maximum Flow (GSAMF)
customers can be reasonably performed, and the number of activity sessions may then be
determined accordingly.
The Algorithm
4.1.1 4.1.1 The Algorithm
4. Algorithms and Analysis

i
g

a
g
t

c
a
o
h
se
n
e

t
y
t
m
e
h
d
e
a
a
l
r
r
h

i

We propo We propose a greedy algorithm that in each iteration, we select the facility and
l
c
e

e
e
s
acility
f
nd
a

t
he
t
w
t
a
o
i
i
n
e
t

,
r
In this section, we propose an iterative greedy heuristic algorithm for our problem.
its scale levels with t he b est performance ratio a mong those un built ones and add it i nto
its scale levels with the best performance ratio among those unbuilt ones and add it into
to
t
budget
ion
when
not
here
i
s
stops
enough
process
t
the constr the construction plan. The selection process stops when there is not enough budget to
a
l
n
T

.
p
t
c
u
i

n
o
e
e
e
s

h
l
c
4.1 Greedy Selection Algorithm with Maximum Flow (GSAMF)
4.1.1 The Algorithm
build more new facilities.
build more n ew facili ties.
We propose a greedy algorithm that in each iteration, we select the facility and its
scale levels with the best performance ratio among those unbuilt ones and add it into the
As described in Section 3, among the built facilities, the customers will choose
As described i n Section 3, among t h e b u i l t f a c i l i t i e s , t h e c u s t omers will c hoose
construction plan. The selection process stops when there is not enough budget to build
re,
f
o
n
o
en
c

where to g where to go according to their preference order. Therefore, once we are given a set of
e
g
i
w
e
e
ar
v

heir
herefo
accord
reference

T
a
er.
ing
o

p
to
t
ord

set
more new facilities.
As described in Section 3, among the built facilities, the customers will choose
, we have
, we have
built facilities with determined scale levels, represented by = � ��
built facilities with determined scale levels, represented by = � �� � �,� � �� � �,� �
where to go according to their preference order. Therefore, once we are given a set of
to find the number of customers served by this plan, i.e., to solve the objective value
to find the n u mber o f cu stome r s s erv ed by this p lan, i.e., to s olve t he objective , we have to find
value
built facilities with determined scale levels, represented by y=[y ]
jk j∈J, k∈K
the number of customers served by this plan, i.e., to solve the objective value z(y) of the
( ) of the following program
( ) of the following program
following program
( ) = max � � � , ,
( ) = max � � �
� ��� � ���
� � � �� � � � � � �� � �
s.t. (4), (9) – (16).
s.t. (4), (9) – (16).
Kang et al. (2023) proposes a way to transform the benefit evaluation problem to
Kang et al. (2023) proposes a way to transform the benefit evaluation problem to
14
a maximum flow problem. We now show how to extend this method to incorporate
a maximum flow problem. We now show how to extend this method to incorporate
time dependency, which is not considered in his work. Given a construction plan , we
time dependency, which is not considered in his work. Given a construction plan , we
construct a directed acyclic graph whose structure is similar to that in Figure 1. For each
construct a directed acyclic graph whose structure is similar to that in Figure 1. For each
customer location , we add a customer node into the graph. A source node is into the graph. A source node is
customer location , we add a customer node
� �
created and connected to customer node with capacity for all . For with capacity for all . For
created and connected to customer node � � � �
20 20