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.

12 C h a p t e r 3 transit Simulation Vehicle simulation under the presence of transit vehicles needs to properly differentiate the situation with or without bus pull- outs. As illustrated in Figure 3.1, when a bus pullout is present and a transit vehicle resides in the pullout, passerby vehicles’ SIR area remains unchanged. On the other hand, without the pull- out the stopped transit vehicle typically blocks one traffic lane, creating a temporal blockage to the following traffic steam. The departure from each stop involves different rules for frequency or schedule-based transit. The main difference is that for sched- ule-based transit operation, a transit vehicle needs to be held until the scheduled departure time if the transit vehicle is still ahead of schedule after boarding and alighting. Such vehicle holding is unnecessary in frequency-based operation. As previously mentioned, demand is generated from a tour- based travel demand model. Before this information can be used for traffic simulation and assignment purposes it must be manipulated to meet the traffic simulation and assignment model’s specific network and demand inputs. In terms of demand, DynusT demand inputs take two forms: the typical OD table for specified time periods, and vehicle and path files. In general, the exogenous travel components (truck, external, and airport vehicle trips) yield OD demand files given diurnal factors while tour/trip records yield vehicle and path demand files. Generating DynusT’s vehicle demand file is a more involved process because it requires detailed trip information as opposed to OD demand files simply requiring OD and diurnal factors. Examples of this mandatory information include household identification (ID), traveler/person ID, tour/trip ID, OD parcels/points, OD zones, mode choice, travel time, value of time, and arrival/departure time. The purpose of this infor- mation is to represent a trip as realistically as possible within DynusT’s node-link based network and context. Examples of this realistic representation not only entail correct zone vehicle generation or destinations but most importantly also ensure that a specific person’s trip reaches its destination before his or her next trip (tour) is generated. This instance is usually prevalent in networks with congestion or disruption or where trips are sequenced immediately after one another. temporal Domain Decomposition algorithmic Scheme for Large-Scale Dta Implementation In order to support ABM integration, DynusT needs to perform 24-h simulation and assignment. This large spatial and tempo- ral scale brings forth great computational challenges in algo- rithm design and implementation. The DynusT research team developed a temporal decomposition scheme called the Method of Isochronal Vehicle Assignment (MIVA) that has successfully overcome this computational challenge and enabled DynusT to perform megascale spatial- and temporal-scale dynamic traffic assignment. The design concept is to divide the entire analysis period into epochs (evenly or based on computing loads). Vehicle assignment is performed sequentially and parallelly in each epoch. Vehicles generated in each epoch are assigned in a par- allel (multi-threaded) fashion. This scheme has two principal advantages. First, it improves the model scalability by confin- ing the peak runtime memory requirement as the maximum memory usage for each individual epoch regardless of the total analysis period, thus improving the memory efficiency. Secondly, the parallel processing of vehicle assignment further improves the runtime efficiency. A self-turning scheme adap- tively searches for the runtime-optimal epoch setting during iterations regardless of the characteristics of the modeled net- work. The following explanations are the brief excerpt from Nava and Chiu (2012). As shown in Figure 3.2, the common algorithmic frame- work of a typical simulation-based DTA model includes the iterative execution of network loading (simulation), the path DynusT Enhancement for the Integrated Model

13 set update procedure (time-dependent travel time cost of routes for all origin, destination, and departure time triplets), and the path set adjustment (DTA) procedure to update vehi- cle paths. To determine how close the current solution is to the dynamic user equilibrium (DUE) condition, the evalua- tion of path assignments, by means of simulation, requires checking a defined convergence criterion. The algorithm ter- minates if the stopping criterion is met. The proposed MIVA decouples the time domain between simulation and both the path set update and path adjustment procedures (composed of the TDSP and assignment solution algorithm) into forward-sliding time periods, which allows the memory requirement for both the path set update and path adjustment to be bounded solely on the length of the deter- mined temporal segment instead of the entire analysis period. The memory usage for storing time-varying link travel times is of memory size I × T, where I is the set of links and T is the set of assignment intervals. Memory usage for storing the time-varying node (intersection) delay is of size I × M × T, where M is the set of movements. These arrays are of mod- est size, even for a large network and long analysis period. The TDSP memory requirement, depending on the algorithmic implementation, generally requires the memory for storing many arrays with dimension I × M × J × T, where J is (a) (b) Figure 3.1. SIR areas with and without bus pullouts. Path Set Update (Including Latest TDSP) Path Adjustment Arrays Storing Time-Varying Travel Time, Intersection Delay, etc. Network Loading Stop Assignment Interval Convergence Check Simulation Interval Arrays Storing Vehicles and Assigned (Selected) Paths Simulation Period Source: Chiu et al. 2011. Figure 3.2. The simulation-based DTA algorithmic framework.

14 the set of destinations (or zones if the destination is the cen- troid of the zone). For example, a network with 20,000 links, 1,000 zones, 5 movements per intersection, and 100 depar- ture intervals would need 1 × E10 elements to store informa- tion for one array, let alone the multiple arrays typically needed during full network TDSP computation. The applied TDSP algorithm for this research is label-correcting with complexity O(nmT 2), where n is the number of nodes, m is number of links, and T is number of assignment intervals. It is apparent that the TDSP computational time will grow poly- nomially with network size and the analysis period. The mem- ory usage for the assignment procedure, although varied by implementation, typically would require a significant amount of memory to store a time-dependent path set for each origin– destination–departure time triplet. The memory usage is linear in the temporal domain, but could be large if each path is stored in terms of individual nodes/links composing the path. The MIVA Temporal Decomposition Framework Shown in Figure 3.3, the MIVA scheme is denoted by two inter- associated time periods: epoch and projection period. The MIVA scheme decouples the temporal domain of the analysis period (also termed simulation period) into sequential seg- ments of equal length called epochs. For vehicles departing within a single epoch, the arrival times to their destinations are used to estimate the time period, known as the projection period, in which the T domain for the TDSP algorithm is defined for the path set update for vehicles departing within the current epoch. At the end of one epoch, all TDSP and assignment-related memory is de-allocated, and then re- allocated for the next epoch. The MIVA scheme then slides the path set update and adjustment operations from one epoch to the next until completing all epochs. As a result, the memory usage during the entire path set update and adjust- ment operation is only a function of the epoch length. Epoch The epoch is the partitioned period that acts as the temporal segment for the path adjustment procedure, meaning the TDSP and assignment procedure is bounded solely by the length of the epoch. An epoch consists of multiple assignment intervals (interchangeably termed as departure intervals as assignment is performed for vehicles departing at the same Epoch 1: TDSP Arrays Storing Time-Varying Travel Time, Intersection Delay, etc. Stop Assignment Interval Convergence Check Simulation Interval Arrays Storing Vehicles and Assigned (Selected) Paths Simulation Period Epoch 1: Vehicle Assignment Network Loading: Simulation Epoch 2: TDSP Epoch 2: Vehicle Assignment Epoch 3: TDSP Epoch 3: Vehicle Assignment Epoch 4: TDSP Epoch 4: Vehicle Assignment Epoch Projection Period Source: Nava and Chiu 2012. Figure 3.3. The MIVA computational scheme implemented within the simulation-based DTA algorithmic framework.

15 departure interval). An aggregation interval pertains to the time interval in which traffic data (e.g., time-dependent link travel times and intersection delays) are averaged to be the input for the TDSP. The assignment interval is bounded by the number of simulation intervals. A simulation interval is defined as the time resolution that traffic simulation states are updated. An assignment interval is a multiple of simulation intervals, and, in the same manner, an epoch is a multiple of assignment intervals, as shown in Figure 3.4. Let H be the simulation period and h be the length of the assignment/departure time interval in which H is discretized, resulting in a time discrete model. Let T = {t1, t2, . . . , tH/h} be the set of departure time intervals. Let the length of each epoch (number of assignment intervals) be in terms of the integer number of assignment intervals b = H/h/n where n is the pre- specified total number of epochs within H. Let E = {e1, e2, . . . , en} be the set of epochs. Let es = {t(s-1)b+1, t(s-1)b+2, . . . , tsb}, ∀ es ∈ E be the set of assignment intervals for epoch es containing b num- ber of assignment intervals. In each epoch domain there is a set of departing vehicles Ves (i, j, t) ⊆ V, where V = {v1, v2, . . . , vV}. Those vehicles v ∈ Ves (i, j, t) are assigned based on the TDSP solved over the projection period associated with es, which will be further explained in the next section. Projection Period The projection period, (es), is defined as the set of assignment intervals for each epoch es. Let P(es) = {t(s-1)b+1, t(s-1)b+2, . . . , tsb, tsb+1, . . . , tsb+y}, ∀ es ∈ E be the set of assignment intervals con- tained in the project period for epoch es. By definition, the start of the projection period is synchronized with each asso- ciated epoch. However, the projection period is extended beyond the end of the epoch by {tsb+1, . . . , tsb+y} as shown in Figure 3.4. This temporal extension is to allow the TDSP to solve for the later arrival times of those vehicles departing toward the end of the epoch. It is intuitive to set the limit of the projection period based on the latest arrival time of all vehicles departing within the epoch, as beyond this limit link travel times and intersection delays would not be needed for the current epoch’s TDSP calculation. However, binding the project period limit based on the latest arrival time may be too conservative and thus include too many additional assignment intervals if the latest arriving vehicle’s travel time is likely to improve in the next iteration because it is assigned with a new path, and/or other vehicles assigned with a better path would also improve the overall traffic condition and improve all vehicles’ travel times. With this being recognized, the length of the projec- tion period can be defined as a ratio of total vehicles based on ranked experienced arrival times. This means vehicles belonging to Ve (i, j, t) are sorted by increasing experienced arrival times. The projection period length is then defined based on a predefined ratio. For example, a 0.95 means that the end of the projection period is set at the 95th percentile of all arrival times. In other words, P(es) = {t(s-1)b+1, t(s-1)b+2, . . . , tsb, tsb+1, . . . , tsb+y}, where h z tsb+y ≥ G(j), where G is the increas- ing arrival time profile and j is the predefined ratio, 0.0 ≤ j ≤ 1.0. One should also expect that P(es) may vary due to dif- ferent levels of congestion experienced by vehicles in differ- ent epochs. Vehicles departing in an epoch corresponding to off-peak hours would have a shorter projection period than those corresponding to peak hours due to more severe con- gestion during peak hours even though the epoch lengths are identical. After solving the TDSP, the path becomes available over the domain P(es) = {t(s-1)b+1, t(s-1)b+2, . . . , tsb, tsb+1, . . . , tsb+y}. The Simulation Period Epoch es: Vehicle Assignment Projection Period P(es): Time-Dependent Shortest Path Assignment Interval Simulation Interval τ (s-1) b+1 ... τ sb … τ sb+y τ (s-1) b+1 ... τ sb Aggregation Interval Source: Nava and Chiu 2012. Figure 3.4. The epoch and projection period of the MIVA structure.

16 computational requirement to maintain Ve (i, j, t) in memory rather than for V is the major advantage of the MIVA com- putational scheme. Memory is allocated only to the TDSP of size P(e) rather than the entire simulation period. For the given Ve (i, j, t) set, the path set adjustment (i.e., the DTA solu- tion algorithm procedure) is performed, which is bounded by Source: Nava and Chiu 2012. Figure 3.5. The pseudo code of the MIVA scheme. a given e. Once path adjustment is completed ∀v ∈ Ve (i, j, t), the traffic data and TDSP calculations for the current epoch e are de-allocated from memory, and the MIVA scheme contin- ues on to the next epoch. Figure 3.5 describes the MIVA algorithmic structure within the simulation-based DTA (SBDTA) framework.