A Bi‐Level Model for Planning Signalized and Uninterrupted Flow Intersections in an Evacuation Network

Abstract: The problem to be addressed in this paper is the lack of an advanced model in the literature to locate the optimal set of intersections in the evacuation network for implementing uninterrupted flow and signal control strategies, respectively, which can yield the maximum evacuation operational efficiency and the best use of available budgets. An optimization model, proposed in response to such needs, contributes to addressing the following critical questions that have long challenged transportation authorities during emergency planning, namely: given the topology of an evacuation network, evacuation demand distribution, and a limited budget, (1) how many intersections should be implemented with the signals and uninterrupted flow strategies; (2) what are their most appropriate locations; and (3) how should turning restriction plans be properly designed for those uninterrupted flow intersections? The proposed model features a bi‐level framework. The upper level determines the best locations for uninterrupted flow and signalized intersections as well as the corresponding turning restriction plans by minimizing the total evacuation time, while the lower level handles routing assignments of evacuation traffic based on the stochastic user equilibrium (SUE) principle. The proposed model is solved by a genetic algorithm (GA) ‐based heuristic. Extensive analyses under various evacuation demand and budget levels have indicated that the location selection of uninterrupted flow and signalized intersections plays a key role in emergency traffic management. The proposed model substantially outperforms existing practices in prioritizing limited resources to the most appropriate control points by significantly reducing the total evacuation time (up to 39%).     

A Hybrid Branch‐and‐Bound and Benders Decomposition Algorithm for the Network Design Problem

Given a set of candidate road projects associated with costs, finding the best subset with respect to a limited budget is known as the network design problem (NDP). The NDP is often cast in a bilevel programming problem which is known to be NP‐hard. In this study, we tackle a special case of the NDP where the decision variables are integers. A variety of exact solutions has been proposed for the discrete NDP, but due to the combinatorial complexity, the literature has yet to address the problem for large‐size networks, and accounting for the multimodal and multiclass traffic flows. To this end, the bilevel problem is solved by branch‐and‐bound. At each node of the search tree, a valid lower bound based on system optimal (SO) traffic flow is calculated. The SO traffic flow is formulated as a mixed integer, non‐linear programming (MINLP) problem for which the Benders decomposition method is used. The algorithm is coded on a hybrid and synchronized platform consisting of MATLAB (optimization engine), EMME 3 (transport planning module), MS Access (database), and MS Excel (user interface). The proposed methodology is applied to three examples including Gao's network, the Sioux‐Falls network, and a real size network representing the city of Winnipeg, Canada. Numerical tests on the network of Winnipeg at various budget levels have shown promising results.     

A Dual Variable Approximation‐Based Descent Method for a Bi‐level Continuous Dynamic Network Design Problem

Abstract: The transportation network design problem (NDP) considers modifying network topology or parameters, such as capacity, to optimize system performance by taking into account the selfish routing behavior of road users. The nature of the problem naturally lends itself to a bi‐level formulation of a problem that represents a static case of a Stackelberg game. The NDP is complex because users’ individual objectives do not necessarily align with system‐wide objectives; thus, it is difficult to determine the optimal allocation of limited resources. To solve the bi‐level dynamic NDP, this study develops a dual variable approximation‐based heuristic, which identifies the system‐wide gradient as a descent direction, and designs an iterative solution framework. Descent direction‐based approaches designed to solve bi‐level programming problems typically suffer from non‐differentiability, which can hamper the solution process. The proposed method addresses this issue by approximating the descent direction with dual variables that correspond to cell transmission model constraints and using the constructed rational direction to iteratively decrease the upper‐level objective while maintaining the feasibility of the lower‐level program. The proposed method was empirically applied to three networks of various sizes. The results obtained from this empirical solution were compared with the results from an exact Kth‐best algorithm and a genetic algorithm. The promising results demonstrate the efficacy and efficiency of the proposed descent method.     

A Dantzig‐Wolfe Decomposition‐Based Heuristic for Off‐line Capacity Calibration of Dynamic Traffic Assignment

Abstract: One of the critical elements in considering any real‐time traffic management strategy requires assessing network traffic dynamics. Traffic is inherently dynamic, since it features congestion patterns that evolve over time and queues that form and dissipate over a planning horizon. Dynamic traffic assignment (DTA) is therefore gaining wider acceptance among agencies and practitioners as a more realistic representation of traffic phenomena than static traffic assignment. Though it is imperative to calibrate the DTA model such that it can accurately reproduce field observations and avoid erroneous flow predictions when evaluating traffic management strategies, DTA calibration is an onerous task due to the large number of variables that can be modified and the intensive computational resources required. To compliment other research on behavioral and trip table issues, this work focuses on DTA capacity calibration and presents an efficient Dantzig‐Wolfe decomposition‐based heuristic that decomposes the problem into a restricted master problem and a series of pricing problems. The restricted master problem is a capacity manipulation problem, which can be solved by a linear programming solver. The pricing problem is the user optimal DTA which can be optimally solved by an existing combinatorial algorithm. In addition, the proposed set of dual variable approximation techniques is one of a very limited number of approaches that can be used to estimate network‐wide dual information in facilitating algorithmic designs while maintaining scalability. Two networks of various sizes are empirically tested to demonstrate the efficiency and efficacy of the proposed heuristic. Based on the results, the proposed heuristic can calibrate the network capacity and match the counts within a 1% optimality gap.     

Graph‐Based Modeling of Information Flow Evolution and Propagation under V2V Communications‐Based Advanced Traveler Information Systems

A vehicle equipped with a vehicle‐to‐vehicle (V2V) communications capability can continuously update its knowledge on traffic conditions using its own experience and anonymously obtained travel experience data from other such equipped vehicles without any central coordination. In such a V2V communications‐based advanced traveler information system (ATIS), the dynamics of traffic flow and intervehicle communication lead to the time‐dependent vehicle knowledge on the traffic network conditions. In this context, this study proposes a graph‐based multilayer network framework to model the V2V‐based ATIS as a complex system which is composed of three coupled network layers: a physical traffic flow network, and virtual intervehicle communication and information flow networks. To determine the occurrence of V2V communication, the intervehicle communication layer is first constructed using the time‐dependent locations of vehicles in the traffic flow layer and intervehicle communication‐related constraints. Then an information flow network is constructed based on events in the traffic and intervehicle communication networks. The graph structure of this information flow network enables the efficient tracking of the time‐dependent vehicle knowledge of the traffic network conditions using a simple graph‐based reverse search algorithm and the storage of the information flow network as a single graph database. Further, the proposed framework provides a retrospective modeling capability to articulate explicitly how information flow evolves and propagates. These capabilities are critical to develop strategies for the rapid flow of useful information and traffic routing to enhance network performance. It also serves as a basic building block for the design of V2V‐based route guidance strategies to manage traffic conditions in congested networks. Synthetic experiments are used to compare the graph‐based approach to a simulation‐based approach, and illustrate both memory usage and computational time efficiencies.     

A Cell‐Based Model for Multi‐class Doubly Stochastic Dynamic Traffic Assignment

Abstract: This article proposes a cell‐based multi‐class dynamic traffic assignment problem that considers the random evolution of traffic states. Travelers are assumed to select routes based on perceived effective travel time, where effective travel time is the sum of mean travel time and safety margin. The proposed problem is formulated as a fixed point problem, which includes a Monte–Carlo‐based stochastic cell transmission model to capture the effect of physical queues and the random evolution of traffic states during flow propagation. The fixed point problem is solved by the self‐regulated averaging method. The results illustrate the properties of the problem and the effectiveness of the solution method. The key findings include the following: (1) Reducing perception errors on traffic conditions may not be able to reduce the uncertainty of estimating system performance, (2) Using the self‐regulated averaging method can give a much faster rate of convergence in most test cases compared with using the method of successive averages, (3) The combination of the values of the step size parameters highly affects the speed of convergence, (4) A higher demand, a better information quality, or a higher degree of the risk aversion of drivers can lead to a higher computation time, (5) More driver classes do not necessarily result in a longer computation time, and (6) Computation time can be significantly reduced by using small sample sizes in the early stage of solution processes.     

Evaluation of Information Applications of a Self‐Organizing Distributed Traffic Information System for a Large‐Scale Real‐World Traffic Network

Abstract: This article presents an evaluation of the system performance of a proposed self‐organizing, distributed traffic information system based on vehicle‐to‐vehicle information‐sharing architecture. Using microsimulation, several information applications derived from this system are analyzed relative to the effectiveness and efficiency of the system to estimate traffic conditions along each individual path in the network, to identify possible incidents in the traffic network, and to provide rerouting strategies for vehicles to escape congested spots in the network. A subset of vehicles in the traffic network is equipped with specific intervehicle communication devices capable of autonomous traffic surveillance, peer‐to‐peer information sharing, and self‐data processing. A self‐organizing traffic information overlay on the existing vehicular roadway network assists their independent evaluation of route information, detection of traffic incidents, and dynamic rerouting in the network based both on historical information stored in an in‐vehicle database and on real‐time information disseminated through intervehicle communications. A path‐based microsimulation model is developed for these information applications and the proposed distributed traffic information system is tested in a large‐scale real‐world network. Based on simulation study results, potential benefits both for travelers with such equipment as well as for the traffic system as a whole are demonstrated.     

End‐to‐End Deep Learning Methodology for Real‐Time Traffic Network Management

This article presents a novel real‐time traffic network management system using an end‐to‐end deep learning (E2EDL) methodology. A computational learning model is trained, which allows the system to identify the time‐varying traffic congestion pattern in the network, and recommend integrated traffic management schemes to reduce this congestion. The proposed model structure captures the temporal and spatial congestion pattern correlations exhibited in the network, and associates these patterns with efficient traffic management schemes. The E2EDL traffic management system is trained using a laboratory‐generated data set consisting of pairings of prevailing traffic network conditions and efficient traffic management schemes designed to cope with these conditions. The system is applied for the US‐75 corridor in Dallas, Texas. Several experiments are conducted to examine the system performance under different traffic operational conditions. The results show that the E2EDL system achieves travel time savings comparable to those recorded for an optimization‐based traffic management system.     

Surrogate‐based toll optimization in a large‐scale heterogeneously congested network

Toll optimization in a large‐scale dynamic traffic network is typically characterized by an expensive‐to‐evaluate objective function. In this paper, we propose two toll‐level problems (TLPs) integrated with a large‐scale simulation‐based dynamic traffic assignment model of Melbourne, Australia. The first TLP aims to control the pricing zone (PZ) through a time‐varying joint distance and delay toll such that the network fundamental diagram (NFD) of the PZ does not enter the congested regime. The second TLP is built upon the first TLP by further considering the minimization of the heterogeneity of congestion distribution in the PZ. To solve the two TLPs, a computationally efficient surrogate‐based optimization method, that is, regressing kriging with expected improvement sampling, is applied to approximate the simulation input–output mapping, which can balance well between local exploitation and global exploration. Results show that the two optimal TLP solutions reduce the average travel time in the PZ (entire network) by 29.5% (1.4%) and 21.6% (2.5%), respectively. Reducing the heterogeneity of congestion distribution achieves higher network flows in the PZ and a lower average travel time or a larger total travel time saving in the entire network.     

Dynamic origin‐destination flow estimation using automatic vehicle identification data: A 3D convolutional neural network approach

Dynamic origin‐destination (OD) flow estimation is one of the most fundamental problems in traffic engineering. Despite numerous existing studies, the OD flow estimation problem remains challenging, as there is large dimensional difference between the unknown values to be estimated and the known traffic observations. To meet the needs of active traffic management and control, accurate time‐dependent OD flows are required to understand time‐of‐day traffic flow patterns. In this work, we propose a three‐dimensional (3D) convolution‐based deep neural network, “Res3D,” to learn the high‐dimensional correlations between local traffic patterns presented by automatic vehicle identification observations and OD flows. In this paper, a practical framework combining simulation‐based model training and few‐shot transfer learning is introduced to enhance the applicability of the proposed model, as continuously observing OD flows could be expensive. The proposed model is extensively tested based on a realistic road network, and the results show that for significant OD flows, the relative errors are stable around 5%, outperforming several other models, including prevalent neural networks as well as existing estimation models. Meanwhile, corrupted and out‐of‐distribution samples are generated as real‐world samples to validate Res3D's transferability, and the results indicated a 60% improvement with few‐shot transfer learning. Therefore, this proposed framework could help to bridge the gaps between traffic simulations and empirical cases.     

A graph deep learning method for short‐term traffic forecasting on large road networks

Short‐term traffic flow prediction on a large‐scale road network is challenging due to the complex spatial–temporal dependencies, the directed network topology, and the high computational cost. To address the challenges, this article develops a graph deep learning framework to predict large‐scale network traffic flow with high accuracy and efficiency. Specifically, we model the dynamics of the traffic flow on a road network as an irreducible and aperiodic Markov chain on a directed graph. Based on the representation, a novel spatial–temporal graph inception residual network (STGI‐ResNet) is developed for network‐based traffic prediction. This model integrates multiple spatial–temporal graph convolution (STGC) operators, residual learning, and the inception structure. The proposed STGC operators can adaptively extract spatial–temporal features from multiple traffic periodicities while preserving the topology information of the road network. The proposed STGI‐ResNet inherits the advantages of residual learning and inception structure to improve prediction accuracy, accelerate the model training process, and reduce difficult parameter tuning efforts. The computational complexity is linearly related to the number of road links, which enables citywide short‐term traffic prediction. Experiments using a car‐hailing traffic data set at 10‐, 30‐, and 60‐min intervals for a large road network in a Chinese city shows that the proposed model outperformed various state‐of‐the‐art baselines for short‐term network traffic flow prediction.     

Bi-level Programming Formulation and Heuristic Solution Approach for Dynamic Traffic Signal Optimization

Abstract:   Although dynamic traffic control and traffic assignment are intimately connected in the framework of Intelligent Transportation Systems (ITS), they have been developed independent of one another by most existing research. Conventional methods of signal timing optimization assume given traffic flow pattern, whereas traffic assignment is performed with the assumption of fixed signal timing. This study develops a bi-level programming formulation and heuristic solution approach (HSA) for dynamic traffic signal optimization in networks with time-dependent demand and stochastic route choice. In the bi-level programming model, the upper level problem represents the decision-making behavior (signal control) of the system manager, while the user travel behavior is represented at the lower level. The HSA consists of a Genetic Algorithm (GA) and a Cell Transmission Simulation (CTS) based Incremental Logit Assignment (ILA) procedure. GA is used to seek the upper level signal control variables. ILA is developed to find user optimal flow pattern at the lower level, and CTS is implemented to propagate traffic and collect real-time traffic information. The performance of the HSA is investigated in numerical applications in a sample network. These applications compare the efficiency and quality of the global optima achieved by Elitist GA and Micro GA. Furthermore, the impact of different frequencies of updating information and different population sizes of GA on system performance is analyzed.     

Wavelet‐Based Denoising for Traffic Volume Time Series Forecasting with Self‐Organizing Neural Networks

Abstract: In their goal to effectively manage the use of existing infrastructures, intelligent transportation systems require precise forecasting of near‐term traffic volumes to feed real‐time analytical models and traffic surveillance tools that alert of network links reaching their capacity. This article proposes a new methodological approach for short‐term predictions of time series of volume data at isolated cross sections. The originality in the computational modeling stems from the fit of threshold values used in the stationary wavelet‐based denoising process applied on the time series, and from the determination of patterns that characterize the evolution of its samples over a fixed prediction horizon. A self‐organizing fuzzy neural network is optimized in its configuration parameters for learning and recognition of these patterns. Four real‐world data sets from three interstate roads are considered for evaluating the performance of the proposed model. A quantitative comparison made with the results obtained by four other relevant prediction models shows a favorable outcome.     

Strategic network expansion of urban rapid transit systems: A bi‐objective programming model

With the development of urbanization and the extension of city boundaries, the expansion of rapid transit systems based on the existing lines becomes an essential issue in urban transportation systems. In this study, the network expansion problem is formulated as a bi‐objective programming model to minimize the construction cost and maximize the total travel demand covered by the newly introduced transit lines. To solve the bi‐objective mixed‐integer linear program, an approach called minimum distance to the utopia point is applied. Thus, the specific trade‐off is suggested to the decision makers instead of a series of optimal solutions. A real‐world case study based on the metro network in Wuxi, China, is conducted, and the results demonstrate the effectiveness and efficiency of the proposed model and solution method. It is found that the utopia method can not only provide a reasonable connecting pattern of the network expansion problem but also identify the corridors with high priority under the limited budget condition.     

High‐Order Computational Scheme for a Dynamic Continuum Model for Bi‐Directional Pedestrian Flows

Abstract: In this article, we present a high‐order weighted essentially non‐oscillatory (WENO) scheme, coupled with a high‐order fast sweeping method, for solving a dynamic continuum model for bi‐directional pedestrian flows. We first review the dynamic continuum model for bi‐directional pedestrian flows. This model is composed of a coupled system of a conservation law and an Eikonal equation. Then we present the first‐order Lax–Friedrichs difference scheme with first‐order Euler forward time discretization, the third‐order WENO scheme with third‐order total variation diminishing (TVD) Runge–Kutta time discretization, and the fast sweeping method, and demonstrate how to apply them to the model under study. We present a comparison of the numerical results of the model from the first‐order and high‐order methods, and conclude that the high‐order method is more efficient than the first‐order one, and they both converge to the same solution of the physical model.     

A two‐level mixed‐integer programming model for bridge replacement prioritization

A bridge network is an essential part of the transportation system. Therefore, the restoration and replacement activities of aging bridges result in severe traffic delays and disruptions that heavily impact the daily traffic. Accelerated bridge construction (ABC) techniques are rapidly gaining acceptance as an alternative to conventional construction due to reduced construction duration and minimum closure impact at the network level. The limitations and completion rates vary depending on types of ABC. There is a trade‐off between a faster ABC technique with higher investment and a faster construction of a critical bridge in the network resulting large savings to users. To provide a balanced portfolio of ABC techniques on bridge sites and the prioritization of bridges for replacement, this paper develops a mixed‐integer programming (MIP) model with two levels. In this model, a network‐level scheme is used to select bridges for rapid replacement based on their criticality to the network, and a project‐level scheme is used to optimize the choice of ABC techniques for each selected bridge. To account for the effects of different construction strategies for bridge replacement, the costs associated with each replacement activity are calculated, including direct costs from the actual replacement of bridges and indirect costs experienced by network users due to bridge closures during maintenance. Using the MIP model and based on investment, outcomes are estimated for the enhanced serviceability, efficient ABC techniques, an optimal bridge replacement strategy, and minimized total cost during the entire process. These outcomes could provide decision makers and stakeholders with a complete understanding of the prioritization process at both the network and project levels.     

Surrogate‐Based Optimization of Expensive‐to‐Evaluate Objective for Optimal Highway Toll Charges in Transportation Network

This article adopts a family of surrogate‐based optimization approaches to approximate the response surface for the transportation simulation input–output mapping and search for the optimal toll charges in a transportation network. The computational effort can thus be significantly reduced for the expensive‐to‐evaluate optimization problem. Meanwhile, the random noise that always occurs through simulations can be addressed by this family of approaches. Both one‐stage and two‐stage surrogate models are tested and compared. A suboptimal exploration strategy and a global exploration strategy are incorporated and validated. A simulation‐based dynamic traffic assignment model DynusT (Dynamic Urban Systems in Transportation) is utilized to evaluate the system performance in response to different link‐additive toll schemes implemented on a highway in a real road transportation network. With the objective of minimizing the network‐wide average travel time, the simulation results show that implementing the optimal toll predicted by the surrogate model can benefit society in multiple ways. The travelers gain from the 2.5% reduction (0.45 minutes) of the average travel time. The total reduction in the time cost during the extended peak hours would be around US$65,000 for all the 570,000 network users assuming a US$15 per hour value of time. Meanwhile, the government benefits from the 20% increase of toll revenue compared to the current situation. Thus, applying the optimized pricing scheme in real world can be an encouraging policy option to enhance the performance of the transportation system in the study region.     

Passing Rates to Measure Relaxation and Impact of Lane‐Changing in Congestion

Abstract: Passing rate measurements of backward‐moving kinematic waves in congestion are applied to quantify two traffic features; a relaxation phenomenon of vehicle lane‐changing and impact of lane‐changing in traffic streams after the relaxation process is complete. The relaxation phenomenon occurs when either a lane‐changer or its immediate follower accepts a short spacing upon insertion and gradually resumes a larger spacing. A simple existing model describes this process with few observable parameters. In this study, the existing model is reformulated to estimate its parameter using passing rate measurements. Calibration results based on vehicle trajectories from two freeway locations indicate that the revised relaxation model matches the observation well. The results also indicate that the relaxation occurs in about 15 seconds and that the shoulder lane exhibits a longer relaxation duration. The passing rate measurements were also employed to quantify the postrelaxation impact of multiple lane‐changing maneuvers within a platoon of 10 or more vehicles in queued traffic stream. The analysis of the same data sets shows that lane‐changing activities do not induce a long‐term change in traffic states; traffic streams are perturbed temporarily by lane‐changing maneuvers but return to the initial states after relaxations.     

Short‐Term Traffic Speed Prediction for an Urban Corridor

Short‐term traffic speed prediction is one of the most critical components of an intelligent transportation system (ITS). The accurate and real‐time prediction of traffic speeds can support travellers’ route choices and traffic guidance/control. In this article, a support vector machine model (single‐step prediction model) composed of spatial and temporal parameters is proposed. Furthermore, a short‐term traffic speed prediction model is developed based on the single‐step prediction model. To test the accuracy of the proposed short‐term traffic speed prediction model, its application is illustrated using GPS data from taxis in Foshan city, China. The results indicate that the error of the short‐term traffic speed prediction varies from 3.31% to 15.35%. The support vector machine model with spatial‐temporal parameters exhibits good performance compared with an artificial neural network, a k‐nearest neighbor model, a historical data‐based model, and a moving average data‐based model.     

Cross‐comparison of convergence algorithms to solve trip‐based dynamic traffic assignment problems

Solving a dynamic traffic assignment problem in a transportation network is a computational challenge. This study first reviews the different algorithms in the literature used to numerically calculate the user equilibrium (UE) related to dynamic network loading. Most of them are based on iterative methods to solve a fixed‐point problem. Two elements must be computed: the path set and the optimal path flow distribution between all origin–destination pairs. In a generic framework, these two steps are referred to as the outer and the inner loops, respectively. The goal of this study is to assess the computational performance of the inner loop methods that calculate the path flow distribution for different network settings (mainly network size and demand levels). Several improvements are also proposed to speed up convergence: four new swapping algorithms and two new methods for the step size initialization used in each descent iteration. All these extensions significantly reduce the number of iterations to obtain a good convergence rate and drastically speed up the overall simulations. The results show that the performance of different components of the solution algorithm is sensitive to the network size and saturation. Finally, the best algorithms and settings are identified for all network sizes with particular attention being given to the largest scale.