Page 28 - 33-3

In our algorithm with flow estimation, we replace in GSAMF with its
estimated value . We therefore replace by , which
�
�
is defined as
�
�
������
�
− �
.
�
=

��
The pseudocode of the greedy selection algorithm with maximum flow estimation
(GSAMFE) is presented in Algorithm 2. The only difference between Algorithms 1 and
Optimal Allocation of Capacitated Facilities Considering Time-Dependent User Preference for User Number
In our algorithm with flow estimation, we replace in GSAMF with its
Maximization
2 is using or (i.e. or ) in each iteration.
�
�
estimated value . We therefore replace by , which
�
�
In our algorithm with flow estimation, we replace z(y) in GSAMF with its estimated
While this is some kind of approximation, a huge amount of computation time may be
is defined as
value z'(y). We therefore replace Ratio(j,k|y) by Ratio'(j,k|y), which is defined as
saved.
� � ������
− � �
� .
=
We now analyze the complexity of GSAMFE. First of all, ∑ ∑ should
��� ��� ��
��
be calculated before the greedy selection starts. The time it takes is .
The pseudocode of the greedy selection algorithm with maximum flow estimation
The pseudocode of the greedy selection algorithm with maximum flow estimation
(GSAMFE) is presented in Algorithm 2. The only difference between Algorithms 1 and 2
Second, the values of should be initialized to for all customer . This takes
�
�
is using Ratio(j,k|y) or Ratio'(j,k|y) (i.e. z(y) or z'(y)) in each iteration. While this is some
(GSAMFE) is presented in Algorithm 2. The only difference between Algorithms 1 and
. The final part is the greedy selection, whose structure of GSAMFE is the same
kind of approximation, a huge amount of computation time may be saved.
2 is using or (i.e. or ) in each iteration.
�
�
We now analyze the complexity of GSAMFE. First of all, ∑ ∑
β should be
j∈J
k∈K jk
as that of GSAMF. Therefore, GSAMFE also runs for at most iterations, and in the
calculated before the greedy selection starts. The time it takes is O(|I||J||K||T|). Second,
While this is some kind of approximation, a huge amount of computation time may be
iteration, it does at most − times of flow estimation. For each time
the values of α (y) should be initialized to d for all customer i. This takes O(|I|). The final
��
saved. i i
part is the greedy selection, whose structure of GSAMFE is the same as that of GSAMF.
of flow estimation, a new facility of a certain scale level is added, which requires
th
Therefore, GSAMFE also runs for at most |J| iterations, and in the j iteration, it does at
should
∑
We now analyze the complexity of GSAMFE. First of all, ∑
GSAMFE to update the values of for all customers who are willing to visit the
���
���
most (|J|-j+1)|K| times of flow estimation. For each time of flow estimation, a new facility
��
�
be calculated before the greedy selection starts. The time it takes is .
of a certain scale level is added, which requires GSAMFE to update the values of α (y)
i
newly added facility in at least one activity session. Such updating can be done in
for all customers who are willing to visit the newly added facility in at least one activity
Second, the values of should be initialized to for all customer . This takes
. Collectively, the total time complexity is �
session. Such updating can be done in O(|I||T|). Collectively, the total time complexity is
�
. The final part is the greedy selection, whose structure of GSAMFE is the same
�
as that of GSAMF. Therefore, GSAMFE also runs for at most iterations, and in the
O � � − � = .
�
���
iteration, it does at most − times of flow estimation. For each time
��
Compared to GSAMF, which solves for the exact flow amount for each construction
Compared to GSAMF, which solves for the exact flow amount for each construction
of flow estimation, a new facility of a certain scale level is added, which requires
plan, GSAMFE indeed saves time with the idea of flow estimation.
plan, GSAMFE indeed saves time with the idea of flow estimation.
GSAMFE to update the values of for all customers who are willing to visit the
4.3 An Illustrative Example
�
In this section, we demonstrate an example of the GSAMFE algorithm to better
28
newly added facility in at least one activity session. Such updating can be done in
explain how it works. Suppose that there are three customers, three facilities, and
two activity sessions. For each facility, there are two scale levels. The budget of the
. Collectively, the total time complexity is
construction plan B=70, and the customer demands, facility capacities, and facility
�
construction costs are listed in Tables 4 and 5. In Table 6, we label the preference levels
O � � − � = .
�
larger than 0 with the plus sign (+).
���
Compared to GSAMF, which solves for the exact flow amount for each construction
20
plan, GSAMFE indeed saves time with the idea of flow estimation.
28