Geoscience Reference
In-Depth Information
adding a second identical customer node j
0
to the system in Example 1. Now, if
customers at both nodes are assigned to different facilities: x
ij
D
1;x
.1i/j
D
0,
x
ij
0
D
0;x
.1i/j
0
D
1 for j
D
0;1, we have two different equilibria. In fact, there
may be infinitely many equilibria: any assignment satisfying
x
ij
D
Ǜ;x
.1i/j
D
1
Ǜ;x
ij
0
D
1
Ǜ;x
ij
0
D
Ǜ; Ǜ
2
Œ0;1
is also an equilibrium. In principle, different equilibrium allocation vectors may
lead to different values of the objective function in the underlying SLCIS model,
creating uncertainty as to which solution will actually arise. However, all equilibria
are “similar” in certain key aspects, as shown in the following theorem based on the
result provided in Brandeau and Chiu (
1994
):
Theorem 17.2
For any two customer flow equilibria under which a subset
J
0
J
is fully served, the values of
i
i
2
I
(total demand seen at each facility) and
v
j
;j
2
J
(equilibrium disutility of each customer node) are the same.
This theorem implies that, under a sensible specification of the objective function,
where the total travel and waiting cost for each customer node is a function of v
j
,
all equilibria will give rise to the same values of the objective.
While the previous results show that AR models with multi-sourcing demand
allocations are well-posed, there is an important issue concerning computational
tractability of system (
17.31
)-(
17.38
). Even for fixed facility locations and capac-
ities, solving the customer flow equilibrium conditions is far from easy. While
certain numerical approaches (described in Nagurney
1999
) do exist, they are
computationally heavy even for moderate-size problems (see Tong
2011
). Often,
to get reasonable algorithmic efficiency one has to make simplifying assumptions
about the system, e.g., assuming M=M=1 queues simplifies (
17.31
), making the
system much more solvable—see Zhang et al. (
2010
) who were able to compute
equilibria for a system with
j
J
j
500 and
j
I
j
40 (note that their model also
had elastic demands, which likely increased computational complexity). Keeping in
mind that computing customer flow equilibrium is only a subproblem of an SLCIS
model, embedding this computation in an overall exact optimization procedure is
nearly impossible. Hence both of the papers cited above resort to search heuristics
for the upper level (location and capacity allocation decisions).
In view of the difficulties involved in using the customer flow equilibrium
approach above, it is natural to think of model simplifications. We mention three
such approaches. One is to keep the single-sourcing assumption in spite of the
possible non-existence of equilibria (see Zhang et al.
2009
). The reason this may be
reasonable is that, as mentioned earlier, nonexistence is a result of discontinuity—
when re-assignment of a single customer alters the waiting times at the facility
for the remaining customers. It is reasonable to assume that for realistic problem
instances, this should not be an issue: as the number of customers and customer
nodes grows, no single assignment should exert a significant impact on waiting
times at the facilities. Thus, asymptotically, single-sourcing equilibria should
emerge. Indeed, Zhang et al. (
2009
) did not report issues with nonexistence of
