This paper develops node-based formulations for user equilibrium (UE) and system optimum (SO) dynamic trac assignment (DTA) problems with de- parture time choice and route choices for general multiple origin-destination networks. Both the formulations are embedded with a new cell transmis- sion model that satis es the link-level First-In-First-Out (FIFO) principle. Because the formulations are node-based, the need for path enumeration is obviated, which results in considerable computational eciency compared to the existing path-based models. While this advantage of node-based (or bush-based) models has been widely accepted in the literature of static traf- c assignment, the formulations of dynamic trac assignment models have mostly been path-based. The present work rst describes a node-based cell transmission model that satis es the link-level FIFO principle, which is t within a DTA framework that facilitates ecient computation of UE and SO solutions. Further contributions of the work include the introduction of a backpropagation algorithm to eciently compute marginal costs and com- plementarity formulations of the problems. Finally, numerical results are presented to demonstrate the performance of the proposed models using two standard test networks, along with a discussion of their convergence. Keywords: Bush-based, Cell transmission model, Dynamic trac Corresponding author 1Research Scholar, Department of Civil Engineering, Indian Institute of Science (IISc), Bangalore-560012, India. E-mail: mayakuntlasaikiran@gmail.com 2Associate Professor, Department of Civil Engineering and Center for Infrastructure, Sustainable Transport, and Urban Planning (CiSTUP), Indian Institute of Science (IISc), Bangalore-560012, India. E-mail: ashishv@iisc.ac.in Preprint submitted to Transportation Research Part B: Methodological August 23, 2019 assignment, Node-based, First-In-First-Out, User equilibrium, System optimum 1. Introduction There are broadly two types of dynamic trac assignment (DTA) prob- lems: (1) dynamic user equilibrium (DUE) and (2) dynamic system optimal (DSO). In a DUE, the individual travel costs of the drivers on the road net- work are minimized by their travel choices and they have no incentive to change them. By contrast, in a DSO, the travel choices are made such that the total travel cost of the system is minimised. The solutions to the two problems provide useful insights into the quality and eciency of transporta- tion networks, and they have been extensively studied not only as isolated problems (Merchant and Nemhauser, 1978; Ziliaskopoulos, 2000; Ramadu- rai et al., 2010), but as sub-problems within applications such as evacuation planning (Shen et al., 2006), congestion pricing (Arnott et al., 1993; Shen and Zhang, 2009), network design (Karoonsoontawong and Waller, 2010), etc. Any DTA model relies on a core module known as dynamic network load- ing (DNL), which includes rules for ow propagation, conservation and the estimation of travel times. Of the many such DNL models used in the past, cell transmission models (CTM) have been quite popular due to their ability to reproduce realistic, spatio-temporal phenomena like shockwave propaga- tion and queue spillbacks. CTMs are typically embedded within the DTA models and optimisation problems are formulated to obtain the user equilib- rium and system optimal solutions. Some such formulations have resulted in the violation of the rst-in- rst-out (FIFO) principle, which must be satis ed by any realistic trac ow model. It has also been observed that some of these models exhibit an arti cial holding back of the trac despite the avail- ability of space downstream (Doan and Ukkusuri, 2012). Some recent works have addressed both these issues by using CTM as an implicit simulation method and formulating the variational inequality (VI) based models for the DTA problems. These include Szeto and Lo (2004), where both the route and departure time choices are incorporated in the model for a general net- work with elastic demand. Similarly, Han et al. (2011) formulated the DUE problem within the framework of complementarity theory for a network with a single origin-destination (O-D) pair and multiple user classes with elastic 2 demand. This work is extended for multiple O-D pairs by Ukkusuri et al. (2012) with maximum and average travel time models and a heuristic solution procedure based on the projection algorithm from the VI theory. Recently, Doan and Ukkusuri (2015) developed a similar DSO formulation for general multi-OD networks with both route and departure time choices and they also provided an estimation procedure for path marginal costs that accu- rately captures the e ect of any perturbation on all other trac. However, all these models are path-based, i.e., the path choices are made by the trac at the time of their entry into the network, and it has been acknowledged that considerable computational complexity arises from the path enumera- tion (Doan and Ukkusuri, 2015). While it has long been accepted in the case of static trac assignment (STA) that node-based (or bush-based) models are computationally ecient than path-based ones and extensive literature is available on node- based STA models (Bar-Gera, 2002; Nie, 2010; Gentile, 2014), the same is surprisingly lacking in the case of DTA problems, possibly because of the diculty of tractable formulation of such models. The present work proposes node-based formulations for the DUE & DSO problems that incorporate many important features of the previous mod- els like multiple O-D pairs, departure time choices and route choices, while avoiding their drawbacks such as holding back problem and FIFO violation. Since the models are node-based, the route choices are determined by the turning choices made by the trac at diverging intersections, if and when they reach them. The CTM embedded within these formulations satis es FIFO level 3 (or) link-level FIFO, as de ned by Carey et al. (2014). While Carey et al. (2014) does provide algorithms for the implementation of such a CTM, an alternative implementation is devised in the present study to facili- tate various computations of the DTA problems, including a backpropagation algorithm that can calculate all the relevant marginal costs with about the same computational complexity as a single simulation run. The proofs of the solution existence and some of the solution procedures of the proposed formulations given here are based on the techniques introduced in the earlier studies by Han et al. (2011), Ukkusuri et al. (2012) and Doan and Ukkusuri (2015) In the following section, a Cell Transmission Model (CTM) is presented for a general network with demands between multiple O-D pairs incorporat- ing the departure time choices for each O- D pair and the time-dependent turning choices at each diverging intersection. Further, detailed algorithms are given for the ow computations at merging and diverging intersections. 3 This is followed by the derivation of recursive equations for average travel costs from the entrance of each link towards each destination and a back- propagation algorithm is described to calculate the marginal costs with re- spect to all the choice variables. Next, complementarity formulations are given for DUE and DSO problems and their solution existence are proven using complementarity and variational inequality theories. This is followed by the presentation of a solution algorithm that can be adapted for both the problems and a discussion of numerical experiments demonstrating the application of the proposed formulations. And the paper concludes with a brief summary of the present work and a note on the scope for further work. 2. Notation Indices i;j;k - Indices for cells s - Index for destination cells t;t0; ; 0- Indices for timesteps l;l0- Indices for links Parameters Tm - Maximum departure time T - Maximum time horizon Qi- Flow capacity into and out of cell i Ni- Jam density of cell i i- Congestion wave parameter of cell i ni - Number of cells between the cell iand the entry cell of the link it belongs to, inclusive of both s- Unit cost of travel time for trac destined to s s- Unit cost of early arrival for trac destined to s s- Unit cost of late arrival for trac destined to s ; - In nitesimal parameter used to create modi ed cumula- tive curves Di s - Total demand from a source cell ito a sink cell s M - Penalty value for the trac that fails to reach its destina- tion by the end of the simulation B - a value less than the minimum of the lower bounds of all the derivatives w.r.t. the choice variables  - Learning rate in the projection algorithm 4 Sets C - Set of all cells CO - Set of ordinary cells CR - Set of source cells CS - Set of sink cells CD - Set of diverging cells CM - Set of merging cells CJ - Set of all cells immediately downstream of a diverging cell, i.e.,fjj1 j\CD6=;g CK - Set of all cells immediately upstream of a merging cell, i.e.,fkjk\CM6=;g Cl - Set of all cells on link l L - Set of all links en(l) - Entry cell of link l ex(l) - Exit cell of link l i - Set of all immediate downstream cells of a cell i 1 i - Set of all immediate upstream cells of a cell i Xi - Set of all immediate downstream links of a link l X1 i - Set of all immediate upstream links of a link l Variables xi s;t - Occupancy of cell iat timetby the trac destined to sink cells yi;j s;t - Flow destined to the sink cell sfrom cellito celljat timet yi: s;t - Out ow from cell iof the trac destined to the sink cell sat timestep t y:i s;t - In ow from cell iof the trac destined to the sink cell s at timestep t yi: :t - Total out ow from cell iat timestep t y:i :t - Total in ow from cell iat timestep t yi;j s;t - Cumulative sum variable corresponding to yi;j s;t yi: s;t - Cumulative sum variable corresponding to yi: s;t y:i s;t - Cumulative sum variable corresponding to y:i s;t eyi: s;t - Auxiliary variable corresponding to  yi: s;t ey:i s;t - Auxiliary variable corresponding to  y:i s;t 5 ri s;t - Proportion of demand from the source cell ito destina- tion cellsthat enters the system at time t di;j s;t - Proportion of trac destined to s in a diverging cell iat timesteptthat chooses to move into an immediate down- stream cell j Al;i t - Time of entry into link lof the earliest vehicles exiting celliat timet al;i t - Time of exit from cell iof the earliest vehicles entering a linklat time zl;i ;t - Proportion of vehicles that enter a link lat timetand exit celliat time ^zl;i ;t - Auxiliary variable corresponding to zl;i ;t Zl: s; ;t - Proportion of trac destined to sthat enters the link lin timestep and exits in timestep t Zl;l0 s; ;t - Proportion of trac destined to sthat enters the link lin timestep and exits in timestep tto enter a downstream linkl0 pl s; ;t - Proportion of trac that enters the link lin timestep and reaches its destination in timestep t TTl s;t - Expected travel time of the trac destined to sthat en- ters the link lin timestep el s;t - Expected early arrival costs of the trac destined to s that enters the link lin timestep fl s;t - Expected late arrival costs of the trac destined to s that enters the link lin timestep TCl s;t - Expected travel cost of the trac destined to sthat en- ters the link lin timestep pi s - Equilibrium cost corresponding to the departure time choices at origin iin the DUE solution qi s;t - Equilibrium cost corresponding to the turning choices at diverging cell iin the DUE solution Pi s - Equilibrium cost corresponding to the departure time choices at origin iin the DSO solution Qi s;t - Equilibrium cost corresponding to the turning choices at diverging cell iin the DSO solution bPi s - Auxiliary variable corresponding to Pi s bQi s;t - Auxiliary variable corresponding to Qi s;t 6 TSC - Total system cost Some additional notation is used in section 5 to some background to the results presented, but since that notation is not used anywhere else in the paper, it is not de ned in this section. Nevertheless, it is clearly de ned at the location of its usage. 3. Cell transmission model Extensions of Cell transmission model (Daganzo, 1994, 1995) have been widely used as dynamic network loading (DNL) models because of their abil- ity to accurately capture spatio-temporal phenomena like shockwaves and queue spillbacks. Unless the overtaking behaviour is explicitly included, these models typically ensure FIFO behaviour, in order to avoid arbitrary, unreal- istic behaviour that could arise otherwise. Carey et al. (2014) de ned three levels of FIFO approximations and presented algorithms for CTMs that sat- isfy each of them. In this section, an alternative implementation of CTM that satis es FIFO level 3, i.e., link-level FIFO behavior, is presented. This will facilitate the computations performed to solve the node-based DTA prob- lems detailed in later sections. Given the departure time choices at each source and the turning choices at each diverging intersection, the CTM pre- sented in this section uniquely determines the cell ows and occupancies on a multiple O-D network for the time period considered. Vehicles are labelled by their destinations (or sink cells) and their paths are determined by the turning choices made at diverging intersections. This obviates the need to enumerate all the paths between each O-D pair, which signi cantly reduces the computational cost of the model. 3.1. Cell updates xi s;0= 0 8i2C;d2CS (1) xi s;t=xi s;t1yi: s;t1+y:i s;t18i2C;s2CS;t2f1;:::;Tg (2) yi: s;t=X j2iyi;j s;t 8i2CCS;s2CS;t2f1;:::;Tg(3) yi: s;t=X j21 iyi;j s;t 8i2CCR;s2CS;t2f1;:::;Tg(4) 7 Cell type No. of outgoing connectors (jij)No. of incom- ing connectors (j1 ij) Ordinary (CO) 1 1 Merging (CM) 1 >1 Diverging ( CD)>1 1 Sink (CS) 0 1 Source (CR) 1 0 Table 1: Possible cell types in the model yi: s;t= 0 8i2CS;s2CS;t2f1;:::;Tg (5) y:i s;t=ri s;tDi s 8i2CR;s2CS;t2f1;:::;Tg (6) xi :t=X s2CSxi s;t 8i2C;t2f1;:::;Tg (7) y:i :t=X s2CSy:i s;t 8i2C;t2f1;:::;Tg (8) yi: :t=X s2CSyi: s;t 8i2C;t2f1;:::;Tg (9) xi :t=xi :t1yi: :t1+y:i :t18i2C;t2f1;:::;Tg (10) The applicability of the above equations to a given cell in the cell trans- mission network depends on its type, as de ned in table 1. Cells with multiple incoming and outgoing connectors are disallowed in the present model, as is common in the existing CTM literature. Eqs. (1)-(6) give the basic cell update equations disaggregated by the vehicle destinations. Eq. (1) ensures that all cells are empty at the beginning of the simulation. Eq. (2) updates the destination-wise occupancies in each cell. Eqs. (3) & (5) and eqs. (4) & (6) provide the out ows and in ows, respectively, of all the cells in the network. Sink cells are assumed to have in nite store capacity and all the vehicles entering them remain there till the end of the simulation. Similarly, in ows to source cells depend on the departure time choices at those cells. Eqs. (7), (8) & (9) give the aggregated cell occupancies, in ows and out ows, respectively. And eq. (10) is the aggregate occupancy update equation that can be derived from the equations above it. It may be useful to clarify certain terms before moving further. Unlike some previous studies (Ukkusuri et al., 2012; Doan et al., 2015), the terms 8 \link" and \connector" have been used with two di erent meanings here. A \connector" refers to the abstract representation of the allowability of ow between any two given cells. There are three possible types of connectors in the present model: ordinary, which joins a cell with a single outgoing connector to another cell with a single incoming connector; merging, which joins a cell with a single outgoing connector to a merging cell; and diverging, which joins a diverging cell to another cell with a single incoming connector. A \link" can be de ned as a maximal contiguous sequence of cells joined by ordinary connectors. In the following subsection, ows on the three types of equations are computed here in a way that ensures the link-level FIFO is satis ability. 3.2. Flow computation In the implementation algorithm of FIFO level 3 described by Carey et al. (2014), vehicle cohorts are labelled by their route and time of entry into a given link, and the disaggregated cell updates are performed by keeping track of the position of these cohorts along the link. In contrast, labelling is done here by the vehicle destinations and their entry times and their disaggregation at each cell is performed using cumulative ows. However, as observed in Nie (2004), such usage of cumulative ows gives rise to diculties, as they are not strictly increasing and remain at at portions with zero ow. This could occur due to two major factors: (a) A temporary in ow drop to zero (e.g., during light trac), and (b) A temporary out ow capacity drop to zero (e.g., during a red phase). Nie (2004) circumvented this problem by estimating the link travel times in the zero- ow portions through the method of linear interpolation. Alternatively, Long et al. (2011) dealt with the same issue by adding small, non-zero values to the cumulative ows at every timestep and essentially forcing them to become strictly increasing. In the present work, a limit-based approach is used to derive conditional formulas that can determine the required values using non-decreasing cumulative ow curves. More speci cally, the cumulative entry ows to each link (eq. 11) and the cumulative exit ows out of each cell (eq. 12) are modi ed by adding a small, positive constant value ( >0) at each timestep and de ning some new terms as the limits of functions using these modi ed curves as the constant value approaches zero. ~y:en(l) :t = y:en(l) :t+ (t+ 1) (11) 9 Figure 1: Illustration of de nitions 1 & 2. Curves 1 & 2 represent the modi ed cumulative curves (eqs. 11-12) of the ows entering a given link land those exiting a cell ion that link, respectively. For trac ow satisfying FIFO level 3, the earliest (>0) vehicles exiting cell iat timetmust have entered the link at Al;i t, and the earliest 0(>0) vehicles entering the link at time must exit the cell iat timeal;i t. ~yi: :t=( yi: :t(= 0) if t<ni yi: :t+ (tni+ 1)o/w(12) De nition 1. The time of entry of the earliest vehicles exiting cell iat time tis given by: Al;i t=( 1 ift<ni lim!0+lim!0+maxn t0j~yi: :t1+>~y:en(l) :t01o o/w(13) To understand the above de nition, rst observe that niis the number of cells between the entry cell of link land celli, inclusive of both. Under free- ow conditions, the out ow from any given cell must be equal to its occupancy, as vehicles move at a speed of one cell per timestep, which makes nithe minimum number of timesteps in which a vehicle cohort entering a link lcan begin exiting cell i. Since the entire network is empty at the beginning of our simulation, there cannot be any out ow from cell ibeforeni, where a 10 value of -1 is assigned to indicate this. Further the modi cations made to the cumulative ows are equivalent to increasing all the relevant parameters of the cells, i.e., ow and storage capacities, and the demand from the incoming links by. In eq. (13), represents vehicles exiting cell iat the beginning of the timestep t. Figure 1 may further clarify the de nition. Proposition 1. Al;i t=( 1 ift<ni lim!0+maxn t0j~yi: :t1~y:en(l) :t01o o/w(14) Proof. This result can easily be veri ed using eq. (13). Proposition 2. 1.For all <tniand>0, (a) yi: :t>y:en(l) : )~yi: :t>~y:en(l) : (b) yi: :t= y:en(l) : )~yi: :t= ~y:en(l) : (c) yi: :t<y:en(l) : )~yi: :t<~y:en(l) : ;8<y:en(l) : yi: :t tni 2.For all =tniand>0, (a) yi: :t>y:en(l) : )~yi: :t>~y:en(l) : (b) yi: :t= y:en(l) : )~yi: :t= ~y:en(l) : (c) yi: :t<y:en(l) : )~yi: :t<~y:en(l) : 3.For all >tniand>0, (a) yi: :t= y:en(l) : )~yi: :t<~y:en(l) : (b) yi: :t<y:en(l) : )~yi: :t<~y:en(l) : (15) Proof. All the statements in eq. (15) can be veri ed using de nitions of the modi ed cumulative ows (eqs. (11) & (12)). Corollary 2.1. y:t i:y:tni :en(l);8i2Ci;l2L;t2fni;:::;T1g (16) Corollary 2.1 says that no vehicle entering a link later than tnican exit the cell ibeforet+ 1. 11 Corollary 2.2. ~y:t i:= ~y: :en(l), =tniandy:t i:= y: :en(l); 8i2Ci;l2L; 2f0;:::;T1g: (17) Proposition 3. Al;i ttni;8i2Cl;l2L;t2fni;:::;T1g (18) Proof. As we assumed that the cell network is empty at the beginning of the simulation (eq.1) and all non-sink cells must have a non-zero out ow capacity, the earliest vehicles entering the link lat timetmust move at their free- ow speed, making eq.(18) true at t=ni. Fort > ni, eq.(18) can be veri ed to be true using eqs.(13) & (15). Proposition 4. Al;i t=8 >< >:1; ift<ni; tni; iftniandyi: :t1= y:en(l) :tni1; maxt0jyi: :t1y:en(l) :tni1o=w; 8i2Cl;l2L;t2f0;:::;T1g (19) The proof of the above proposition can be found in appendix A. Next, an inverse notion to Al;i tis introduced that will be useful in later computations. De nition 2. al;i =8 >< >:lim!0+lim!0+maxf 0j~y:en(l) : 1+0>~yi: : 01g; if~y:en(l) : 1<~yi: :T1and <Tni T; o=w; 8i2Cl;l2L; 2f0;:::;T1g (20) The rst conditional is applicable to timesteps that do not entirely remain within the link lat the end of the simulation. A value of Tis assigned to al;i to the rest of the timesteps to indicate otherwise. 12 Proposition 5. al;i =8 >< >:lim!0+maxf 0j~y:en(l) : 1>~yi: : 01g; if~y:en(l) : 1<~yi: :T1and <Tni T; o=w; 8i2Cl;l2L; 2f0;:::;T1g (21) Proposition 6. al;i  +ni;8i2Cl;l2L; 2f0;:::;Tni1g (22) Proposition 7. al;i =8 >>>>>>< >>>>>>: +ni; ify:en(l) : 1= yi: : +ni1 and <Tni maxf 0j~y:en(l) : 1>~yi: : 01g;ifyi: : +ni16= y:en(l) : 1<yi: :T1 and <Tni T; o=w; 8i2Cl;l2L; 2f0;:::;T1g(23) The proofs of the propositions 5, 6 & 7 are similar to those of 1, 3 & 4, respectively. Both the notions introduced above are clearly related and, in fact, the values of al;i can directly be obtained using only Al;i tvalues, without using cumulative ows. Proposition 8. al;i =8 >< >: +ni; Al;i +ni= and <Tni minftj Al;i t+1g;9t2fni1;:::;T2gs:t: <Al;i +ni T; o=w; 8i2Cl;l2L; 2f0;:::;T1g(24) The proof of the above proposition can be found in appendix A. Corollary 8.1. al;i t>t>Al;i t;8i2Cl;l2L;t2f0;:::;T1g (25) 13 Proof. This result follows directly from eqs. (14), (18), (21) & (22). In a CTM satisfying FIFO level 3 (or) link-level FIFO, the vehicles exit each cell on the link in the same order as they entered it. But since the vehicles are only di erentiated by their destinations, satisfying the FIFO principle here means appropriately calculating the out ow proportion bound to destination. The most obvious way to do that is by using linear inter- polation as the out ow could be comprised of vehicles entering the link in multiple timesteps. To avoid introducing more cumbersome notation, an easily interpretable de nition of those proportions is given below as a limit function of modi ed cumulative ows and Al;i tvalues. Figure 2 provides an illustration of that de nition by considering two main cases. De nition 3. The proportion of vehicles that enter a link lat timetand exit celliat time is given by: zl;i ;t= lim !0+^zl;i ;t where ^zl;i ;t=8 >>>>>>>>>< >>>>>>>>>:0; if <Al;i tor >Al;i t+1 ~yi: :t~yi: :t1 ~y:en(l) : ~y:en(l) : 1;ifAl;i t= =Al;i t+1 ~y:en(l) : ~yi: :t1 ~y:en(l) : ~y:en(l) : 1;ifAl;i t= <Al;i t+1 1; ifAl;i t< <Al;i t+1 ~y:en(l) : ~yi: :t1 ~y:en(l) : ~y:en(l) : 1;ifAl;i t< =Al;i t+1(26) To understand the rst conditional in the above equation, note that, under link-level FIFO, the earliest vehicles exiting cell iat timethave entered the link later than implies that the entry cohort of has completely exited the cellibeforet. Similarly, if the earliest vehicles exiting cell iat timet+ 1 have entered the link earlier than , then the vehicles from must not have begun exiting cell ibeforet+ 1. Therefore, zl;i t; values must be zero for these two periods. The second conditional corresponds to a situation where all the vehicles exiting cell iat timethave come from the same entry cohort of , whereas the other three conditionals combinedly represent the case where the cohort exits in multiple timesteps. An analogous de nition could be given in terms of al;i values, but it is instead derived from eq. (26) to demonstrate their consistency. 14 (a) (b) Figure 2: Illustration of de nition 3 15 Proposition 9. ^zl;i ;tin eq.(26) can alternatively be given by: ^zl;i ;t=8 >>>>>>>>>< >>>>>>>>>:0; ift<al;i ort>al;i +1 1; ifal;i =t=al;i +1 ~y:en(l) : ~yi: :t1 ~y:en(l) : ~y:en(l) : 1;ifal;i =t<al;i +1 ~yi: :t~yi: :t1 ~y:en(l) : ~y:en(l) : 1;ifal;i <t<al;i +1 ~y:en(l) : ~yi: :t1 ~y:en(l) : ~y:en(l) : 1;ifal;i <t=al;i +1(27) Proof. It can be seen that each conditional in eq.(27) has a corresponding equivalent conditional in eq.(26), which is veri able using eq.(24). Proposition 10. X t2f0;:::;T1gzl;i ;t= 1, <Tniandal;i +1T1: (28) Proof. This can again be easily veri ed using eqs.(23) & (27). Proposition 11. X t02f0;:::;tgzl;i ;t0>0)X t02f0;:::;tgzl;i 1;t0= 1; 8t2f1;:::;T1g; 2f0;:::;tnig;l2L;i2Cl:(29) This proposition means that the vehicles entering a link at time 1 must have exited the cell ibefore the entry cohort of begins to exit. This can be derived using the eqs.(19) & (26). Flow computations on the three types of connectors, i.e., ordinary, diverging and merging, can be performed now according to the methods given in Carey et al. (2014), but with the terms de ned above. First, the aggregate ow from cell ito celljthrough an ordinary connector at timestep tis given by: yi;j :t= min(xi :t;Qi;Qj;j(Njxj :t))8(i;j)2EO;t2f0;:::;T1g(30) Similarly, at a merging intersection, the supply (or receiving capacity) of the merging cell is distributed among all its incoming cells based on some 16 yk;i :t 0;8k21 i V 1 i Sk minfxk :t;Qkg;Rk Qk P k02IQk0minfQi;i(Nixi :t)g;8k2V whileI6=;do U 0 fork2Ido ifSkRkthen yk;i :t yk;i :t+Sk;V Vfkg else yk;i :t yk;i :t+Rk;U U+SkRk end end fork2Ido Sk SkRk Rk Qk P k02IQk0U end end Algorithm 1: Computations at a merging intersection 17 xed proportions. In case the demand from an incoming cell is less than the supply allocated to it, the surplus is redistributed to the cells where the demand is greater. This iteration ends when either all the demands from the incoming cells are satis ed, or the supply is exhausted. Algorithm 1 is used to perform computations at each merging cell iat each timestep t. yi;j :t 0;8j2i h Al;ex(l) t Rj minfQj;j(Njxj :t)g;8j2i whileyi;j :t<Rj;8j2iandhAl;ex(l)1 t do f 8 >>>< >>>:y:ex(l)1 :t1y:ex(l) :t1;ifAl;ex(l) t =h=Al;ex(l)1 t y:en(l) :hy:ex(l) :t1; ifAl;ex(l) t =h<Al;ex(l)1 t y:en(l) :h; ifAl;ex(l) t<h<Al;ex(l)1 t y:ex(l)1 :t1y:ex(l) :t1;ifAl;ex(l) t =h<Al;ex(l)1 t fj 8 < :0; ify:en(l) :h = 0 fP s2CSy:en(l) s;h y:en(l) :hdi;j s;t;o/w yi;j :t ( yi;j :t+fj;ifyi;j :t+fjRj Rj; o/w h h+ 1 end Algorithm 2: Computations at a diverging intersection At any given timestep t, the proportion of in ow to each cell immedi- ately downstream to a diverging cell is calculated using its corresponding destination-based turning choices. The ow is calculated by considering the vehicle cohorts labeled by their entry times sequentially starting with the earliest vehicles remaining on link latt, until either the sending capacity of the diverging cell or one of the receiving capacities its downstream cells is exhausted. In the latter case, trac moving to the other downstream cells will be stuck behind that of the blocked one, which is a phenomenon often observed on real road intersections. Algorithm 2 gives all the computations performed at each diverging intersection at each timestep. 18 Now the disaggregate ows out of each cell iat any timestep tcan be given by: yi: s;t=tniX =0zl;i ;ty:en(l) s; ;8i2Cl;l2L;t2fni;:::;T1g (31) Since there is only one outgoing connector for all cells except the diverging type, yi;j s;t=yi: s;t;8i2CCD;j2i;s2CS;t2fni;:::;T1g (32) Note that this also applies to sink cells, which do not have any connectors and the out ows are zero. Further, it can be veri ed that the out ows from a diverging cell iare distributed as: yi;j s;t=di;j s;tyi: s;t;8i2CD;j2i;s2CS;t2fni;:::;T1g (33) Finally, the following proposition can be derived from eqs.(26) & (33). Proposition 12. yi;j s;t=8 >>>>>>>>< >>>>>>>>:lim!0+yi: :t+ y:en(l) :Al;i t+y:en(l) s;Al;i t; ifAl;i t=Al;i t+1 lim!0+~y:en(l) :Al;i t~yi: :t1 y:en(l) :Al;i t+y:en(l) s;Al;i t+PAl;i t+11 0=Al;i t+1y:en(l) s; 0 +~yi: :t~y:en(l) :Al;i t1 y:en(l) :Al;i t+y:en(l) s;Al;i t+1;o/w; 8i2Cl;l2L;s2CS;t2fni;:::;T1g(34) 4. Cost computations Several travel cost computation approaches have been proposed in earlier studies that range from the summation of travel costs of all the links on a path to its estimation using cumulative departures and cumulative arrivals at the origin and destination of a given path. However, since paths between each O-D pair are not enumerated in this study, the average travel costs entering each link at each time step are estimated here instead. In the following two 19 subsections, recursive formulations are given to compute the average travel costs from the entry of each link and the marginal system costs with respect to the choice variables (departure time and turns at the diverge intersections), both of which include travel time and schedule delay components. 4.1. Average travel costs (ATC) Without loss of generality, it is assumed here that all the ow capacities on a sink link are equal, and the storage capacities on all the non-sink links are equal. The storage capacity of a sink cell will, of course, be in nite. This guarantees that the sink links will always be under free- ow, as there is no possibility of congestion propagating from the downstream. This assumption is made only to make the representation of computations simpler, but the following methods should apply equally well for cases violating it. Now, the proportion of trac that enters a given link lat time and reaches its destination sat timetis given by pl s; ;l=8 >>>>< >>>>:1; ifs=ex(l) andt= +nex(l)1P 02f +1;:::;T1gzl;ex(l) ; 0pl0 s; 0; ; ifjXlj= 1 andl02Xl pP l02XlP 02f +1;:::;T1gzl;ex(l) ; 0dex(l);en(l0) s; 0pl0 s; 0; ;ifjXlj>1 0; o/w(35) Using eq.(37), the average travel time for trac entering link lat time and destined to sis given by: TTl s; =X t2f ;:::;T1gpl s; ;t(t ) + (1X t2f ;:::;T1gpl s; ;t)(M+T ) = (M+T ) +X t2f ;:::;T1gpl s; ;t(tMT) 8l2L;s2CS; 2f0;:::;T1g (36) Min the above equation is the penalty value assigned to vehicles that fail to reach their destinations before the end of simulation. Along with the average travel times, travels costs include average late arrival costs and early arrival costs, de ned as follows: 20 el s; =( 0; if ts P t2f ;:::;ts1gpl s; ;t(tst);o/w; 8l2L;s2CS; 2f0;:::;T1g fl s; =8 >>< >>:0; ifs2Cland ts P t2maxfts+1; g;:::;T1pl s; ;t(tts) + 1P t2maxfts+1; g;:::;T1pl s; ;t (M+Tts);o/w; 8l2L;s2CS; 2f0;:::;T1g The average travel costs are given by appropriately weighting the above three components as follows: TCl s; = sTTl s; + sel s; + l s; ;8l2L;s2CS; 2f0;:::;T1g(37) TTl s; =8 >>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>:nex(l)1; ifs=ex(l) and <Tnex(l) P 02f +1;:::;T1gzl;ex(l) ; 0(TTl0 s; 0+ 0 )+ 1P 02f +1;:::;T1gzl;ex(l) ; 0 (M+T ); ifjXlj= 1 andl02Xl P l02XlP 02f +1;:::;T1gzl;ex(l) ; 0dex(l);en(l0) s; 0 (TTl0 s; 0+ 0 ) + 1P 02f +1;:::;T1gzl;ex (l) ; 0 (M+T ); ifjXlj>1 T ; o/w (38) el s; =8 >>>>< >>>>:ts nex(l)+ 1; ifs=ex(l) and +nex(l)<ts P 02f +1;:::;T1gzl;ex(l) ; 0el0 s; 0; ifjXlj= 1 andl02XlP l02XlP 02f +1;:::;T1gzl;ex(l) ; 0dex(l);en(l0) s; 0el0 s; 0; ifjXlj>1; 0; o/w (39) 21 fl s; =8 >>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>: +nex(l)1ts; ifs=ex(l) and +nex(l)<ts P 02f +1;:::;T1gzl;ex(l) ; 0fl0 s; 0 + 1P 02f +1;:::;T1gzl;ex(l) ; 0 (M+Tts); ifjXlj= 1 andl02Xl P l02XlP 02f +1;:::;T1gzl;ex(l) ; 0dex(l);en(l) s; 0fl0 s; 0 + 1P 02f +1;:::;T1gzl;ex(l) ; 0 (M+Tts);ifjXlj>1 M+Tts; ifex(l)2CSands6=ex(l) 0; o/w (40) TCl s; =8 >>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>: s(nex(l)1) +1( +nex(l)<ts) s ts nex(l)+ 1 +1( +nex(l)>ts) s +nex(l)1ts ; ifs=ex(l) s(M+Tts) + s(M+T );ifs6=ex(l) andex(l)2CS P 02f +1;:::;T1gzl;ex(l) ; 0 TCl0 s; 0+ s( 0 ) + 1P 02f +1;:::;T1gzl;ex(l) ; 0 (( s+ s)(M+T)) ( sts+ s );ifjXlj= 1 andl02Xl P l02XlP 02f +1;:::;T1gzl;ex(l) ; 0dex(l);en(l) s; 0 TCl0 s; 0+ s( 0 ) + 1P 02f +1;:::;T1gzl;ex(l) ; 0 (( s+ s)(M+T)) ( sts+ s );ifjXlj>1 (41) 4.2. Total system cost (TSC) and marginal system costs (MSCs) While average travel costs are used for the calculation of the user equilib- rium, marginal costs are used to determine the system optimum assignment. 22 In this subsection, a formula for total system cost is given in terms of cell oc- cupancies and marginal costs are computed with respect to the occupancies using an ecient, backpropagation procedure. Finally, marginal costs w.r.t. all the choice variables are determined, which are, unlink the travel costs, dis- continuous. As will be seen in later sections, this should not pose a signi cant problem in their usage in determining the system optimum assignment. Since it is not possible to derive a simple formula for TSC without intro- ducing further cumbersome notation, only a sketch of the proof is provided here. But rst, for the purpose of clarity, the vehicles are divided into three types: (a) Those that reached their respective destinations before their target times, (b) Those that reached their destinations after their target times but before the end of the simulation and (c) those that failed to reach their desti- nations. Now, the value of TSC can be given in terms of the cell occupancies as follows: Proposition 13. TSC =X s2CSX i2CRX t2f0;:::;T1gy:i s;tTCi s;t =X s2CS2 4 st sX t=1xs s;t s8 < :T1X t=ts+1xs s;t(T1t s)xs s;T9 = ; +X i2CCS0 @X t2f0;:::;T1g sxi s;t+ ( sM+ s(M+Tt s))xi s;T1 A +X s02CS:s06=sxs s0;T(M+Tt s0)# (42) The rst expression of TSC as the sum of products of all in ows at source cells and their corresponding average travel costs should be clear from their de nitions. The second expression in terms of occupancy variables can be understood by considering its components, i.e., travel time component, schedule delay component and penalties, separately. Using the cell update equations (eqs. 1-10) and the ow computation equations (eqs. 11-36), the marginal costs of TSC w.r.t. each cell occupancy variable can be computed. Using a backpropagation technique to achieve this 23 means beginning with the occupancy variables at the end of simulation ( xi s;T) and providing recursive formulations corresponding to each type of cell. First, the partial derivatives of TSC w.r.t. each occupancy variable ( xi s;t) can be given as follows: @(TSC ) @xi s;t=8 >>>>>>>>< >>>>>>>>: s; ifi2CCSandt2f0;:::;T1g s; ifi=sandt2f0;:::;t sg  s; ifi=sandt2ft s+ 1;:::;T1g s(T1t s); ifi=sandt=T (M+Tt s0); ifs02CSands06=sandt=T ( sM+ s(M+Tt s));ifi2CCSandt=T (43) The marginal costs w.r.t. the occupancies of each ordinary cell that is not part of an intersection ( COCJCK) are given by: d(TSC ) dxi s; = s+d(TSC ) dxi s; +1+1(xi =yi: : ) d(TSC ) dxj s; +1d(TSC ) dxi s; +1! +1 y:i : =i(Nixi ) " iX s2CSgj s; +1d(TSC ) dxi s; +1d(TSC ) dxk s; +1# (44) wheregi s; =8 < :1; ify:Aen(l) s; = 0 y s;Aen(l) s; y :Aen(l) s; ;o/w. Note that the third component in the above equation cannot be active wheny:A:en(l) s; +1= 0 because that indicates a free- ow situation. Unlike the midsection ows, ows at intersections are calculated using algorithms, which makes the calculation of marginal costs w.r.t. all the relevant occupancies less straightforward. However, formulas for the same can still be derived by considering the possible cases exhaustively. Thus, the 24 marginal costs at a merging intersection can be given as follows: d(TSC ) dxi s; = s+d(TSC ) dxi s; +1+1(xi =yi: : ) d(TSC ) dxj s; +1d(TSC ) dxi s; +1! +1 y:i : =i(Nixi )" iX k02VQ0 kP k002VQk00X s2CSgj s; +1d(TSC ) dxi s; +1d(TSC ) dxk0 s; +1# (45) d(TSC ) dxk s; = s+d(TSC ) dxk s; +1+1(xk =yk: : )d(TSC ) dxi s; +1d(TSC ) dxk s; +1 +1 y:i : =i(Nixi )"X k02VQ0 kP k002VQk00X s2CSgj s; +1d(TSC ) dxi s; +1d(TSC ) dxk0 s; +1#) +1 y:i : =i(Nixi )" iX s2CSgj s; +1d(TSC ) dxi s; +1d(TSC ) dxk s; +1# (46) whereV=fkjk21 iandyk;i : 6= minfxk ;Qkgg;8i2CM;j2j;k2 1 i;s2CS; 2f0;:::;T1g. Similarly, the marginal costs at a diverging intersection can be calculated as follows: d(TSC ) dxi s; = s+d(TSC ) dxi s; +1+1(xi =yi: : )X j2idi;j s; d(TSC ) dxj s; +1d(TSC ) dxi s; +1! +1 y:i : =i(Nixi ) " iX s2CSgj s; +1d(TSC ) dxi s; +1d(TSC ) dxk s; +1# (47) d(TSC ) dxi s; = s+d(TSC ) dxi s; +1+1(xi =yi: : ) d(TSC ) dxj s; +1d(TSC ) dxi s; +1! +1 yi;j : =j(Njxj ) " jX s2CSgi s; +1X j02idi;j0 s; d(TSC ) dxj0 s; +1d(TSC ) dxi s; +1!# (48) 8i2CD;j2i;k21 i;s2CS; 2f0;:::;T1g: 25 And nally, the marginal costs w.r.t. the actual choice variables are given by: d(TSC ) ddi;j s; =yi: s; d(TSC ) dxj s; +1d(TSC ) dxi s; +1! ; 8i2CD;j2i;s2CS;t2f0;:::;T1g (49) d(TSC ) dri s; =( Di sd(TSC ) dxi s; +1;if Tm 0; o/w; 8i2CO;s2CS; 2f0;:::;T1g (50) 5. Problem formulations and their solution existence In this section, we propose complementarity formulations for both the DUE and DSO problems and show their equivalence to a nite-dimensional variational inequality (VI) and a generalized variational inequality (GVI), respectively. Their solution existence is then proven using some results from VI theory brie y reviewed below. For more details on VI theory, the readers may refer to Facchinei and Pang (2007). Ukkusuri et al. (2012) also presents a self-contained review of the following results. 5.1. Preliminaries Given a non-empty convex closed set KRnand set-valued map F: K!K, a GVI problem consists of nding a vector x2Ksuch that (yx)TF(x)0;8y2K: In the special case of Fbeing a continuous function, the above problem can be described as a nite-dimensional VI. Given below are two results regarding the solution existence of these problems that are relevant to the present study. Lemma 5.1. (Fang and Peterson, 1982) If K is a compact set, Fis a nonempty, compact, contractible and upper semicontinuous, then GVI (K;F) has a solution. Note that a convex set is always contractible. Lemma 5.2. (Facchinei and Pang, 2007) If the set Kis nonempty convex and convex, then the solution set of VI(K;F ), denoted by SOL (K;F )is nonempty and compact. In the following subsections, the above two lemmas are used to prove the solution existence properties of the proposed DSO and DUE problems. 26 5.2. Dynamic user equilibrium (DUE) The proposed model of DUE problem consists of three sets of comple- mentarity conditions: dynamic equilibrium conditions, demand satisfaction conditions, and diverge ow conservation constraints. Dynamic equilibrium conditions are obtained by applying the Wardrop's rst principle to both departure time choices and turning choices, and they ensure that the ex- pected travel cost associated with every choice variable with positive value is minimal. 06ri s;t?TCi s;tpi s>08i2CR;s2CS;t2f0;:::;Tf1g (51) 06di;j s;t?TCj s;tqi s;t>08i2CD;j2i;s2CS;t2f0;:::;T1g(52) Further, the following two sets of conditions relating to departure time choices and turning choices, respectively, ensure that all the demands depart from their respective origins before Tfand the ows are conserved at the diverging intersections. 06pi s?X t2f0;:::;Tf1gri s;t1>08i2CR;s2CS (53) 06qi s;t?X j2idi;j s;t1>08i2CD;s2CS;t2f0;:::;T1g(54) To prove the solution existence of the above formulation, let us rst de ne: r, ri s;t i2CR;s2CS;t2f0;:::;T1g(55) d, di;j s;t i2CD;j2i;s2CS;t2f0;:::;T1g(56) TC, TCi s;t i2C;s2CS;t2f0;:::;T1g(57) C, TCi s;t i2CRSCD;s2CS;t2f0;:::;T1g(58) p, pi s i2CR;s2CS;t2f0;:::;T1g(59) q, qi;j s;t i2CD;j2i;s2CS;t2f0;:::;T1g(60) By noting that all the calculations leading to C(r;d) preserve the con- tinuity property, it is easy to prove the following lemma. Lemma 5.3. The function C(r;d)is continuous in ( r,d). 27 Now let us de ne ,(~r;~d); where ~r>0 ~d>0X t2f0;:::;Tf1g~ri s;t= 18i2CR;s2CS X j2i~di;j s;t= 18i2CD;s2CS;t2f0;:::;T1g It can now be claimed that the complementarity formulation given by eqs. (51)-(54) is equivalent to VI( ;C). The proof of the following lemma is similar to that of Lemma 3.4 of Ukkusuri et al. (2012), except for the notations. Lemma 5.4. (r;d;p;q)is a solution of the complementarity problem (eqs. 51- 54) if and only if it is a solution to VI( ;C). Due to Lemma 5.1, the solution to VI( ;C) exists, and it must also be a solution to the above complementarity problem. Theorem 5.5. The complementarity problem described by eqs.(51)-(54) has a solution. 5.3. Dynamic system optimum (DSO) Unlike the previous case, DSO problem can be described as a tractable optimization problem with TSC as the objective function and constraints on departure time choices and turning choices to ensure demand satisfaction and diverge ow conservation. minimize TSCX t2f0;:::;Tf1gri s;t= 18i2CR;s2CS X j2idi;j s;t= 18i2CD;s2CS;t2f0;:::;T1g 28 ri s;t>08i2CR;s2CS;t2f0;:::;Tf1g di;j s;t>08i02CD;j2i;s2CS;t2f0;:::;T1g For the sake of later computations, the occupancy variable-based expres- sion ofTSC is used in the above problem, which obviates the need to include travel cost equations in the formulation. Applying the rst-order condition to the Lagrangian function of the above problem gives: ri s;tdTSC dri s;tPi s = 08i2CR;s2CS;t2f0;:::;Tf1g (61) dTSC dri s;tPi s >08i2CR;s2CS;t2f0;:::;Tf1g (62) di;j s;t dTSC ddi;j s;tQi;j s! = 08i2CD;j2i;s2CS;t2f0;:::;T1g(63) dTSC ddi;j s;tQi;j s! >08i2CD;j2i;s2CS;t2f0;:::;T1g(64) X t2f0;:::;Tf1gri s;t= 18i2CR;s2CS (65) X j2idi;j s;t= 18i2CD;s2CS;t2f0;:::;T1g (66) ri s;t>08i2CR;s2CS;t2f0;:::;Tf1g (67) di;j s;t>08i2CD;j2i;s2CS;t2f0;:::;T1g(68) Lemma 5.6. The rst derivative of TSC w.r.t. each of the choice variables is bounded. Proof. From eqs.(49) & (50), it should be clear that the lemma can be proven by showing that the rst derivatives of TSC w.r.t. the occupancy variables are bounded. Note also that the boundedness is preserved by eqs.(44)-(48). This implies that when the derivatives w.r.t. occupancy variables at 0 < < Tare bounded, the same is true for those at 1. But the derivatives at =Tgiven by eq.(43) are bounded. Since the simulation is run for only a nite number of timesteps, all the derivatives of TSC must be bounded. LetBbe a value less than the minimum of the lower bounds of all the 29 derivatives w.r.t. the choice variables. The complementarity formulation of the DSO problem can now be given as follows. 06ri s;t?dTSC dri s;tBbPi s>08i2CR;s2CS;t2f0;:::;Tf1g (69) 06di;j s;t?dTSC ddi;j s;tBbQi s;t>08i2CD;j2i;s2CS;t2f0;:::;T1g (70) 06bPi s?X t2f0;:::;Tf1gri s;t1>08i2CR;s2CS (71) 06bQi s;t?X j2idi;j s;t1>08i2CD;s2CS;t2f0;:::;T1g(72) where bPi s=Pi sB8i2CR;s2CS;t20;:::;T1 bQi s;t=Qi s;tB8i2CD;s2CS;t20;:::;T1 This formulation allows us to prove its equivalence with a GVI problem, similar to lemma 5.4. And the following solution existence theorem of the DSO problem can be proven using lemma 5.1. Theorem 5.7. The complementarity problem described by eqs.(69)-(72) has a solution. 5.4. Discussion on the choice of penalty travel times In addition to the schedule delay and travel time costs, the proposed models include a dummy penalty travel time to ensure that the vehicles reach their respective destinations by the end of the simulation period. Assuming that this can be achieved for a given DTA problem by a non-empty set of choice variable combinations, a large penalty value increases the likelihood of the solution belonging to such a set. To see this, note that the minimal, equilibrium costs corresponding to both DUE and DSO solutions are made up of both penalty and non-penalty components. As the penalty travel time increases, the solutions will have fewer vehicles imposed it on them. This 30 should be true as long as not every single choice has the same proportion of vehicles failing to reach their destination, which is very unlikely due to the inherent asymmetry of the problem. It may be helpful to note here that, due to the FIFO satisfaction of the proposed models, the DUE problem may require a shorter penalty value than DSO. In the next section, where a penalty travel time of 10 times the simulation time is used, almost none of the experiments have led to solution where some vehicles fail to reach their destinations. 6. Solution algorithm and numerical results 6.1. Projection algorithm The solution algorithm used in the present work for both the problems described in the previous section is developed by Ukkusuri et al. (2012) based on a classical approach to solve GVI problems. Only the algorithm is pre- sented here and the interested readers may refer to this earlier work for more details. 1. Setk= 0. Initialize the departure time choice and turning choices with some feasible values ( r0;d0). 2. Run the simulation and compute CTM (rk;dk) andC(rk;dk). 3. Solve the quadratic program: z=argminjjz (rk;dk)C(rk;dk) jj2. 4. Ifjjzrkjj< , terminate the algorithm with r=z. Otherwise, rk+1=z;k=k+ 1 and go to step 1. The costsC(rk;dk) used in the above algorithm are average travel costs in the case of the UE problem and marginal costs divided by the average demand per O-D pair in the case of the SO problem. The scaling of the marginal costs could be avoided by choosing an appropriate learning rate but is made to keep all the costs in the later experiments within similar ranges to facilitate their comparisons. Also, note that is the learning rate parameter whose choice a ects the speed and accuracy of the solution. A detailed discussion of this issue can be found in the numerical results section. Note that the proposed models involve multiple sets of proportion variables in terms of which both the objective function and the constraints are separable in the algorithm. Therefore, it may be more ecient in terms of both memory and time to solve the quadratic program in each iteration separately for each set of proportion variables. 31 6.2. Numerical results In this section, the proposed models and algorithms are applied to two standard test networks: the rst one ( g. 3a), originally used in Ziliaskopou- los (2000), has 10 cells, two diverging sections and a single O-D pair (1-10), and the second one ( g. 3b), originally given in Nguyen and Dupuis (1984), has 57 cells, eight diverging intersections and four O-D pairs (1-48; 1-57; 14-48; 14-57). Unlike in the previous studies, no prede ned paths are used in the experiments. The cell length in both the cases is 0.5 miles, and the free- ow speed and congestion wave factor of the vehicle type are 30 mph and 0.8, respectively. All the roads have three lanes, and their jam density and ow capacity are 160 vehicles/mile/lane and 24 vehicles/minute/lane, respectively. For simplicity, the same travel cost factors are used for all sinks ( s=1; s=0.5; s=2). For Ziliaskopoulos' network, the target time, maximum departure time and maximum time horizon are 110, 160 and 170, respectively; whereas the same for the Nguyen-Dupuis' network are 60, 80 and 132, respectively. The experiments were conducted by varying total demands between each O-D pair (450, 900, 1350, 1800) and learning rates in the projection algorithm (0.01, 0.001, 0.0001). The convergence of the algorithms is observed using the following measures: (a) The norm of the di erence between two consecutive departure time choice variable solutions ( jjrjj2). (b) The norm of the di erence between two consecutive turning choice vari- able solutions, averaged across all the diverging intersections ( jjdjj2). (c) A relative gap measure corresponding to the departure time choice vari- ables given by: g1=1 jCOjjCSjX fi;lji2CO;en(l)=igX s2CSP t2f0;:::;Tm1g(ri s;tCl s;tCls) Cl s+ whereCl s= min t2f0;:::;Tm1gCl s;t:(73) (d) A relative gap measure corresponding to the turning choice variables given by: g2=1 jCDjX i2CDP s2CSP t2f0;:::;T1gP j2i di;j s;tCi;j s;tCi s;t P s2CSP t2f0;:::;T1gCi s;t+ whereCi s;t= min j2iCi;j s;t(74) 32 (a) (b) Figure 3: Test networks: (a) Ziliaskopoulos' network, (b) Nguyen-Dupuis' network 33 The relevant average travel costs ( TCl s;t) and marginal costs scaled with the mean demand (dTSC dri s;t=Dmean anddTSC ddi;j s;t=Dmean) take the place of the above cost variables for the UE & SO problems, respectively. Since the latter has a clearly de ned and eciently computable objective function, its value could be used as an additional performance indicator. But to make the comparison across di erent demand levels, the average travel cost is used here instead. 6.2.1. Discussion of the results The following strategy is chosen for the initialisation of the variables after conducting several experiments: all the trac between each O-D pair is departed at the maximum departure time, and the turning choices at the diverging intersections are made towards the link with the least free- ow travel cost. Figures (4)-(6) present the results of the experiments conducted at di erent demand levels and learning rates. All the axes in the gures are clipped for the sake of clarity, but in almost all the cases, this has only a ected the visibility of the values in the initial iterations. All the results in gure 4 conform to a common observation made regard- ing the convergence of optimisation algorithms with a learning rate param- eter: large learning rates converge faster but only to a suboptimal solution, whereas smaller learning rates usually give better solutions but with slower convergence. All the values of measures (b) and (d) in gure 4a are zero, indicating that the initial turning choices remain optimal throughout the it- eration. On the other hand, a learning rate of 1e-2 induces periodicity to the measures in many cases, which could be attributed to rapid shifting of trac to a new choice leading to a sharp increase in its associated cost and a sharp decrease in the cost of the starting choice. This may lead to the traf- c oscillating between two di erent portions of the choices as the iterations continue. Overall, the learning rate of 1e-3 seems to largely avoid both the problems arriving at a nearly optimal solution quickly and avoiding rapid shifting of the trac to new choices. The DSO results shown in gure 5 are similar, but many of the measures seem relatively more volatile and do not display the same level of convergence as the DUE results ( gure 4). Fortunately, their volatility decreases with the learning rates and it can be observed gure 6 that optimal solutions can be obtained with small enough learning rates. It also indicates an inverse relationship between the optimal learning rate and demand per O-D pair. Also, a phenomenon of sharp drops and rises in the average travel cost is 34 (a) (b) Figure 4: Values of the convergence measures for the rst 50 iterations of the user equi- librium algorithm at a demand per O-D pair of 1800 vehicles with (a) Ziliaskopoulos' network; (b) Nguyen-Dupuis' network. All the x-axes of the subplots indicate iteration number and y-axes indicate measure value. 35 (a) (b) Figure 5: Values of the convergence measures for the rst 50 iterations of the system optimum algorithm at a demand per O-D pair of 1800 vehicles with (a) Ziliaskopoulos' network; (b) Nguyen-Dupuis' network. All the x-axes of the subplots indicate iteration number and y-axes indicate measure value. 36 (a) (b) Figure 6: Average travel costs for the rst 100 iterations of the system optimum algorithm at di erent demand levels for (a) Ziliaskopoulos' network; (b) Nguyen-Dupuis' network. All the x-axes of the subplots indicate iteration number and y-axes indicate measure value. 37 Task Ziliaskopoulos' networkNguyen-Dupuis' network Initialization 0.00 0.0025 Simulation 0.31 1.01 Calculation of av- erage travel costs0.03 0.11 Calculation of marginal costs0.13 0.55 DUE quadratic program0.092 0.48 DSO quadratic program0.095 0.53 Table 2: Comparison of the average running time (in seconds) of the subtasks in the proposed algorithms observed in the DSO results and is especially pronounced for smaller demand levels. But the overall trend in all the results is satisfactorily converging towards an optimal solution. 6.2.2. Running times of the algorithms Table 2 compares the running times (in seconds) of di erent subtasks in the proposed algorithms for the two example networks. The simulation code is written in Python programming language using Numpy and Scipy packages and all the simulations were run on a 64-bit Intel Core i5-6500 3.2 GHz Quad-Core processor. For the purpose of comparison, the total demand between each O-D pair in both the networks is assumed to be 1800 vehicles. Each iteration takes less than 1 second in the case of Ziliaskopoulos network and a little more than 2 seconds is needed for Nguyen-Dupuis network. The complexity of the network and the demand level a ect the number of iter- ations taken by the algorithm to converge, thereby increasing the running time. 7. Conclusion and future work This paper formulates user equilibrium and system optimum problems within a generalised node-based DTA framework with an embedded cell 38 transmission model for a trac network with multiple origin-destination pairs. Both departure time choices at each origin and turning choices at each diverging intersection are incorporated in the models. Since the frame- work is node-based, the enumeration of paths is avoided and the eciency of the solution algorithms is signi cantly improved. The contributions made by the present work can be listed as follows: Proposal of a node-based cell transmission model that satis es the FIFO principle at link-level, i.e., the vehicles exit any given link in the same order as they entered it. Embedding the proposed CTM in a complementarity formulation for user equilibrium DTA with simultaneous departure time and route choices. Since the model is node-based, the route choice is made collec- tively by the individual turning choices of the trac at the diverging intersections. Embedding of the proposed CTM in a complementarity formulation of node-based system optimum DTA model with simultaneous departure time and route choices. Development of a time-dependent shortest path algorithm to eciently compute average travel costs, which includes travel time and schedule delay components. Development of an ecient, backpropagation algorithm to compute marginal costs with travel time and schedule delay components. Adaptation of the projection algorithm to solve the two problems and a discussion of their results. Simplifying assumptions have been made at di erent points in the pro- posed models and their realism can be improved in the future by modifying them appropriately. For example, the real trac networks can be too com- plicated to be fully represented by the types of intersections possible in the CTM. And the computation techniques developed in this paper are fairly generalisable to any new and improved CTMs. In addition, the proposed models could be used in the standard transportation network problems like trac signal optimisation, congestion pricing, etc. As both DUE and DSO 39 models share a similar framework, they could be used in studying the net- work eciency problem and developing mechanism design tools improve the performance of a given network. 8. Code availability All the relevant codes (Python codes of the proposed DUE and DSO models along with the details of the benchmark networks) are available via the GitHub repository of the primary author https://github.com/ SaiKiran92/Dynamic-traffic-assignment-node-based-with-CTM