Page 30 - 33-3

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

The preference of customers can be transformed into the graph as a maximum flow
problem as Figure 1 in Section 4.1.1.

Table 6 Example Preferences (Positive Ones Are Marked)

(j, t): facility j with activity session t
customer i
(1, 1) (1, 2) (2, 1) (2, 2) (3, 1) (3, 2)
1 + +
2 + +
3 + +

We now start to run GSAMF and GSAMFE on this example. In iteration 1, the
estimation step of first iteration, since none of the facilities are added into the construction
plan, we compute the estimated flow z'(y) of all facilities with its scale level. The estimated

flow z'(y) and the ratio Ratio'(j,k|y) are listed in Table 7. We also list the exact objective
value z(y) of our GSAMF algorithm, which solves exact objective value z(y) with
maximum flow in every iteration, in the table.
Take facility 3 with scale level 1 for example, if we add it into our construction
plan, the customers who are willing to go to those built facilities are customer 2 and 3.

Thus, the potential customer demand of each customer is α =min{d ,q }=min{9,5}
3,1
2
2
and α = min{d ,q } = min{11,5}, respectively. The potential facility supply of the only
3,2
3
3
built facility 3, β , is min{d ,q }+min{d ,q }=min{9,5}+min{11,5}=10. Therefore,
2
3,1
3,2
3
3
the estimated flow of adding facility 3 with scale level 1 is z' (y)=min{∑ α ,∑ β
j∈J j
i∈I i
}=min{5+5,10}=10, and Ratio' (3,1|y) is 1.
According to Table 7, we choose facility 3 with scale level 1 since its Ratio'(j,k|y) is
the highest one. After adding it into the construction plan (which is constructing nothing
at the beginning of iteration 1), we end this iteration and proceed to the second iteration
with only facilities 1 and 2 remain as candidates. The result is shown in Table 8. Note
that facility 1 with capacity 2 does not have to take into calculation since we do not have
enough budget to build it. At the end of the second iteration, we add facility 1 with scale
level 1 into our construction plan. The result is shown in Table 9.

22