Dynamic, Integrated Model System: Sacramento-Area Application, Volume 2: Network Report (2014)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

5The DynusT DTA Model DynusT (Dynamic Urban Systems in Transportation) is a model system that is designed and implemented to perform simulation-based DTA and associated analysis. Due to its unique algorithmic structure and software implementation, it is capable of performing DTA on regional-level networks over a long simulation period. This makes DynusT particu- larly well-suited for regional-level modeling such as regional transportation planning, corridor studies, integration with activity-based models, and mass evacuation modeling. The purpose of this chapter is to present an overview of the theo- retical and algorithmic innovations in DynusT. As shown in Figure 2.1, DynusT consists of two main mod- ules: traffic simulation and traffic assignment. Vehicles are created and loaded into the network based on their respective origins and follow a specific route to their intended destina- tions. The large-scale simulation of network-wide traffic is accomplished through the mesoscopic simulation approach that omits inter-vehicle car-following details while maintain- ing realistic macroscopic traffic properties (e.g., speed, density, and flow). More specifically, the traffic simulation is based on the Anisotropic Mesoscopic Simulation (AMS) (Chiu et al. 2010) technique that calculates a vehicle’s speed from the traf- fic conditions ahead of the vehicle. Specifically, at each simula- tion interval, a vehicle’s speed is determined by a speed–density curve, the density being the number of vehicles per mile per lane within a limited forward distance designated as SIR (speed- influencing region). What is referred to as the traffic assignment module of DynusT consists of two algorithmic components: a time-dependent shortest path (TDSP) algorithm and a time-dependent traffic assignment, or routing. The TDSP algorithm determines the TDSP for each origin, destination, and departure time, and the traffic assignment component selects a route for each driver following some heuristic rules that are proven to lead to approximate user equilibrium, a condition in which each driver has selected the least-cost path available to him. In DynusT, the assignment algorithm maintains the balance of computational efficiency and solution algorithm quality. Innovations in computational efficiency allow DynusT to per- form 24-h assignment, which is a requirement for ABM and DTA integration. After shortest paths have been calculated and a route choice has been made, all the vehicles are simulated. DynusT uses the time gap between a vehicle’s simulated travel time and the vehicle’s available shortest path time to assess the level of con- vergence. If the average time gap for all the vehicles in the simulation is small enough (usually 1% to 2%), DynusT ter- minates and outputs network-wide LOS measures; otherwise, it continues iterating between its two models until convergence is achieved. The rest of this chapter is structured as follows: the first section presents the AMS model that powers the traffic simu- lation component of DynusT, and the second section dis- cusses the traffic assignment algorithm that is deployed to achieve convergence. Anisotropic Mesoscopic Simulation Model The AMS model was based on research published by Chiu et al. (2010) and developed based on two empirical traffic rules: (1) At any time, a vehicle’s prevailing speed is influenced only by the vehicles in front of it, including those that are in the adjacent lanes, and (2) the influence of downstream traffic decreases with increasing distance. These two characteristics define the anisotropic property of the traffic flow and provide the guiding principle for AMS model design. Based on the above, for any vehicle i, only the downstream vehicles within a certain distance influence vehicle i’s speed. This is a similar con- cept to a stimulus-response type of car-following model, with the distinction that in AMS, the stimulus of a vehicle’s speed response is represented in a macroscopic manner instead of using intervehicle distance or speed as in microscopic models. C h A p t e r 2

6For modeling purposes, the SIR for vehicle i (SIRi) is defined as vehicle i’s immediate downstream roadway section in which the stimulus is significant enough to influence vehicle i’s speed response. This concept is further depicted in Figure 2.2, AMS model concept, in which a multilane homogeneous roadway segment is considered. The SIR for vehicle i is defined as the area (including the lane in which vehicles reside and all the adjacent lanes) in front of vehicle i, where the traffic condition (represented by the density) affects vehicle i’s speed response. At each simulation clock tick, vehicle i’s speed is influenced by the density in the SIR. The upstream traffic and downstream traffic outside the SIR does not influence vehicle i. The traffic density in SIRi, denoted as ki, is calculated as the number of vehicles present in SIRi divided by the total lane-miles of the SIRi. As such, the unit of ki becomes the number of vehicles per mile per lane. At the beginning of a simulation interval t, the prevailing speed of vehicle i during the simulation interval t is determined by Equation 2.1, which is a non-increasing speed–density rela- tionship function with the following properties: density does not influence speed up to a certain density threshold and, for density greater than the threshold, value increases in density result in decreases in speed. The maximum density in DynusT is the “bumper-to-bumper” density observed in a long, standing-still queue. The algorithmic steps of an AMS model during simulation are as follows: At each clock tick t (the beginning of a simula- tion interval), each vehicle’s speed is evaluated based on its SIR density, which is obtained from the previous clock tick t - 1 through the speed–density (v-k) relationship of Equation 2.1. The SIR density is calculated based on Equation 2.2 or Equa- tion 2.3, depending on whether the SIR spans over a roadway segment with a different capacity. If the SIR spans a hetero- geneous highway section, Equation 2.2 applies; otherwise, the relationship is simplified to Equation 2.3. Vehicle i’s travel- ing distance at the end of the current simulation interval is obtained by multiplying the prevailing speed with the dura- tion of the simulation interval. ( )=℘ −v kit it (2.1)1 ( )= + −     − − − − k k N mx n l x i t queue i t i t i t min , (2.2)1 1 1 1 min , (2.3)1 1 k k N nl i t queue i t =     − − i = Subscript denoting a vehicle. The index i decreases with vehicles traveling in the same direction on the same link, t = Superscript denoting a simulation interval, n = Number of lanes downstream of lane add/drop, m = Number of lanes upstream of lane add/drop, l = SIR length, vti = Prevailing speed of vehicle i during simula- tion interval t, xit-1 = Distance between vehicle i and lane-drop (open) at clock tick t - 1, kit-1 = Density of the SIR for vehicle i, Nit-1 = Number of vehicles present in SIR, excluding vehicle i, vf = Free-flow speed in the speed–density relation- ship, ℘ : k → v = Non-increasing speed–density function speci- fying the v-k relationship, where ℘(0) = vf and ℘(kqueue) = 0, and kqueue = Queue density, ℘(kqueue) = 0. During the AMS simulation, each vehicle maintains its own desired speed and SIR. Individual vehicles’ traveling distances are therefore likely to differ, even though they are on the same link. This feature is different from certain previous models Method of Isochronal Vehicle Assignment Epoch k Traffic Assignment Time-Dependent Shortest-Path Algorithm Gap Function Vehicle Based Traffic Assignment Algorithm k = k + 1 Stop All Epochs Assigned?No Assignment Converged? No Iteration n Traffic Simulation Generated Vehicles with Assigned Attributes Anisotropic Mesoscopic Simulation (AMS) Information Strategy Initial Path Time-dependent OD, network Initial/Intermediate Vehicle Paths Model MoEs Evacuation Time, Exposure Level, Casualty, etc. n = n + 1 Yes Figure 2.1. Traffic simulation, assignment, and link volume estimation framework in DynusT.

7 (Jayakrishnan et al. 1994, Balakrishna et al. 2005), in which all moving vehicles on the same link travel at the same speed. This characterizes the AMS model as a vehicle-based meso- scopic model having a greater degree of resemblance with car- following–based microscopic models. The major difference between AMS and car-following models is that in AMS, a vehicle’s speed adjustment at each simulation time interval is governed by the SIR density, which is a macroscopic measure of all the vehicles present in the SIR, instead of an intervehicle measure between the target vehicle and the leading vehicle(s). Since the SIR moves with each vehicle during simulation, it can be anticipated that in the AMS model, the vehicle advancing mechanism is generally independent of the math- ematical representation of the roadway network (size/length of cell/segment/link). AMS simulation results generally remain stable regardless of whether link lengths are shorter than the simulation interval multiplied by the speed. AMS handles queue formation/discharge in a natural and straightforward manner. When the maximum value of (kqueue) is reached, vehicles get zero speed: v = ℘(kqueue) = 0. When density in the SIR region decreases, affected vehicles speed up. This mechanism allows for clear representations of substantial or transient queue formation or discharge. When a free-moving vehicle approaches the end of a queue, its speed gradually approaches the speed of the vehicles at the queue’s tail. Equation 2.1 is further extended to simulate traffic flow in uninterrupted flow facilities under various configura- tions, such as homogeneous highways, non-homogeneous l m lanes n lanesVehicle i (c) Non-Homogeneous Highway (bottleneck discharge) l-xx l-x l x m lanes n lanesVehicle i (b-1) Non-Homogeneous Highway (lane drop) n lanes l-x l x m lanes Vehicle i (b-2) Non-Homogeneous Highway (point bottleneck) l n lanesVehicle i Speed Influence Region SIRi (a) Homogeneous Highway Vehicle i (d) AMS with SIR extending beyond current link boundary 0 Figure 2.2. AMS model concept.

8highways, and temporary blockage, by incorporating differ- ent SIR and density kti calculations. In the case of homoge- neous highways, kti is calculated as the number of vehicles present in the SIR divided by the total lane-miles of the SIR (Equation 2.2). When lane drops or lane additions occur within the SIR, the total lane-miles of SIR is the sum of lane- miles of separate sections, as shown in Equation 2.3 and depicted in Figure 2.2, AMS model concept (where m = the number of lanes at the beginning of the section and n = the number of lanes at the end of the section). In the case of a lane drop or a point bottleneck (n < m), the SIR density of a vehicle gradually increases (and, hence, speed reduces) as it approaches the bottleneck. When n = 0, a complete blockage occurs; this can be applied to either the point blockage or red-light signal indication. On the other hand, in the case of discharging from a bottleneck, as a vehi- cle approaching the open-up of the bottleneck, the density reduces and speed increases gradually. In this project, the speed–density function takes the follow- ing two Greenshield types of function forms. v v k k v k k k k k cal f b f b q b = ≤ − − −           , ,1 β α b qk k≤ ≤      ( . )2 4 v v k k v k k k k k k cal f b f b q b b = ≤ − − −         ≤ , ,1 α ≤     kq ( . )2 5 Gap Function Vehicle-Based traffic Assignment In the assignment, the proposed gap function vehicle-based (GFV) algorithm adopts a gradient projection concept, where path flow updates are composed of both a gradient and a step size. The algorithm also takes advantage of the vehicle-based simulation, allowing reassigned selected individual vehicles with better paths to improve their travel times. The gradient projection approach is common in constrained nonlinear programming and has been applied in many classical static and DTA works (Dafermos and Sparrow 1969; Florian and Nguyen 1974; Sheffi 1985; Smith 1993). The route-swapping heuristics developed in more recent years have been found to be related to the same concept, except that in the route- swapping heuristics the step size is usually a pre-determined swapping rate, and the direction is linearly proportional to the travel time difference between the current vehicle travel time and the shortest path travel time (Smith and Wisten 1995; Huang and Lam 2002; Szeto and Lo 2006). In a more recent study the swapping rate was proposed to be the ratio of the difference of the individual path travel time to the shortest path travel time (Lu 2007; Lu et al. 2008a). In the GFV method used in the SHRP 2 C10B model, the step size is in relation to the relative gap value calculated for all the paths between each origin–destination–departure time (i, j, t) triplet at iteration l. Similar in concept to prior studies, the GFV method leads to a smaller step size with a smaller rela- tive gap value. The gradient determines the search direction, where “search direction” means those paths to be updated with more or fewer vehicles. For each (i, j, t) triplet, paths are sorted according to the average travel time, and vehicles trav- eling on each path are also sorted according to decreasing experienced travel time. Note that the assignment interval is normally much longer than the simulation interval. There- fore, vehicles departing within the same assignment interval, while subject to the same path set, would experience different travel times due to their different departure times during the simulation interval. Furthermore, at each iteration, once the assignment is com- pleted, the path set Kl+1 (i, j, t) ∀ all (i, j, t) is released from memory. At the beginning of each iteration, the path set is reconstructed by scanning through each vehicle and assigned path. This may cause a slight increase in computation, but it eliminates the need to retain the path set K l+1 (i, j, t) ∀ all (i, j, t) when such information is not used (e.g., in simula- tion), thus reducing the peak memory needed during the entire simulation-assignment procedure. It should also be noted that this strategy is likely to deplete high-travel-time paths of vehi- cles. As a result, such paths will not appear in the next iteration path set. Different from methods that explicitly solve for the opti- mal flow distribution among paths within Kl (i, j, t) (Chang and Ziliaskopoulos 2004; Lu et al. 2008b), the determination of the step size and gradient are based on a simple joint approximation of the descent direction and step size. This strategy is adopted after a careful consideration of the trade- offs between the solution quality and computational tracta- bility. The methods that explicitly solve for the optimal distribution given Kl (i, j, t) require significantly more com- putation time that may make the algorithm computationally intractable unless a parallel computing scheme is used. Over- all, the GFV method used in SHRP 2 C10B exhibits satisfactory convergence quality for a reasonable computation time. A schematic representation of the GFV algorithm as part of DynusT is illustrated in Figure 2.3. The iterative simulation assignment is initialized with the primary inputs of network loading: demand patterns, time-dependent OD matrices, and initial path assignments. As the AMS model simulates vehi- cles within the network, evaluations of time-varying link densities, link flows, travel times, and speeds are made (Chiu

9 et al. 2010). After the initial network loading, the interplay between GFV and the AMS simulation continues until the convergence criterion is met. The convergence criterion is the gap function value, which is further discussed below. The GFV procedure starts by sorting vehicles for all Kl (i, j, t) based on vehicles’ experienced travel times. Note that vehicles are loaded into the network on links; therefore, the origin node i for a vehicle refers to the downstream node of the link on which the vehicle is loaded. In the GFV algorithm, the step size is in relation to the rela- tive gap (RG) value, calculated ∀k ∈ Kl (i, j, t). Furthermore, the relative gap RGk for path k defined in Equation 2.6 indi- cates that qv is the experienced travel time of vehicle v (from the downstream node of origin link i to destination node j) and ut,li,j is the calculated time-dependent shortest path travel time for (i, j, t) at iteration l solved by the TDSP algorithm. RGk measures the travel time deviation of path k in compari- son with the shortest path. ∑ ( )= − ∀ ∈ τ( ) τ τ ∈ τ τ τ RG q r u r u k K i jk v i j k l i j l v V i j k i j k l i j l l l i i , , , (2.6) , , , , , , , , , , , , , The stopping criterion follows Equation 2.7. (2.7)0RG RG≤ where RG0 is the user-specified threshold and RG follows Equation 2.8. (2.8) , , , , ,, , ,, , , , , , , , RG q r u r u v i j i j l i jv V i j ki j k i j i j l i j l i i ∑∑∑ ∑ ( ) ( )= −( ) τ τ τ∈ ττ τ τ τ GAP FUNCTION VEHICLE-BASED ASSIGNMENT (GFV) Network Initialization Demand patterns Time-dependent OD matrices Initial path assignment Traffic Simulator (AMS) Evaluation of time-dependent link densities, travel times, turn penalties Path Processing Time-dependent shortest path Initial Path Assignment MoE Statistics Vehicles with Updated Path Assignment Path Assignment Update Calculate gradient/swapping rate, Identify subset, Update path flow, Re-assign vehicles with paths, ,, jiK l l kd 1, ,, l kjir Gap Function Vehicle-Based Assignment (GFV) Vehicle sort, Vehicle flow adjustment, Total vehicle flow, l ji , , ,, ji jir , Relative Gap Convergence?YESSTOP NO , ,i j kr Figure 2.3. GFV method in conjunction with DynusT.

10 Next, the time-dependent shortest path is solved. At each iteration l, the flow for each k ∈ Kl (i, j, t) to be shifted at this iteration is the step size at,li,j times the total flow r ti,j between the (i, j, t) triplet. at,li,j is defined as the minimal of two candi- date step sizes as shown in Equation 2.9. a′ is the RG-based step size, calculated based on Equation 2.10; a0 is the maxi- mum step size. The step size is determined by Equation 2.7 as the RG-based step size is calculated as average RG value for all path k ∈ Kl (i, j, t): min , (2.9), , 0 i j l { }α = α ′ατ ∑ ( )′α = τ   RG K i j kk l , , (2.10)  Kl (i, j, t) is the cardinality of the set of non-zero flow paths between criterion (i, j, t) for iteration l. Paths in Kl (i, j, t) are ordered with decreasing travel time. Note Kl (i, j, t) includes the TDSP solved at the current iteration. Based on Equation 2.6 through Equation 2.10, one should expect that since the algorithm starts from an all-or-nothing (AON) assignment,  Kl (i, j, t) is small and RGk may be large; therefore, the step size is initially capped at a0. As iterations increase,  Kl (i, j, t) also increases while RGk decreases. With the step size capped by a0 at initial iterations, as iterations increase, the step size then will be handled by a′ as the size of path sets Kl (i, j, t) would eventually stabilize. The value of a′ generally continues to decrease as the time-dependent user equilibrium (TDUE) solution is iteratively improved. If the assignment starts from an initial simulation in which vehicles are being loaded following TDUE paths solved from a prior TDUE run, the step size in the initial iteration is likely to be capped by a′. This reduces excess fluctuation of the initial assignment away from the TDUE condition since the initial solution is already close to the TDUE condition. Only those Kl (i, j, t) exhibiting large gaps are to be shifted with a larger flow amount. This observation implies a relatively stable and quick convergence for a warm-start assignment. Next, the descent direction dlk updates the direction of flow adjustment at iteration l using what are considered increasing- flow and decreasing-flow path subsets. Kl (i, j, t)+ defines the path subset that will have the increased flow after assignment while Kl (i, j, t)- is the path subset with decreased flow, where ( ) ( ) ( )τ ∪ τ = τ+ −K i j K i j K i jl l l, , , , , , (2.11) After determining the step size, the amount of the total shifted flow is at,li,j z r ti,j, by definition. It is important to note that in Kl (i, j, t), paths are always ranked in the order of increasing path average travel time q t,li,j,k, which is ∑ ( ) ( )= τ ∀ ∈ τ ( )τ ∈ τq q V i j k k K i ji j k l vv V i j k l l l , , , , , , (2.12), , , , , , and ≤ ≤ ≤ ( ) τ τ τ τq q qi j l i j l i j K i j l l . . . (2.13), ,1 , , ,2 , , , , , , The decreasing-flow path set Kl (i, j, t)-, as defined in Equation 2.14, is determined by scanning paths k = 1, 2, . . . , kˆ until the condition defined in Equation 2.15 is met. kˆ is the cutoff path in which vehicles in any path k ∈ Kl (i, j, t) whose q t,li,j,k ≥ q t,li,j,kˆ will be considered for reassignment. , , ,ˆ . . . , , , (2.14) , , , , , 1 ˆ 1 , , , , 1 ˆ K i j k k K i j r r rl l i j k l i j l k k i j i j k l k k i∑ ∑{ }( ) ( )τ = = τ < α ≤− τ τ = − τ τ = Equation 2.14 only determines the decreasing-flow path set; however, because the GFV algorithm is vehicle based, the step size at,li,j specifies a certain number of vehicles that would be reas- signed to the increasing-flow path set. For that reason, all vehi- cles on path k ∈ Kl (i, j, t)-\kˆ will be assigned to the increasing- flow path set, but only part of those on the cutoff path kˆ will be assigned. vˆ is defined as the cutoff vehicle on path kˆ such that any vehicle beneath vˆ is not considered for reassignment. ∑= − α ( ) τ τ τ = τ − v r ri j k l i j l i j k K i jl iˆ (2.15), , , , , , 1 , , Those vehicles belonging to k ∈ Kl (i, j, t)- will be reassigned with one of the paths in the set Kl (i, j, t)+, which may also include the latest solved TDSP. The redistribution scheme is depicted in Equation 2.16: ∑ ( ) ( ) ( ) ( ) ( ) = − − ∀ ∈ τ − α ∀ ∈ τ − α ∈ τ      ( ) θ θ ∈ τ + τ τ τ − τ τ − + d RG RG RG RG k K i j r r k K i j k v r k K i j k l k k k kk K i j l i j k l i j l i j l i j l i j l i i , , , , , , \ ˆ ˆ , ˆ , , (2.16) ˆ ˆ, , , , , , , , , , , where RGkˆ is the relative gap value for cutoff path kˆ.

11 For those paths k ∈ Kl (i, j, t)+, the number of vehicles is increased by the amount (2.17), , , ˆ ˆ, , i i ∑ ) ) ( (α − −)( τ τ θ θ ∈ τ + r RG RG RG RG i j l i j k k k kk K i j For a vehicle to be assigned to a path k ∈ Kl (i, j, t)+, the prob- ability can be expressed as ˆ ˆ, , P k RG RG RG RG k k k kk K i j∑ ( ) ( )( ) = − −( ) θ θ ∈ τ + For those paths k ∈ Kl (i, j, t)-\kˆ the change in the number of vehicles is , , , , , , , , , i i i −α α τ τ τ τ τ r r r i j l i j i j k l i j l i j For k = kˆ, the decrease amount is −α α τ τ τ τ r v r i j l i j i j l i j i i i ˆ , , , , , , Note that q is a scaling factor which can be kept as a pre- defined constant or can be an increasing function of iteration number. The larger q is, the more aggressive the assigned flow to the first best paths will be. The value used in the C10B proj- ect is 2.0. Lastly, all flow determined to be reassigned are applied to all paths k ∈ Kl (i, j, t)+ following a nonlinear proportional scheme: , , ,, , , 1 , , , , , ,r r r d k K i ji j k l i j k l i j l i j k l li i ( )= + α ∀ ∈ ττ + τ τ τ