Geoscience Reference
In-Depth Information
Recall the definition of
u
j
givenby(
17.26
), which is now interpreted as the
expected utility for customers at j
2
J given a fractional allocations vector x
ij
;j
2
J;i
2
I (we emphasize that the waiting times are affected by the allocations of all
customers, not just the ones at j). We seek allocations under which no customer can
improve their utility by making unilateral changes. It follows that the equilibrium
utilities
u
j
;j
2
J must satisfy
(
D
u
j
if x
ij
>0
I
u
j
if x
ij
D
0
d.i;j/
C
W
i
(recall that we are assuming linear utilities which are equal to the negative of total
travel and waiting times). These conditions can be represented by replacing (
17.30
)
with the following non-linear complementarity conditions:
d.i;j/
C
W
i
v
j
;j
2
J;i
2
I
(17.36)
.d.i;j/
C
W
i
v
j
/x
ij
D
0; j
2
J;i
2
I
(17.37)
v
j
0; j
2
J
(17.38)
where v
j
D
u
j
, representing the equilibrium “disutility” for customers at j
2
J,
is included in the model as a new decision variable. We will refer to a solution of
the system (
17.31
)-
17.38
)as
Customer Flow Equilibrium
.
The following result follows direc
tly
from Theorem 5.4 of Ashtiani and Magnanti
(
1981
) by continuity of U
d.i;j/;W
i
.
/
for all j
2
J;i
2
I,where
x
x
is a
fractional allocation vector with components x
ij
.
Theorem 17.1
For any values of
y
i
2f
0;1
g
and
i
0
such that
i
My
i
,
if a subset
J
0
J
is serviceable, then there exists at least one customer flow
equilibrium
x
ij
;j
2
J;i
2
I
under which
J
0
is fully served.
In particular, if the system has the capacity to service all of customer demand,
i.e., J is serviceable, at least one customer flow equilibrium must exist under which
all customers are served.
The discussion and the result above is quite general: in particular, it extends to
models with elastic demand (i.e., models of type FR discussed below). Additionally,
in place of the expected waiting time for an M=G=1 queue, a general measure of
“congestion” can be used with the only requirements that it is strictly increasing,
twice differentiable, non-negative and convex (recall that all capacity decisions are
considered to be fixed in this section). These requirements are clearly satisfied
by most performance measures for queueing systems, including multi-server and
limited-buffer queues. We refer the reader to Brandeau et al. (
1995
) for a discussion
of these more general settings.
It is important to realize that the customer flow equilibrium may not be unique. In
fact, there may be multiple allocation vectors satisfying the equilibrium conditions
for a particular fully served subset of customer nodes. For an example, consider
