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

1/--страниц