close

Вход

Забыли?

вход по аккаунту

?

Proportional lot sizing and scheduling Some extensions

код для вставкиСкачать
On the Relationship between Dynamic Nash
and Instantaneous User Equilibria
Byung-Wook Wie, 1 Roger L. Tobin 2
1
School of Travel Industry Management, University of Hawaii, 2560 Campus Road,
Honolulu, Hawaii 96822
2
GTE Laboratories Incorporated, Waltham, Massachusetts 02254
Received 6 September 1995; accepted 26 May 1998
Abstract: The problem of a dynamic Nash equilibrium traffic assignment with schedule delays on
congested networks is formulated as an N-person nonzero-sum differential game in which each player
represents an origin–destination pair. Optimality conditions are derived using a Nash equilibrium solution
concept in the open-loop strategy space and given the economic interpretation as a dynamic game
theoretic generalization of Wardrop’s second principle. It is demonstrated that an open-loop Nash equilibrium solution converges to an instantaneous dynamic user equilibrium solution as the number of players
for each origin–destination pair increases to infinity. An iterative algorithm is developed to solve a discretetime version of the differential game and is used to numerically show the asymptotic behavior of openloop Nash equilibrium solutions on a simple network. A Nash equilibrium solution is also analyzed on the
18-arc network. q 1998 John Wiley & Sons, Inc. Networks 32: 141–163, 1998
1. INTRODUCTION
The problem of dynamic traffic assignment is to predict
time-varying flow patterns and travel costs on transportation networks where travel demands and arc capacities
change over time and space. In recent years, there have
been extensive research activities in the development of
mathematical models, computer simulation models, and
solution algorithms for such a problem. Comprehensive
reviews of various models and algorithms proposed to
date can be found in Watling and van Vuren [31], Friesz
et al. [10], and Ran and Boyce [21].
When there are considerable time-to-time and day-today variations in travel demands and arc capacities due
to road construction, traffic accidents, or bad weather conditions, network users try to optimize their departure time
Correspondence to: B.-W. Wie; e-mail: bjwie@hawaii.edu
and route decisions each day on the basis of current traffic
information for the whole network. As each user moves
downstream, it can instantaneously revise its route choice
at any en-route intersection node if the current route is
no longer optimal on the basis of updated information.
Optimal control theory has been applied to develop the
so-called instantaneous dynamic user equilibrium traffic
assignment models. For details of such models, the reader
is referred to Wie [32], Friesz et al. [11], Wie et al.
[36], Ran et al. [22], and Boyce et al. [2].
The term instantaneous is used for the behavioral assumption that departure time and route decisions of network users are based on unit path travel costs that are
instantaneously calculated at each moment in time. A
solution of an equivalent optimal control problem represents a temporal evolution of the traffic-flow pattern corresponding to the following dynamic generalization of
Wardrop’s user equilibrium principle (Wardrop [30]):
q 1998 John Wiley & Sons, Inc.
CCC 0028-3045/98/020141-23
141
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
W: Networks
830
142
WIE AND TOBIN
Definition 1. If , at each instant in time, the instantaneous unit travel costs for all departure time and route
choices for each origin–destination pair are identical
and equal to the minimum instantaneous unit travel cost,
the corresponding time-varying flow pattern is an instantaneous dynamic user equilibrium.
The above traffic assignment principle does not require
equilibration of unit path travel costs that are actually
experienced by network users with the same departure
time and origin–destination pair. Instead, it requires
equilibration of unit path travel costs that are instantaneously estimated at each moment in time by network users
with the same departure time and origin–destination pair.
A dynamic system equilibrium may be reached in a
centralized network where one player (e.g., a central traffic control authority) completely controls all transportation decisions of departure times, routes, and departure
flow rates. This equilibrium concept has been widely used
in the modeling of freight transportation and telecommunication networks. A dynamic system equilibrium flow
pattern represents an efficient allocation of scarce network
capacities and provides a lower bound on the total transportation cost on a congested network with fixed demands. For a variety of dynamic system equilibrium traffic assignment models reported in the literature, the reader
is referred to Merchant and Nemhauser [19], Carey [4],
Friesz et al. [11], Mahmassani and Peeta [18], Lafortune
et al. [16], Wie et al. [37, 38].
Some intermediate situations between instantaneous
dynamic user equilibrium and dynamic system equilibrium may exist on future urban transportation networks
where more than one player can control departure time
and route decisions of network users. In the 21st century,
automated highways will be built and in-vehicle route
guidance systems will provide network users with optimal
departure time and routing information. Private communication companies will sell departure time and route guidance services to drivers equipped with in-car navigation
systems. These companies will compete with each other
to improve its customers’ travel times. A dynamic Nash
equilibrium may be reached when no company can improve customers’ travel times by unilaterally changing its
departure time and routing strategies. A solution of an Nperson nonzero-sum differential game represents a temporal evolution of traffic flow pattern corresponding to the
following dynamic generalization of Wardrop’s system
equilibrium principle (Wardrop [30]:
Definition 2. If , at each instant in time, the instantaneous marginal travel costs for all departure time and
route choices for each player are identical and equal
to the minimum instantaneous marginal travel cost, the
corresponding time-varying flow pattern is a dynamic
Nash equilibrium.
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
Dynamic Nash equilibrium traffic assignment problems also naturally arise in multimedia applications (e.g.,
teleconferencing, digital libraries, virtual reality telesimulations, and interactive televisions) over high-speed
broadband networks. A recent work of Economides [9]
considered the dynamic resource sharing problem in multimedia networks with multiple competing traffic types
and multiple objectives. In a multimedia network, telecommunication companies carrying different traffic types
(e.g., voice, data, and video) may share the limited common network resources such as buffers, switches, and
transmission lines. These companies may have different
objectives of maximizing packet throughput or minimizing packet blocking probability. A dynamic Nash equilibrium may be reached when no company can improve its
own performance by unilaterally changing its traffic load
admission and routing strategies. The reader is referred
to Wie [34] for another intermediate situation characterized as a dynamic mixed behavior traffic network equilibrium.
The objective of this paper was to characterize dynamic noncooperative Nash equilibria on congested traffic networks and to show that a Nash equilibrium solution
characterized in the open-loop strategy space converges
to an instantaneous dynamic user equilibrium solution as
the number of players increases to infinity. To do this,
we extend a differential game model of Nash equilibrium
traffic assignment in the work of Wie [33] which is applicable only to a network with one origin-destination pair
connected by parallel routes. The extended model can
now handle any general traffic network with many origins
and many destinations. We then apply the approach that
is similar to that of Haurie and Marcotte [13] to obtain
the convergence result.
Haurie and Marcotte [13] considered two static games
on a congested transportation network: (1) a noncooperative game among infinitely many players characterized
by user equilibrium and (2) a noncooperative game with
a finite number of players characterized by Nash equilibrium. They showed that the asymptotic behavior of a
Nash equilibrium yields, under appropriate assumptions,
a traffic-flow pattern corresponding to a Wardrop user
equilibrium. To our best knowledge, we are unaware of
any attempt in the literature to demonstrate the relationship between Nash and user equilibria in a dynamic setting and to show that the asymptotic behavior of an openloop Nash equilibrium yields a time-varying traffic-flow
pattern corresponding to an instantaneous dynamic user
equilibrium.
Another contribution of this paper is the development
of an iterative algorithm for solving, in discrete time, a
N-person nonzero-sum differential game formulation of
the Nash equilibrium traffic assignment problem. For an
application to large-scale traffic networks, the proposed
algorithm has the following attractive features: (1) No
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
path enumeration is required during the computation and
(2) the dynamic game framework provides a natural decomposition by time period which significantly reduces
the dimensionality of dynamic traffic assignment problems. In particular, no path-enumeration requirement is
very important for a real-time implementation of dynamic
traffic assignment models to support two major components of the Intelligent Transportation Systems (ITS):
Advanced Traveler Information Systems (ATIS), and
Advanced Traffic Management Systems (ATMS). Path
enumeration tends to cause heavy computational burden
because any network of realistic size has a huge number
of distinct paths between each origin–destination pair.
For an update of ITS developments, the reader is referred
to Sussman [27].
Our paper certainly contributes to a better understanding of departure time and route choice behavior of network users in the near future when the ITS are fully
operational with a varying degree of competition among
communication companies providing departure time and
route guidance services on a fee basis. Our paper, however, has several limitations that need to be addressed
here: First, a dynamic Nash equilibrium solution is characterized in an open-loop strategy space. When using the
open-loop strategies, players choose entire time trajectories of departure time and route decisions before the start
of the game and simultaneously commit themselves to
the chosen trajectories until the termination of the game.
Thus, open-loop strategies are often called path strategies.
It is, however, well known that a Nash equilibrium in
open-loop strategies may be dynamically inconsistent if
one or several players deviate from their equilibrium strategies for some time (Reinganum and Stokey [23]). To
avoid the possibility of dynamic inconsistency, our differential game model would need to be reformulated in a
closed-loop strategy space. Then, a closed-loop Nash
equilibrium is said to be subgame perfect because departure time and routing strategy of each player is the optimal
response to strategies of the other players, when viewed
from any intermediate time-state pairs. Closed-loop Nash
equilibrium solutions on general traffic networks, however, appear to be very difficult to obtain because they
must be explicitly expressed as analytic functions.
The second limitation of our paper is that an iterative
algorithm is proposed without a formal proof of convergence of a discrete-time solution to a continuous-time
solution. A rigorous convergence proof is needed to demonstrate that a discrete-time solution is a reasonable approximation to a continuous-time solution when small
enough sampling periods are used. Lastly, theoretical and
numerical results reported in this paper need to be empirically tested in real traffic networks. It is important to
answer questions as to whether open-loop Nash equilibria
would actually be reached in practice or whether closedloop Nash equilibrium solutions better represent the actu-
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
143
ally observed behavior of departure time and route choice
of network users.
The paper is organized as follows: In Section 2, the
problem of the dynamic Nash equilibrium traffic assignment with schedule delays is formulated as a N-person
nonzero-sum differential game in the open-loop strategy
space. In Section 3, the necessary conditions for an openloop Nash equilibrium solution are derived and given
the economic interpretation as a dynamic game theoretic
generalization of Wardrop’s second principle (Wardrop
[30]). In Section 4, the asymptotic behavior of an openloop Nash equilibrium is shown to yield a time-varying
traffic-flow pattern corresponding to an instantaneous dynamic user equilibrium. In Section 5, an iterative algorithm which makes use of the augmented Lagrangian
method and the gradient method is developed for solving
a discrete-time version of the differential game formulated
in Section 2. To numerically show the asymptotic behavior of open-loop Nash equilibrium solutions in discrete
time, changes in total travel cost and flow pattern are
compared while increasing the number of players from
one to 20 in a single-arc network with one origin–destination pair. Nash equilibrium solutions on the 18-arc network are also analyzed. The paper concludes with a discussion on future extensions of the proposed model and
algorithm. Key notation used in the paper is listed in
Appendix 1. The necessary conditions for an open-loop
Nash equilibrium solution are presented in Appendix 2.
2. MODEL FORMULATION
Let us consider a network represented by a directed graph
G(A, M) where A is the set of directed arcs and M is the
set of nodes. We use the index a to denote an arc, the
index k to denote a node, and the index p to denote a
path. Note that traffic volume is defined as the number
of vehicles present on any arc at some instant of time
and the traffic-flow rate is defined as the number of vehicles passing a fixed point on any arc per unit time. Also,
note that all flow variables are taken to be continuous
throughout our analysis.
We assume that N players share a network and interact
through the congestion phenomenon which modifies
travel time on each arc at each instant of time. The set
of players is denoted by I. Each player indexed by i
represents an origin–destination pair. The origin node
and destination node of player i will be denoted by kU i
and nV i , respectively. The set of all simple paths connecting origin kU i and destination nV i is denoted by PkU inV i . Each
player competes in a Nash equilibrium manner so as to
minimize his own transportation cost in the task of transporting the predetermined volume of traffic from its origin kU i to its destination nV i during a fixed planning horizon
of length T.
W: Networks
830
144
WIE AND TOBIN
Let xa (t) denote the total traffic volume on arc a at
time t, and x ia (t), the traffic volume of player i on arc a
at time t. Since a network is shared by N players, it
follows at once that
xa (t) Å ∑ x ia (t)
∀a √ A, t √ [0, T].
(1)
i√I
After Merchant and Nemhauser [19], we depict the physical phenomenon of traffic congestion on each arc through
the exit flow rate functions ga[xa (t)] which are assumed
to be nonnegative, nondecreasing, continuously differentiable, and concave for all xa (t) ¢ 0 with the restriction
that ga (0) Å 0 for all a √ A and t √ [0, T]. By assuming
that traffic units of all players are uniformly and completely mixed on each arc, we have the following relationships:
g ia [x ia (t), x 0a i (t)]
ga[xa (t)]
Å
x ia (t)
xa (t)
negativity of state variables because Eq. (2) and the assumption that ga (0) Å 0 ensure that state variables are
always nonnegative.
Let Q iT denote the predetermined traffic volume that
player i has to transport from origin kU i to destination nV i
by the terminal time T. The following isoperimetric constraint ensures that player i would complete its task of
transporting the predetermined traffic volume from origin
to destination by the terminal time T:
Q iT Å
i
a
i
a
Qg i (t) Å S i (t)
i
a
0i
a
xh (t) Å u (t) 0 g [x (t), x (t)]
∀a √ A, t √ [0, T],
(3)
where the overdot denotes differentiation with respect to
time, x ia (t) is a state variable, and u ia (t) is a decision
variable denoting the rate of traffic flow of player i entering arc a at time t. We assume that state variables are
given the following initial conditions:
x aj (0) Å x ajo ¢ 0
∀a √ A, j √ I.
(4)
We also require that both state and control variables are
nonnegative:
x aj (t) ¢ 0
j
a
u (t) ¢ 0
∀a √ A, j √ I, t √ [0, T],
(5)
∀a √ A, j √ I, t √ [0, T].
(6)
Note that we do not have to explicitly consider the non-
8u27
/ 8u27$$0830
07-29-98 20:42:01
∀t √ [0, T],
Q i (0) Å 0,
0i
a
i
a
S i (t) dt,
netwa
(7)
where S i (t) is the rate of traffic flow of player i departing
from origin kU i at time t and traveling to destination nV i .
For ease of handling in a differential game formulation,
constraint (7) is transformed to a linear differential equation with initial and terminal conditions as follows:
(2)
where g [x (t), x (t)] is the rate of traffic flow of
player i exiting from arc a at time t and x 0a i is the total
traffic volume of all other players except player i. Note
that arc exit flow rate functions represent essentially flow/
density relations of the type usually applied to model
highway traffic flows. The interested reader is referred to
Wie et al. [39] for the advantages and shortcomings of
using the Merchant–Nemhauser-type exit flow rate functions.
For player i, the dynamic evolution of the state of each
arc is described by a nonlinear differential equation:
i
a
T
0
∀a √ A, i √ I, t √ [0, T],
i
a
*
(8)
(9)
Q i (T ) Å Q iT ú 0,
(10)
where Q i (t) is a state variable, denoting the cumulative
volume of traffic of player i departed from origin node
by some time t √ [0, T], and S i (t) is a decision variable.
We require that both state and decision variables are always nonnegative:
Q i (t) ¢ 0
∀t √ [0, T],
(11)
S i (t) ¢ 0
∀t √ [0, T].
(12)
Note that we do not have to explicitly consider the nonnegativity constraint (11) because Q iT is a known nonnegative constant and S i (t) is required to be nonnegative.
Conservation of traffic flows at the origin node of
player i is ensured by the equality constraint:
∑
S i (t) 0
u ia (t) Å 0
∀t √ [0, T],
(13)
i
a √ A (kU )
where A(kU i ) is the set of arcs whose tail node is the
origin of player i. Conservation of traffic flows at all other
nodes except for origin and destination of player i is
ensured by the equality constraint:
∑ g ia [x ia (t), x 0a i (t)] 0 ∑ u ia (t) Å 0
a √ B (k )
a √ A (k )
∀k √ (M " {kU i , nV i }), t √ [0, T],
(14)
where B(k) is the set of arcs whose head is k, A(k) is
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
the set of arcs whose tail node is k, and M " {kU i , nV i } is
the set of all nodes except origin and destination of player
i. Let I " i denote the set of players except for a player
indexed by i. Let us define the following vector notation:
x Å {x aj (t): a √ A, j √ I, t √ [0, T]},
Q i Å {Q i (t): t √ [0, T]},
S i Å {S i (t): t √ [0, T]},
u i Å {u ia (t): a √ A, t √ [0, T]},
145
The last one is the cost associated with total schedule
delay of player i that would be incurred by early and late
arrivals at its destination outside the desired arrival time
interval, where B(nV i ) is the set of arcs whose head node
is the destination of player i. In the remainder of this
paper, the above differential game will be referred to as
the differential game G. Note that the differential game G
is reformulated in Wie [35] for traffic situations where
each player makes departure time and route choice decisions for its flow units traveling between multiple origin–
destination pairs instead of only one origin–destination
pair.
S 0i Å {S j (t): j √ (I " i), t √ [0, T]},
3. NASH EQUILIBRIUM CONDITIONS
u 0i Å {u aj (t): a √ A, j √ (I " i), t √ [0, T]}.
To effect some economy of notation, we will employ the
following set of admissible solutions for player i:
V i Å {(x, Q i , S i , u i ): (3), (4), (6), (8), (9),
(10), (12), (13), (14) are satisfied}.
(15)
We assume that traffic flow units of each player do
not have to arrive at its destination at a precise moment,
but have some latitude to arrive early or late. Let [tH i 0 D i ,
tH i / D i ] denote the desired arrival time interval of player
i, where tH i is the center of the interval and D i measures
the flexibility of the arrival time. We also assume that
the unit schedule delay cost functions f i (t) are continuous and nonnegative for all t √ [0, T]. In particular, the
value of f i (t) is zero when tH i 0 D i ° t ° tH i / D i and
positive otherwise.
We now formulate a dynamic Nash equilibrium traffic
assignment model with schedule delays as an N-person
nonzero-sum differential game: Given S 0i and u 0i , each
player i √ I chooses S i and u i to minimize J i (x), where
J i (x) Å ∑ a ia x ia (T ) / ∑
a√A
a√A
/
∑
i
a √ B (nV )
*
*
T
b ia x ia (t) dt
0
Definition 3. Two N-tuples of strategies (S 1 *, . . . , S N *)
and (u 1 *, . . . , u N *), with S i * √ V i and u i * √ V i for
each i √ I, are said to constitute an open-loop Nash
equilibrium solution if and only if the inequalities
(16)
T
i
f i (t)g ia [x ia (t), x 0
a (t)] dt
J i (x*, S i *, S 0i *, u i *, u 0i *)
0
° J i (x*, S i , S 0i *, u i , u 0i *)
subject to (x, Q i , S i , u i ) √ V i . The objective function
J i (x), which measures the total generalized transportation cost incurred by player i over the planning horizon
[0, T], consists of three components: The first one is the
cost associated with the traffic volume of player i that
would have not reached its destination by the terminal
time T, where a ia is the penalty parameter. The second
one is the cost associated with total travel time that would
be spent by player i on the network over the entire planning horizon, where b ia is the value of unit travel time.
8u27
In this section, we derive the necessary conditions for an
open-loop Nash equilibrium solution of the differential
game G and provide them with economic interpretations.
In the present analysis, we consider the open-loop strategy
space. One may wish to consider another type of strategy
space for a modeling of traffic networks with advanced
traveler information systems which would be widely
available in the 21st century. For instance, a Nash equilibrium in closed-loop strategies is dynamically consistent
because players choose their strategies as a function of
time and the current state of the network that may be
obtained via a real-time traffic information system. A
closed-loop analysis, however, appears to be very complex for a general network with many origins and many
destinations because all players are allowed to choose
their closed-loop strategies from any class of functions.
Moreover, the so-called cross-effect terms in the set of
adjoint equations make it difficult to develop a direct
solution algorithm.
We make the following definition:
/ 8u27$$0830
07-29-98 20:42:01
netwa
(17)
are satisfied for all S i √ V i , u i √ V i , and i √ I.
This type of solution is secure because no player can
reduce its own total transportation cost by unilaterally
deviating from its Nash strategy as long as the other players continue to use their Nash strategies.
To apply a Pontryagin-type minimum principle developed in Starr and Ho [26] and Basar and Olsder [1], we
construct the Hamiltonian for each player i √ I as
W: Networks
830
146
WIE AND TOBIN
H i[x(t), Q i (t), S i (t), u i (t), l i (t), c i (t)]
Å
∑ b ia x ia (t)
a√A
/
∑ f i (t)g ia [x ia (t), x 0a i (t)]
(18)
i
a √ B (nV )
/
∑ lia (t)[u ia (t) 0 g ia [x ia (t), x 0a i (t)]]
a√A
0 c i (t)S i (t),
ciency theorems reported in the literature (see e.g., Stalford and Leitmann [25] and Jorgensen [15]) are not
readily applicable to the differential game G with mixed
state-control constraints. A similar difficulty arises in an
effort to apply existence theorems reported in the literature (see e.g., Tolwinski [28]) to the differential game G
with mixed state-control constraints. We thus reserve
these important topics for our future research.
Let V i[x*(t), t] denote the total generalized transportation cost of player i that is evaluated along Nash equilibrium-state trajectories starting from the point [x*(t), t]
and proceeding to the terminal point [x*(T ), T]. The
optimal value function V i[x*(t), t] is expressed as
where lia (t) is an adjoint variable associated with differential Eq. (3) and c i (t) is an adjoint variable associated
with differential Eq. (8). To augment equality constraints
(13) and (14) to the Hamiltonian, we construct the Lagrangian for each player i √ I as
V i[x*(t), t]
L i[x(t), Q i (t), S i (t), u i (t), l i (t), c i (t), n i (t), mi (t)]
Å min
i
S ,u
Å H i[x(t), Q i (t), S i (t), u i (t), l i (t), c i (t)]
i
3
∑
i
/ n (t) S (t) 0
/
∑
i
a
u (t)
i
a √ A (kU )
i
k
m (t)
i
i
k √ (M " {kU ,nV } )
3
4
/
(19)
i
a
0i
a
a √ B (k )
0
4
∑ u ia (t) ,
a √ A (k )
/ 8u27$$0830
07-29-98 20:42:01
a√A
∑
a √ B (nV i )
lia (t) Å
where n i (t) is a Lagrange multiplier associated with constraint (13) and mik (t) is a Lagrange multiplier associated
with constraint (14).
It should be noted that Theorem A-1 of Basar and
Olsder ([1], p. 278) does not directly apply to derive the
necessary conditions for the differential game with mixed
state-control constraints. Because the necessary conditions for the minimization of the Lagrangian in Eq. (19)
with respect to (S, u) for each player are essentially the
Kuhn–Tucker conditions for a single-player optimization
problem, Theorem 1 of Seierstad and Sydsaeter ([24],
pp. 276–277) can be applied to derive the necessary conditions for the differential game G. If (S*, u*) is an openloop Nash equilibrium solution of the differential game
G and (x*, Q*) is the corresponding state trajectories,
there exists ( l, c, n, m) such that the conditions presented
in Appendix 2 are satisfied. The necessary conditions
(51) – (70) in Appendix 2 propose a certain number of
admissible open-loop Nash equilibrium solutions, while
assuring that there is no other candidate that solves the
differential game G. The sufficient conditions still need to
be established to assert that (S*, u*) is indeed an openloop Nash equilibrium solution. Unfortunately, suffi-
8u27
a ia x ia* (T ) /
∑
a√A
*
*
T
b ia x ia* (y) dy
t
J
T
(20)
f i (y)g ia [x ia* (y), x 0a i * (y)] dy .
t
It is well known (Starr and Ho [26]) that an adjoint
variable measures the sensitivity of the optimal value
function V i[x*(t), t] to a small perturbation in a state
variable x ia (t) at time t:
∑ g [x (t), x (t)]
i
a
i
H∑
netwa
ÌV i[x*(t), t]
Ìx ia (t)
∀a √ A, i √ I, t √ [0, T].
(21)
It is clear from Eq. (21) that lia (t) is the marginal contribution of an additional unit of traffic flow of player i
entering arc a at time t to increase in its total generalized
transportation cost incurred during the period [t, T].
Therefore, lia (t) can be interpreted as the marginal travel
cost of player i to destination nV i if entrance to arc a occurs
at time t. From the complementary slackness conditions
(62), (65), and (67) in Appendix 2, similar economic
interpretations can be given to other multipliers as follows: (1) n i (t) is the minimum marginal travel cost of
player i to destination nV i if departure from origin kU i occurs
at time t, (2) mik (t) is the minimum marginal travel cost
of player i to destination nV i if departure from an intermediate node k (k x kU i ) occurs at time t, and (3) c i is the
minimum marginal travel cost of player i from origin
kU i to destination nV i regardless of departure time and/or
route selected over the entire planning horizon [0, T].
We now wish to show that an open-loop Nash equilibrium solution of the differential game G is a time-varying
flow pattern corresponding to a dynamic game theoretic
generalization of Wardrop’s second principle. To this end,
we first rewrite adjoint Eqs. (54) and (55) as follows:
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
1
i
a
0i
a
i
a
i
a
Ìg [x (t), x (t)]/ Ì x (t)
MD ia [x ia (t), x 0a i (t)]
[ b ia / lg ia (t)]
(22)
Å lia (t) 0 mik (t)
Å
1
i
i
Ìg ia [x ia (t), x 0
a (t)]/ Ì x a (t)
i
i
Ìg ia [x ia (t), x 0
a (t)]/ Ì x a (t)
i
a
i
a
[ b / lg (t)]
(23)
Å lia (t) 0 f i (t)
∀a √ B(nV i ), i √ I, t √ [0, T].
Using economic interpretations of adjoint variables and
Lagrange multipliers provided earlier, the left-hand side
of each of Eqs. (22) and (23) can be interpreted as the
instantaneous marginal cost of traversing arc a at time t
for player i.
Using Lemma 1 of Carey and Srinivasan ([5], p. 221),
we can obtain an additional interesting interpretation for
Eqs. (22) and (23). To this end, we assume that the
expected time to traverse arc a if entrance to arc a occurs
at time t is dependent only on xa (t) and the instantaneous
travel time functions Da[xa (t)] are positive, nondecreasing, continuously differentiable, and convex for all xa (t)
¢ 0 and t √ [0, T]. We also assume that arc traffic
volumes do not abruptly change over time. Using the
flow/density relationship in traffic flow theory, we know
that
xa (t) Å Da[xa (t)]ga[xa (t)]
∀a √ A, t √ [0, T].
(24)
Using Eq. (2), we also know that
x ia (t) Å Da[xa (t)]g ia [x ia (t), x a0i (t)]
∀a √ A, i √ I, t √ [0, T].
(25)
Differentiating Eq. (25) with respect to x ia (t) and rearranging yields
1
Å Da[xa (t)]
i
i
Ìg ia [x ia (t), x 0
a (t)]/ Ì x a (t)
i
/ g ia [x ia (t), x 0
a (t)]
1
ÌDa[xa (t)]
Ìx ia (t)
(26)
Ìx ia (t)
i
Ìg [x (t), x 0
a (t)]
i
a
i
a
∀a √ A, i √ I, t √ [0, T].
/ 8u27$$0830
07-29-98 20:42:01
where MD ia [x ia (t), x 0a i (t)] can be interpreted as the instantaneous marginal arc travel time function of player i.
Let us consider a particular path p that connects the
origin and destination nodes of player i, (kU i , nV i ) and
express it in the generic form as
p Å [kU i Å k 0 , a1 , k1 , a2 , . . . , kr 01 , ar , nV i Å kr ].
(28)
We then define the instantaneous marginal path cost function of player i as
C ip (t) Å
∑ MD ia [x ia (t), x 0a i (t)]
a √ A (p )
1 [ b ia / lg ia (t)] / f i (t)
(29)
∀ p √ PkU inV i , i √ I, t √ [0, T],
where A (p) is the set of arcs comprising path p and b ia
is a positive constant that is the value of unit travel time
of player i on arc a. The function C ip (t) consists of two
cost components: one associated with path travel time
and the other associated with schedule delay. The first
component associated with path travel time is divided
into static and dynamic terms: MD ia [x ia (t), x 0a i (t)] b ia is
a static term representing the marginal arc travel cost of
player i at time t, and MD ia [x ia (t), x 0a i (t)] lg ia (t) is a
dynamic term representing the time rate of change of the
marginal arc travel cost of player i. The sign of this
dynamic term depends on whether lia (t) is increasing or
decreasing with respect to time. As will be demonstrated
in Section 6, lia (t) generally increases in prepeak periods
and decreases in postpeak periods. The second component
f i (t) is the marginal schedule delay cost of player i if
arrival at destination nV i occurs at time t. Note that f i (t)
is time varying but constant with respect to arc traffic
volume and flow rate (i.e., not flow-dependent) and thus
marginal schedule delay costs are the same as unit schedule delay costs.
We now state and prove the following result:
Theorem 1. If u ia (t) ú 0 for all a √ A (p) at some time
t √ [0, T], then C ip (t) Å min{ C iq (t): ∀q √ PkU inV i } for
an open-loop Nash equilibrium solution of the differential
game G.
Proof. The proof is similar to that in Wie et al. [37].
Using Eqs. (22) and (23), we may rewrite the instantaneous marginal path cost function of player i as
Let us define the following notation:
8u27
(27)
∀a √ A, i √ I, t √ [0, T],
∀a √ B(k), k √ (M " {kU i , nV i }), i √ I, t √ [0, T],
1
147
netwa
W: Networks
830
148
WIE AND TOBIN
C ip (t) Å [ lia1 (t) 0 mik1 (t)]
/ [ lia2 (t) 0 mik2 (t)] / rrr / liar (t).
(30)
We know from Eqs. (64) and (66) that
lia1 (t) ¢ n i (t)
lia2 (t) ¢ mik1 (t)
:
(31)
:
liar (t) ¢ mikr01 (t).
Substituting Eq. (31) into Eq. (30), it follows at once
that
C ip (t) ¢ n i (t).
(32)
i
a
If u (t) ú 0 for all a √ A (p), then Eq. (32) holds as an
equality due to the complementary slackness conditions
j
(65) and (67). The theorem follows immediately.
Clearly, Theorem 1 preserves the static notion of Nash
equilibrium in a dynamic setting because the instantaneous marginal travel costs on utilized paths that connect
the same origin–destination pair are the same and equal
to the minimum instantaneous marginal travel cost. Moreover, we know from Eq. (13) that if u ia (t) ú 0 for any
a √ A(kU i ) at some time t √ [0, T] then S i (t) ú 0. We
also know from Eq. (62) that if S i (t) ú 0 then n i (t) Å c i .
Hence, the open-loop Nash equilibrium conditions presented in Appendix 2 can be interpreted as a dynamic
game theoretic generalization of Wardrop’s second principle which requires equilibration of instantaneous marginal travel costs for all departure time and route choices
that are being selected by each player.
In this section, we examine the relationship between
open-loop Nash and instantaneous dynamic user equilibria and show that the asymptotic behavior of an openloop Nash equilibrium yields a time-varying flow pattern
corresponding to an instantaneous dynamic user equilibrium. To prove the convergence result, we use a replication strategy which is similar to that of Debreu and Scarf
[8]. They assumed the economy to be composed of m
types of consumers with r consumers of each type. They
also assumed that all consumers of the same type have
the identical preferences and initial resources. It was then
proved that an allocation in the economy assigns the same
/ 8u27$$0830
07-29-98 20:42:01
Definition 4. The time-varying flow pattern ( xV , uV , SV )
is an instantaneous dynamic user equilibrium if Fp ( t )
Å min { Fq ( t ) : ∀q √ Pkn } when uV kn
a ( t ) ú 0 for all a
√ A ( p ) , p √ Pkn , k √ M, n √ M, and t √ [ 0 , T ] .
Note that the instantaneous dynamic unit path travel
cost functions are defined as
Fp (t) Å
∑ Da[xV a (t)][ ba / lg kna (t)] / f kn (t)
a √ A (p )
∀ p √ Pkn , k √ M, n √ M, t √ [0, T],
(33)
where Da[xV a (t)] ba is a static component of the instantaneous unit travel cost on arc a at time t, Da[xV a (t)] lg akn (t)
is a dynamic component of the instantaneous unit travel cost
on arc a at time t, and f kn (t) is the instantaneous unit
schedule delay cost at time t.
We now proceed to establish the following convergence result:
Theorem 2. An open-loop Nash equilibrium solution of
the differential game G converges to an instantaneous
dynamic user equilibrium solution as the number of identical players for each origin–destination pair increases
to infinity.
Proof. Let us assume that each of R identical players
for any origin–destination pair, j Å 1, . . . , R, has the
same instantaneous marginal arc travel time function:
4. CONVERGENCE TO INSTANTANEOUS
DYNAMIC USER EQUILIBRIA
8u27
commodity bundles to all consumers of the same type
and the resulting allocation is competitive as the number
of consumers becomes infinite. Recall that in the differential game G each player represents an origin–destination
pair who competes in a Nash equilibrium manner. We
make an additional assumption that, for each origin–destination pair, there is a set of R identical players who
have the same objective function, transportation demand,
and strategy space.
Before proceeding to prove the convergence, we present a mathematical characterization of an instantaneous
dynamic user equilibrium as follows:
netwa
MD ija [x ija (t), x 0a ij (t)] Å Da[xa (t)]
ij
/ g ija [x ija (t), x 0
a (t)]
1
ÌDa[xa (t)]
Ìx ija (t)
Ìx ija (t)
ij
ij
ij
Ìg a [x a (t), x 0
a (t)]
(34)
∀a √ A, i √ I, t √ [0, T].
We may rewrite the instantaneous marginal path cost
function for each identical player, j Å 1, . . . , R, as
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
∑ MD ija [x ija (t), x 0a ij (t)]
C ijp (t) Å
lim
a √ A (p )
ij
x a (t )r 0
ij
a
ij
a
ij
1 [ b / lg (t)] / f (t)
Å Da[xa (t)]
The fact that R players have the identical objective function, transportation demand and strategy space does not
mean that they act identically at dynamic Nash equilibria.
As a result, R players can make different departure time
and route choice decisions. It is, however, obvious from
Eq. (7) that
* S (t) dt Å QR
T
Q ijT Å
iT
∀i √ I, j Å 1, . . . , R.
ij
ÌDa[xa (t)]
Ìx ija (t)
ij
ij
ij
ij
Ìx a (t) Ìg a [x a (t), x 0
a (t)]
(35)
∀ p √ PkU inV i , i √ I, t √ [0, T].
(36)
0
We know from Eq. (36) that
149
dDa[xa (t)]
dxa (t)
(42)
∀a √ A, i √ I, j Å 1, . . . , R, t √ [0, T].
Because Q iT , which denotes the predetermined traffic volume that player i has to transport from origin kU i to destination nV i by the terminal time T, is bounded as defined in
Eq. (7), it is clear that xa (t) is bounded on every arc at
any instant in time and the product of the partial derivatives in the second term on the right side of Eq. (34)
stays bounded in the limiting process. It follows at once
that for each i Å 1, . . . , N and j Å 1, . . . , R
lim C ijp (t)
Rr`
Rr`cQ
ijT
r0
and
S (t) r 0.
ij
(37)
Å
∑ Da[xa (t)][ b ija / lg ija (t)] / f ij (t). (43)
a √ A (p )
We also know from Eqs. (3), (13), and (14) that
S (t) r 0 c x (t) r 0
ij
ij
a
and
g ija [x ija (t), x 0a ij (t)] r 0.
(38)
It remains to show in the limiting process that the
product of the partial derivatives in the second term on
the right side of Eq. (34) stays bounded. First of all,
because xa (t) Å x ija (t) / x 0a ij (t), we know that
ÌDa[xa (t)]
dDa[xa (t)]
Å
Ìx ija (t)
dxa (t)
(39)
∀a √ A, i √ I, j Å 1, . . . , R, t √ [0, T].
Using Eq. (25), we also know that
g ija [x ija (t), x 0a ij (t)] Å
x ija (t)
Da[xa (t)]
∀a √ A, i √ I, j Å 1, . . . , R, t √ [0, T].
(40)
Differentiating Eq. (40) with respect to x ija (t) yields
ij
Ìg ija [x ija (t), x 0
a (t)]
Ìx ija (t)
Å
Da[xa (t)] 0 x ija (t)dDa[xa (t)]/dxa (t)
{Da[xa (t)]} 2
(41)
Then, we know from Eqs. (39) and (41) that
/ 8u27$$0830
Theorem 2 establishes an interesting relationship between open-loop Nash and instantaneous user equilibria.
The asymptotic limit of an open-loop Nash equilibrium
flow pattern is shown to be an instantaneous dynamic user
equilibrium when network users experience considerable
time-to-time and day-to-day fluctuations in arc capacities
and travel demands. Our result presents a similarity with
classical results in economic theory that deals with the
convergence of Cournot–Nash spatial equilibria to spatial
price equilibria (see e.g., Dafermos and Nagurney [7]).
It should, however, be noted that our convergence result
does not directly apply to a situation where arc capacities
and travel demands are stable over time and network users
find their best departure times and routes through day-today explorations. In such a situation, a day-to-day dynamic user equilibrium flow pattern may be reached
wherein all network users with a common travel purpose
experience the same travel cost regardless of departure
time and route selected (see e.g., Wie et al. [39]).
5. SOLUTION ALGORITHM
∀a √ A, i √ I, j Å 1, . . . , R, t √ [0, T].
8u27
Therefore, the limiting case of an open-loop Nash equilibrium flow pattern corresponds to an instantaneous dynamic user equilibrium one.
j
07-29-98 20:42:01
netwa
In this section, we propose an iterative algorithm for solving a discrete-time version of the differential game G. The
proposed algorithm makes combined use of the augmented
Lagrangian method and the gradient method. The reader
is referred to Wie et al. [37] for a similar application
of these two methods to the solution of dynamic system
W: Networks
830
150
WIE AND TOBIN
TABLE I. Comparison of total travel costs (in minutes)
No.
players
Total travel
time
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Total schedule
delay
25989.38
31239.82
33539.19
34755.71
35497.45
36003.92
36213.18
36473.07
36739.77
37003.46
37076.74
37150.02
37223.30
37296.58
37369.86
37443.14
37516.42
37589.70
37662.98
37736.26
16484.43
12051.67
10433.74
9678.70
9245.59
8965.78
8826.05
8769.67
8570.96
8434.71
8399.83
8364.95
8330.07
8295.19
8260.31
8225.42
8190.54
8155.66
8120.78
8085.90
/
∑
∑ f i ( t )g ia [x ia ( t ), x a0i ( t )]
tÅ1 a √ B (nV i )
Total generalized
cost
/
42473.81
43291.49
43972.93
44434.41
44743.04
44969.70
45039.23
45242.74
45310.73
45438.17
45476.62
45515.07
45553.52
45591.97
45630.42
45668.86
45707.31
45745.76
45784.21
45822.66
TO 0 1
TO 0 1
∑ ∑ lia ( t / 1)[x ia ( t ) / u ia ( t )
tÅ0 a √ A
i
i
0 g ia [x ia ( t ), x 0
a ( t )] 0 x a ( t / 1)]
/
3
TO 0 1
∑ n i ( t ) S i ( t ) 0 ∑ u ia ( t )
tÅ0
/
TO 0 1
∑
∑
i
a √ A (kU )
mik ( t )
i
(48)
i
tÅ0 k √ (M " {kU ,nV } )
1
3
∑ g ia [x ia ( t ), x 0a i ( t ) 0 ∑ u ia ( t )
a √ B (k )
3
a √ A (k )
/ c i Q iTO 0
/
equilibrium traffic assignment problems. To obtain computerized numerical solutions, the entire planning horizon
[0, T] is divided into (T̂ / 1) time periods of uniform
length of Dt. For the sake of computational simplicity, the
length of each time period is assumed to be unity. Each
time period is indexed by t where t Å 0, . . . , T̂.
Let us formulate the dual problem of a discrete-time
version of the differential game G as follows: Given S 0i
and u 0i , for each player i √ I,
/
0
r
2
TO 0 1
z
2
TO 0 1
∑
tÅ0
∑
TO 0 1
∑ Si(t)
tÅ0
3
∑ u ia ( t )
Si(t) 0
i
a √ A (kU )
∑
i
i
tÅ0 k √ (M " {kU ,nV } )
∑ u ia ( t )
a √ A (k )
G
3
i
i
i
i
u ,S
∀a √ A, t Å 0, . . . , TO 0 1,
(45)
∀t Å 0, . . . , TO 0 1,
(46)
∀a √ A, j √ I,
(47)
i
S (t) ¢ 0
x aj (0) Å x ajo ¢ 0
where the augmented Lagrangian dual function is defined
as
L i (x, S i , S 0i , u i , u 0i , l i , n i , mi , c i )
Å
TO 0 1
∑ aP ia x ia (TO ) / ∑ ∑ bO ia x ia ( t )
a√A
8u27
tÅ1 a √ A
/ 8u27$$0830
07-29-98 20:42:01
netwa
2
a √ B (k )
2
/
u ia ( t ) ¢ 0
4
∑ g ia[x ia ( t ), x 0a i ( t )]
i
subject to
4
4
max {min L i (x, S i , S 0i , u i , u 0i , l i , n i , mi , c i )}, (44)
n ,m ,c
4
s
2
3
TO 0 1
Q iTO 0 ∑ S i ( t )
tÅ0
4
2
,
where r, z , and s are positive penalty parameters.
The proposed algorithm is composed of two sets of
iterations. The main iterations update Lagrange multipliers ( n, m, c ) and the subiterations solve two-point boundary-value problems with fixed Lagrange multipliers. The
main iteration is initiated by guessing the nominal values
of Lagrange multiplier sequences and the subiteration is
initiated by guessing the nominal values of decision variable sequences. All zero values may be chosen for these
guessed sequences. Details of the algorithm are described
as follows:
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
Fig. 1. Changes in total travel time.
Fig. 2. Changes in total schedule delay.
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
W: Networks
830
151
152
WIE AND TOBIN
Fig. 3. Changes in total generalized cost.
Fig. 4. Comparison of arc traffic volumes.
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
153
Fig. 5. Comparison of arc inflow rates.
STEP 1. Choose the initial values of the Lagrange multipliers:
n r Å [ n ir ( t ) : i √ I, t Å 0, . . . , TO 0 1],
r
ir
k
r
ir
m Å [ m ( t ) : k √ N, i √ I, t Å 0, . . . , TO 0 1],
c Å [ c : i √ I].
Set the main iteration index r Å 1 and go to Step 2.
STEP 2. Solve two-point boundary-value problems with
fixed Lagrange multipliers:
SUBSTEP 1. Choose the initial values of decisions variables:
u rz Å [u airz ( t )] : a √ A, i √ I, t Å 0, . . . , TO 0 1],
S rz Å [S irz ( t ) : i √ I, t Å 0, . . . , TO 0 1].
Set the subiteration index z Å 1 and go to Substep 2.
SUBSTEP 2. Solve state difference equations forward in
time:
Fig. 6. Eighteen-arc test network with 30 origin–destination pairs.
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
W: Networks
830
154
WIE AND TOBIN
TABLE II. Parameters in arc exit flow rate functions
0 lairz ( t / 1)
a
gamax
ga
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
30
30
30
30
40
40
60
60
80
80
60
60
40
40
30
30
30
30
200
200
200
200
400
400
500
500
700
700
500
500
400
400
200
200
200
200
x airz (t / 1) Å x airz (t) / u airz (t) 0 g ia[x airz (t), x 0irz
(t)]
a
∀ a √ A, i √ I, t Å 0, . . . , TO 0 1,
x ia (0) Å x ia0 ¢ 0
∀a √ A, i √ I.
SUBSTEP 3. Solve adjoint difference equations backward
in time:
lairz ( t ) Å bO ia / lairz ( t / 1)
0 lairz ( t / 1)
irz
Ìg ia [x airz ( t ), x 0
( t )]
a
irz
Ìx a ( t )
∀i √ I, a √ B(kU i ), t Å 0, . . . , TO 0 1,
lairz ( t ) Å bO ia / lairz ( t / 1)
0 lairz ( t / 1)
irz
Ìg ia [x airz ( t ), x 0
( t )]
a
irz
Ìx a ( t )
/ mirk ( t )
irz
Ìg ia [x airz ( t ), x 0
( t )]
a
irz
Ìx a ( t )
∀i √ I, a √ B(k), k √ (M " {kU i , nV i }),
t Å 0, . . . , TO 0 1,
lairz ( t ) Å bO ia / lairz ( t / 1)
/ fi(t)
8u27
irz
Ìg ia [x airz ( t ), x 0
( t )]
a
irz
Ìx a ( t )
/ 8u27$$0830
07-29-98 20:42:01
netwa
irz
Ìg ia [x airz ( t ), x 0
( t )]
a
irz
Ìx a ( t )
∀i √ I, a √ B(nV i ), t Å 0, . . . , TO 0 1,
lairz (TO ) Å aP ia
∀i √ I, a √ A.
SUBSTEP 4. Determine the gradients of the augmented
Lagrangian with respect to the decision variables:
ÌL irz
Å laiirz ( t / 1) 0 n ir ( t )
Ìu airz ( t )
3
0 r S irz ( t ) 0
∑ u airz ( t )
a √ A (kU i)
G
TABLE III. Origin-destination travel demands
O–D
no.
Origin
node
Destination
node
Demand
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
4
4
4
4
4
5
5
5
5
5
6
6
6
6
6
2
3
4
5
6
1
3
4
5
6
1
2
4
5
6
1
2
3
5
6
1
2
3
4
6
1
2
3
4
5
300
400
600
500
700
200
300
400
600
800
300
400
200
300
500
500
100
200
300
100
600
500
300
100
400
800
700
600
500
400
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
155
Fig. 7. Total arc traffic volumes.
∀i √ I, a √ A(kU i ), t Å 0, . . . , TO 0 1,
∀i √ I, a √ A, t Å 0, . . . , TO 0 1,
ÌL irz
Å laiirz ( t / 1) 0 mirk ( t )
Ìu airz ( t )
0z
3
S ir , z/ 1 ( t ) Å S irz ( t ) 0 h z
∑ g ia [x airz ( t ), x 0a irz ( t )] 0 ∑ u airz ( t )
a √ B (k )
a √ A (k )
4
∀i √ I, a √ A(k), k √ (M " {kU i , nV i }),
t Å 0, . . . , TO 0 1,
3
ÌL irz
Å n ir ( t ) 0 c ir 0 s Q iTO 0
ÌS irz ( t )
TO 0 1
∑ S irz ( t )
tÅ0
4
∀i √ I, t Å 0, . . . , TO 0 1.
∀i √ I, t Å 0, . . . , TO 0 1,
where u z and h z are the predetermined step sizes. Set
z Å z / 1 and repeat the computation starting at Substep 2 until the following stopping criterion is satisfied:
TO 0 1
∑ ∑ ∑ Éu ira , z/ 1 ( t ) 0 u airz ( t )É ° p,
tÅ0 a √ A i √ I
TO 0 1
∑ ∑ É S ir , z/ 1 ( t ) 0 S irz ( t )É ° v.
tÅ0 i √ I
STEP 3. Update the values of Lagrange multipliers:
SUBSTEP 5. Compute the new values of decision variables:
3
n i , r / 1 ( t ) Å n ir ( t ) / r S ir ( t ) 0
irz
u ira , z/ 1 ( t ) Å u airz ( t ) 0 u z
8u27
/ 8u27$$0830
ÌL
Ìu airz ( t )
07-29-98 20:42:01
ÌL irz
ÌS irz ( t )
∑ u ira ( t )
a √ A (kU i)
∀i √ I, t Å 0, . . . , TO 0 1,
netwa
W: Networks
830
4
156
WIE AND TOBIN
Fig. 8. Total arc traffic volumes.
mik, r / 1 ( t ) Å mirk ( t )
/z
3
∑
i
a
ir
a
g [x ( t ), x
0 ir
a
∑
( t )] 0
a √ B (k )
ir
a
u (t)
a √ A (k )
4
∀i √ I, k √ (M " {kU i , nV i }), t Å 0, . . . , TO 0 1,
3
c i , r / 1 Å c ir / s Q iTO 0
TO 0 1
∑ S ir ( t )
tÅ0
4
∀i √ I.
Set r Å r / 1 and repeat the computation starting at
Step 2 until the following stopping criteria are satisfied:
TO 0 1
∑ ∑
i √ I tÅ0
TO 0 1
∑ ∑
∑
3
i
S ir ( t ) 0
∑ u ira ( t )
a √ A (kU i)
i
i √ I tÅ0 k √ (M " {kU ,nV } )
3
2
° q,
∑ g ia [x ira ( t ), x 0a ir ( t )]
a √ B (k )
0
∑ u ira ( t )
a √ A (k )
8u27
4
/ 8u27$$0830
4
07-29-98 20:42:01
2
° j,
netwa
3
TO 0 1
∑ Q iTO 0 ∑ S ir ( t )
i√I
tÅ0
4
2
° £.
Convergence properties of the proposed algorithm
were not rigorously investigated in this paper. First of
all, a formal proof is needed to demonstrate that a discrete-time solution converges to a continuous-time solution as the length of sampling period gets shorter.
Convergence results established in optimal control
problems ( see e.g., Budak et al. [ 3 ] and Cullum [ 6 ] )
may be used for this purpose. Conditions to guarantee
convergence of the proposed algorithm to an open-loop
Nash equilibrium solution also need to be established.
Convergence properties of the augmented Lagrangian
method in Glad [ 12 ] and the gradient method in Lasdon
et al. [ 17 ] may be useful for finding conditions to guarantee its convergence. It should be noted that the application of the augmented Lagrangian method in this paper is different from its previous applications in optimal
control problems such as those of Hestenes [ 14 ] , Tripathi and Narendra [ 29 ] , and Glad [ 12 ] . These authors
adjoined state equations to the objective function,
whereas we adjoined state-decision equality constraints
as shown in Eq. ( 48 ) . As a result, the subproblem of
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
157
Fig. 9. Total arc inflow rates.
updating Lagrange multipliers in the algorithm becomes a set of two-point boundary-value problems with
fixed Lagrange multipliers that are to be solved for N
players. Once the state, decision, and adjoint variables
are determined at Substeps 1 – 3, the gradient of the
augmented Lagrangian can be computed independently
for each player.
where g amax is the maximum number of vehicles that can
exit from arc a in each time period and ga is the parameter
that is determined by arc characteristics such as length,
speed limit, traffic signal setting, etc.
For a computational simplicity, we assume that each
player has the same unit schedule delay cost function in
both numerical tasks. The unit schedule delay cost of
arriving at any destination in period t is given by the
following piecewise linear function:
6. NUMERICAL RESULTS
f( t )
In this section, two sets of computational results are presented: one that shows convergence of an open-loop Nash
equilibrium to an instantaneous dynamic user equilibrium
in discrete time on a simple network and the other that
analyzes an open-loop Nash equilibrium solution on a
relatively larger network. The assignment interval of 3
hours for both numerical tasks is discretized into 180 time
periods of 1 min length. The arc exit flow rate functions
expressed in the following functional form are used for
both tasks:
ga[xa ( t )] Å g amax r[1 0 e 0xa( t ) / ga ]
for
(49)
t Å 0, . . . , 180,
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
Å
Qr( tI 0 d 0 t )
if t õ tI 0 d
0
if tI 0 d ° t ° tI / d
Pr( t 0 tI 0 d )
if tI / d õ t,
(50)
where Q Å 0.5, P Å 2.4, d Å 10, and tI Å 100. The
parameter Q implies that 1 min of waiting at the destination in case of early arrival is twice as attractive as one
minute of travel time and the parameter P implies that 1
min of being late is 2.4 times as less attractive as 1 min
of travel time. The flexibility of arrival time is denoted
by d and the center of the desired arrival time interval is
denoted by tI .
To reduce computational requirements of the first
W: Networks
830
158
WIE AND TOBIN
Fig. 10. Total arc inflow rates.
Fig. 11. Departure flow rates and marginal costs. Origin Å 1; destination Å 3; i Å 2.
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
Fig. 12. Departure flow rates and marginal costs. Origin Å 6; destination Å 1; i Å 26.
Fig. 13. Arc inflow rates and marginal costs. Origin Å 3; destination Å 6; i Å 15.
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
W: Networks
830
159
160
WIE AND TOBIN
Fig. 14. Arc inflow rates and marginal costs. Origin Å 3; destination Å 6; i Å 15.
task, we consider a very simple network that consists
of one arc and one origin – destination ( O – D ) pair. We
assume that the arc has zero traffic volume at time t Å
0. The values of parameters in the arc exit flow-rate
function are given by g max Å 20 ( vehicles /minute ) and
g Å 200. The number of players competing in the test
network is increased from 1 to 20 with an increment
of one player. The total number of vehicles that are
controlled by all players is fixed: Q T̂ Å 1500 ( vehicles ) .
For example, when there are three players, we assume
that Q jT̂ Å 500 for j Å 1, 2, 3. For computational simplicity, the values of aP i and bO i in the objective function
are assumed to be the same all players and are given
by: aP i Å 100 and bO i Å 1. We also assume that all
players have the identical objective functions and strategy space.
Changes in total travel time, total schedule delay, and
total generalized travel cost are compared in Table I and
Figures 1–3 as the number of players, denoted by R,
increases from 1 to 20. Also, changes in arc traffic volume
and arc inflow rate are compared for selected numbers of
players (R Å 1, 5, and 20) in Figures 4 and 5. It is
observed that the total travel time increases as R increases,
but the total schedule delay decreases as R increases.
When R is 1, one player completely controls all decisions
of departure times and flow rates and attempts to smooth
traffic by making early and late departures (see Figs. 4
and 5), that is, the network is in a dynamic system equi-
8u27
/ 8u27$$0830
07-29-98 20:42:01
netwa
librium where the total generalized travel cost is minimized. As R increases, noncooperative decisions of players tend to move toward an instantaneous dynamic user
equilibrium. The asymptotic behavior of open-loop Nash
equilibrium solutions is numerically shown on a simple
network in discrete time.
We now wish to analyze an open-loop Nash equilibrium solution obtained on a network of 18 arcs, 6 nodes,
and 30 O–D pairs, as shown in Figure 6. The values of
g amax and ga for the 18 arcs are given in Table II. The
travel demands for 30 O–D pairs are given in Table III.
For a computational simplicity, the values of aP ia and bO ia
in the objective function are assumed to be the same for
all arcs and all players and are given by aP ia Å 100 and
bO ia Å 1. Note that a large value is assumed for aP ia so that
high penalties for remaining on the network in the terminal time period could prevent vehicles of each player
from circling around its destination. We also assume that
the unit schedule delay cost functions f i ( t ) are the same
for all players.
The time trajectories of total traffic volumes on selected arcs are shown in Figures 7 and 8. The time trajectories of total traffic inflow rates on selected arcs are also
shown in Figures 9 and 10. These figures exhibit the
expected peaking of traffic congestion in the neighborhood of the desired arrival time interval.
We now wish to check whether the algorithm indeed
yields an open-loop Nash equilibrium solution. To this
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
end, we choose two O–D pairs and plot the time trajectories of S i ( t ) and n i ( t ). As shown in Figures 11 and 12,
S i ( t ) is positive when n i ( t ) has the minimum value
[i.e., n i ( t ) Å c i ] and zero otherwise. Clearly, the complimentary slackness condition (62) is satisfied in discrete
time. It is also observed that departures occur earlier as
the distance between origin and destination gets longer.
Next, we choose one O–D pair (node 3 as origin and
node 6 as destination) and plot the time trajectories of
u ia ( t ), n i ( t ), and n ia ( t ). As shown in Figures 13 and
14, u ia ( t ) is positive when lia ( t ) Å n i ( t ) and zero otherwise. Evidently, the complimentary slackness condition
(65) is satisfied in discrete time.
7. CONCLUSION
We have analyzed the problem of the dynamic Nash equilibrium traffic assignment with schedule delays using differential game theory. Our main focus has been on the
relationship between open-loop Nash and instantaneous
dynamic user equilibria. We have demonstrated that as
the number of identical players for each origin–destination pair increases to infinity an open-loop Nash equilibrium solution converges to an instantaneous dynamic user
equilibrium solution. The other focus has been on the
development of an iterative algorithm not only to obtain
open-loop Nash equilibrium solutions but also to show
the asymptotic behavior of open-loop Nash equilibrium
solutions on a simple network.
The proposed model and algorithm encounter several
limitations and also suggest possible extensions: First, the
present analysis is restricted to open-loop strategies which
are known to be dynamically inconsistent if one or more
players deviate from their equilibrium strategies for some
time. The closed-loop Nash equilibrium analysis may be
needed for the modeling of traffic networks where realtime traffic information is available. Second, the sufficient
conditions need to be established to guarantee the optimality of an open-loop Nash equilibrium solution. Third,
convergence properties of the proposed algorithm need
to be rigorously investigated. Lastly, computational efficiency of the algorithm needs to be improved through
parallel processor implementation.
dexed by i
origin node of player i
destination node of player i
set of paths connecting origin kU i and
destination nV i
xa (t)
total traffic volume on arc a at time
t
traffic volume of player i on arc a at
x ia (t)
time t
flow rate of traffic of player i entering
u ia (t)
arc a at time t
ga[xa (t)]
flow rate of total traffic exiting from
arc a at time t
g ia [x ia (t), x 0a i (t)] flow rate of traffic of player i exiting
from arc a at time t
flow rate of traffic of player i deS i (t)
parting from origin kU i at time t and
destined to node nV i
i
cumulative volume of traffic of
Q (t)
player i departed from origin node
by some time t √ [0, T]
Q iT
predetermined traffic volume that
player i has to transport from origin kU i to destination nV i by the terminal time T
penalty incurred by one unit of traffic
a ia
of player i which would remain on
arc a at the terminal time T
transportation cost per unit travel
b ia
time on arc a incurred by one unit
of traffic of player i
Da[xa (t)]
instantaneous travel time on arc a if
entrance to arc a occurs at time t
f i (t)
unit schedule delay cost of player i
if arrival at its destination occurs
at time t
kU i
nV i
PkU inV i
APPENDIX 2. NECESSARY CONDITIONS
The necessary conditions which an open-loop Nash equilibrium solution for the differential game G must satisfy
are derived as follows:
xh ia* (t) Å u ia* (t) 0 g ia [x ia* (t), x a0 i * (t)]
∀a √ A, i √ I, t √ [0, T],
8u27
set
set
set
set
set
set
of arcs
of arcs whose tail node is k
of arcs whose head node is k
of nodes
of players
of players except for a player in-
/ 8u27$$0830
07-29-98 20:42:01
netwa
0 lg ia (t) Å
(51)
∀a √ A, i √ I,
(52)
Ìg ia [x ia* (t), x a0 i * (t)]
Ìx ia (t)
(53)
x ia (0) Å x ia0 ¢ 0
APPENDIX 1. NOTATION
A
A(k)
B(k)
M
I
I"i
161
ÌH i *
Ìx ia (t)
Å b ia 0 lia (t)
∀a √ B(kU i ), i √ I, t √ [0, T],
W: Networks
830
162
WIE AND TOBIN
0 lg ia (t) Å b ia 0 lia (t)
/ mik (t)
Ìg ia [x ia* (t), x a0 i * (t)]
Ìx ia (t)
i
i
u ia* (t) ¢ 0
i √ I, t √ [0, T],
S i *(t) 0
Ìg ia [x ia* (t), x a0 i * (t)]
0 lg ia (t) Å b ia / f i (t)
Ìx ia (t)
Ìg ia [x ia* (t), x a0i * (t)]
Ìx ia (t)
lia(T ) Å
a√A
i
a
Ìx (T )
0 cg i (t) Å
Å a ia ∀a √ A, i √ I,
(55)
∀i √ I,
Qg i *(t) Å S i *(t)
Q i (0) Å 0
∀i √ I,
∀i √ I,
i
ÌH *
Å n i (t) 0 c i ¢ 0
ÌS i (t)
S i *(t)
REFERENCES
(57)
[ 2]
(58)
[ 3]
(59)
(61)
S i *(t) ¢ 0
[ 5]
[ 6]
∀i √ I, t √ [0, T],
∀i √ I, t √ [0, T],
(62)
[ 7]
[ 8]
(63)
[ 9]
ÌH i *
Å lia (t) 0 n i (t) ¢ 0
Ìu ia (t)
∀a √ A(kU i ), i √ I, t √ [0, T],
u ia* (t)
ÌH i *
Å u ia* (t)[ lia (t) 0 n i (t)] Å 0
Ìu ia (t)
∀a √ A(kU i ), i √ I, t √ [0, T],
ÌH i *
Å lia (t) 0 mik (t) ¢ 0
Ìu ia (t)
(64)
[10]
(65)
∀a √ A(k),
/ 8u27$$0830
07-29-98 20:42:01
[11]
[12]
(66)
k √ (M " {kU i , nV i }), i √ I, t √ [0, T],
8u27
(70)
i
(56)
∀i √ I, t √ [0, T],
ÌH i *
Å S i *(t)[ n i (t) 0 c i ] Å 0
ÌS i (t)
a √ A (k )
∀k √ (M " {kU , nV }), i √ I, t √ [0, T].
(60)
Q (T ) Å Q ú 0
∑ u ia* (t) Å 0 ∀i √ I, t √ [0, T], (69)
i
∀i √ I,
iT
(68)
∑ g ia [x ia* (t), x a0 i * (t)] 0 ∑ u ia* (t) Å 0
[ 4]
i
∀a √ A, i √ I, t √ [0, T],
a √ B (k )
[ 1]
ÌH i *
Å0
ÌQ i (t)
(67)
a √ A (kU i)
∀a √ B(nV i ), i √ I, t √ [0, T],
Ì ( a ia x ia(T )
∀a √ A(k),
i
k √ (M " {kU , nV }), i √ I, t √ [0, T],
(54)
∀a √ B(k), k √ (M " {kU , nV }),
0 lia (t)
ÌH i *
Ìu ia (t)
Å u ia* (t)[ lia (t) 0 mik (t)] Å 0
Ìg ia [x ia* (t), x a0 i * (t)]
Ìx ia (t)
i
u ia* (t)
netwa
T. Basar and G. J. Olsder, Dynamic Noncooperative
Game Theory. Academic Press, New York (1982).
D. E. Boyce, B. Ran, and L. J. LeBlanc, Solving an
instantaneous dynamic user-optimal route choice model.
Trans. Sci. 29 (1995) 128–142.
B. M. Budak, E. M. Berkovich, and E. N. Solov’eva,
Difference approximations in optimal control problems.
SIAM J. Control 7 (1969) 18–31.
M. Carey, Optimal time-varying flows on congested networks. Oper. Res. 35 (1987) 58–69.
M. Carey and A. Srinivasan, Externalities, average and
marginal costs, and tolls on congested networks with
time-varying flows. Oper. Res. 41 (1993) 217–231.
J. Cullum, Discrete approximations to continuous optimal control problems. SIAM J. Control 7 (1969) 32–
49.
S. Dafermos and A. Nagurney, Oligopolistic and competitive behavior of spatially separated markets. Region.
Sci. Urban Econ. 17 (1987) 245–254.
G. Debreu and H. Scarf, A limit theorem on the core of
an economy. Int. Econ. Rev. 4 (1963) 235–246.
A. A. Economides, Dynamic competitive resource sharing in multimedia networks. Proceedings of the Seventh
International Symposium on Dynamic Games and Applications 1 (1996) 172–181.
T. L. Friesz, D. Bernstein, T. E. Smith, R. L. Tobin, and
B. W. Wie, A variational inequality formulation of the
dynamic network user equilibrium problem. Oper. Res.
41 (1993) 179–191.
T. L. Friesz, F. J. Luque, R. L. Tobin, and B. W. Wie,
Dynamic network traffic assignment considered as a continuous time optimal control problem. Oper. Res. 37
(1989) 893–901.
S. T. Glad, A combination of penalty function and multiplier methods for solving optimal control problems. J.
Optim. Theory Appl. 28 (1979) 303–329.
W: Networks
830
DYNAMIC NASH AND INSTANTANEOUS USER EQUILIBRIA
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[ 20]
[ 21]
[ 22]
[ 23]
[ 24]
[ 25]
[ 26]
8u27
A. Haurie and P. Marcotte, On the relationship between
Nash–Cournot and Wardrop equilibria. Networks 15
(1985) 295–308.
M. R. Hestenes, Multiplier and gradient methods. J. Optim. Theory Appl. 4 (1969) 303–320.
S. Jorgensen, Sufficiency and game structure in Nash
open-loop differential games. J. Optim. Theory Appl. 50
(1986) 189–193.
S. Lafortune, R. Sengupta, D. E. Kaufman, and R. L.
Smith, Dynamic system-optimal traffic assignment using
a state space model. Trans. Res. 27B (1993) 451–472.
L. S. Lasdon, S. K. Mitter, and A. D. Warren, The conjugate gradient method for optimal control problems. IEEE
Trans. Automat. Control 12 (1967) 132–138.
H. S. Mahmassani and S. Peeta, Network performance
under system optimal and user equilibrium dynamic assignments: Implications for AVIS. Trans. Res. Rec. 1408
(1993) 83–93.
D. K. Merchant and G. L. Nemhauser, A model and an
algorithm for the dynamic traffic assignment problems.
Trans. Sci. 12 (1976) 62–77.
D. K. Merchant and G. L. Nemhauser, Optimality conditions for a dynamic traffic assignment model. Trans. Sci.
12 (1976) 200–207.
B. Ran and D. E. Boyce, Modeling Dynamic Transportation Network: An Intelligent Transportation System Oriented Approach. Springer-Verlag, New York (1996).
B. Ran, D. E. Boyce, and L. J. LeBlanc, A new class
of instantaneous dynamic user optimal traffic assignment
models. Oper. Res. 41 (1993) 192–202.
J. F. Reinganum and N. L. Stokey, Oligopoly extraction
of a common property natural resource: The importance
of the period of commitment. Int. Econ. Rev. 26 (1985)
161–173.
A. Seierstad and K. Sydsaeter, Optimal Control Theory
with Economic Applications. North-Holland, New York
(1987).
H. Stalford and G. Leitmann, Sufficiency conditions for
Nash equilibria in N-person differential games. Topics in
Differential Games (A. Blaquiere, Ed.). North-Holland
(1973).
A. W. Starr and Y. C. Ho, Nonzero-sum differential
games. J. Optim. Theory Appl. 3 (1969) 184–206.
/ 8u27$$0830
07-29-98 20:42:01
netwa
[ 27]
[ 28]
[ 29]
[ 30]
[ 31]
[ 32]
[ 33]
[ 34]
[ 35]
[ 36]
[ 37]
[ 38]
[ 39]
163
J. M. Sussman, ITS: A short history and perspective on
the future. Trans. Q. 50 (1996) 115–125.
B. Tolwinski, On the existence of Nash equilibrium
points for differential games with linear and non-linear
dynamics. Control Cybernet. 7 (1978) 57–69.
S. S. Tripathi and K. S. Narendra, Constrained optimization problems using multiplier methods. J. Optim. Theory Appl. 9 (1972) 59–69.
J. G. Wardrop, Some theoretical aspects of road traffic
research. Proceedings, Institution of Civil Engineers II
(1952) 235–378.
D. Watling and T. von Vuren, The modelling of dynamic
route guidance systems. Trans. Res. 1C (1993) 159–
182.
B. W. Wie, Dynamic models of network traffic assignment: A control theoretic approach. Ph.D. Dissertation,
Department of City and Regional Planning, University
of Pennsylvania (1988).
B. W. Wie, A differential game model of Nash equilibrium on a congested traffic network. Networks 23 (1993)
557–565.
B. W. Wie, A differential game approach to the dynamic
mixed behavior traffic network equilibrium problem.
Eur. J. Oper. Res. 83 (1995) 117–136.
B. W. Wie, A differential game model of departure time
and route guidance on congested traffic networks. Presented at the 7th International Symposium on Dynamic
Games and Applications, Japan (Dec. 16–18, 1996).
B. W. Wie, T. L. Friesz, and R. L. Tobin, Dynamic user
optimal traffic assignment on congested multidestination
networks. Trans. Res. 24B (1990) 431–442.
B. W. Wie, R. L. Tobin, and T. L. Friesz, The augmented
Lagrangian method for solving dynamic network traffic
assignment models in discrete time. Trans. Sci. 28
(1994) 204–220.
B. W. Wie, R. L. Tobin, D. Bernstein, and T. L. Friesz,
A comparison of system optimum and user equilibrium
traffic assignments with schedule delays. Trans. Res. 3C
(1995) 389–411.
B. W. Wie, R. L. Tobin, T. L. Friesz, and D. Bernstein,
A discrete time, nested cost operator approach to the
dynamic network user equilibrium problem. Trans. Sci.
29 (1995) 79–92.
W: Networks
830
Документ
Категория
Без категории
Просмотров
3
Размер файла
378 Кб
Теги
extension, scheduling, lot, proportional, sizing
1/--страниц
Пожаловаться на содержимое документа