Solving a nonlinear bilevel programming model of the equilibrium network design problem for Korea

A network design problem solves for link improvements or additions to an existing transportation network provided that a certain objective function such as social welfare is maximised. In addition, an equilibrium network design problem specifically requires each link to have user equilibrium flows.In this paper, two equilibrium transportation network design problems are formulated in a nonlinear bilevel programming framework; one with a budget constraint and one without. A bilevel programming formulation allows explicit consideration of the interaction between the public sector which supplies transportation facilities and the private sector which uses the given facilities. This paper presents a descent-type algorithm to solve an equilibrium network design problem formulated in the nonlinear bilevel programming model for Korea. Numerical analysis using network data for a simplified Korean highway system is reported.     

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.     

Optimization for Roads' Construction: Selection,Prioritization, and Scheduling

Limited resources (budget, labor, machinery) have a significant toll on the roads' construction. The question of interest is: given variations of resources over a lengthy construction time, what would be the best construction scheduling plan, or how to optimize the Gantt chart while considering two highly challenging features (1) prerequisite conditions and (2) the interdependency of the benefit of the projects’ completions. We formulate it as a bilevel problem where the objective function is to minimize generalized costs and the lower level accounts for the drivers’ route choice. We employ a solution algorithm based on a supervised learning technique (a linear regression model of machine‐learning) and an integer programming problem and it is applied to the datasets of Winnipeg and Chicago. The regression model was found to be a tight approximation which resulted in an efficient algorithm (the CPU time is almost a linear function of the number of iterations). Moreover, the proposed methodology can render promising results (at least locally optimal solutions). This article is the first to formulate the Gantt chart using linear binary constraints and optimize it tailored to real‐life case studies.     

A Mixed User‐Equilibrium and System‐Optimal Traffic Flow for Connected Vehicles Stated as a Complementarity Problem

Connected vehicles (CVs), be they autonomous vehicles or a fleet of cargo carriers or Uber, are a matter of when they become a reality and not if. It is not unreasonable to think that CV technology may have a far‐reaching impact, even to the genesis of a completely new traffic pattern. To this end, the literature has yet to address the routing behavior of the CVs, namely traffic assignment problem (TAP) (perhaps it is assumed, they ought to follow the traditional shortest possible paths, known as user equilibrium [UE]). It is possible that real‐time data could be derived from the vehicles’ communications that in turn could be used to achieve a better traffic circulation. In this article, we propose a mathematical formulation to ensure the CVs are seeking the system optimal (SO) principles, while the remainder continue to pursue the old‐fashioned UE pattern. The model is formulated as a nonlinear complementarity problem (NCP). This article contributes to the literature in three distinct ways: (i) mathematical formulation for the CVs’ routing, stated as a mixed UE‐SO traffic pattern, is proposed; (ii) a variety of realistic features are explicitly considered in the solution to the TAP including road capacity, elastic demand, multiclass and asymmetric travel time; and (iii) formal proof of the existence and uniqueness of the solutions are also presented. The proposed methodology is applied to the networks of Sioux‐Falls and Melbourne.     

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 Linear Model for the Continuous Network Design Problem

Abstract:   This article is concerned with the continuous network design problem on traffic networks, assuming system optimum traffic flow conditions and time-dependent demand. A linear programming formulation is introduced based on a dynamic traffic assignment (DTA) model that propagates traffic according to the cell transmission model. The introduced approach is limited to continuous link improvements and does not provide for new link additions. The main contribution of the article is to provide an analytical formulation for network design that accounts for DTA conditions that can be used for further analysis and extensions. The model is tested on a single destination example network, resembling a freeway corridor, for various congestion levels, loading patterns and budget sizes, to demonstrate the simplicity and effectiveness of the approach.     

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%).     

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.     

Robust Transportation Network Design Under Demand Uncertainty

Abstract:   This article addresses the problem of a traffic network design problem (NDP) under demand uncertainty. The origin–destination trip matrices are taken as random variables with known probability distributions. Instead of finding optimal network design solutions for a given future scenario, we are concerned with solutions that are in some sense "good" for a variety of demand realizations. We introduce a definition of robustness accounting for the planner's required degree of robustness. We propose a formulation of the robust network design problem (RNDP) and develop a methodology based on genetic algorithm (GA) to solve the RNDP. The proposed model generates globally near-optimal network design solutions, f, based on the planner's input for robustness. The study makes two important contributions to the network design literature. First, robust network design solutions are significantly different from the deterministic NDPs and not accounting for them could potentially underestimate the network-wide impacts. Second, systematic evaluation of the performance of the model and solution algorithm is conducted on different test networks and budget levels to explore the efficacy of this approach. The results highlight the importance of accounting for robustness in transportation planning and the proposed approach is capable of producing high-quality solutions.     

A Clustering Algorithm for Bi‐Criteria Stop Location Design with Elastic Demand

This article proposes a bi‐criteria formulation to find the optimal location of light rapid transit stations in a network where demand is elastic and budget is constrained. Our model is composed of two competing objective functions seeking to maximize the total ridership and minimize the total budget allocated. In this research, demand is formulated using the random utility maximization method with variables including access time and travel time. The transit station location problem of this study is formulated using mixed integer programming and we propose a heuristic solution algorithm to solve large‐scale instances which is inspired by the problem context. The elastic demand is integrated with the optimization problem in an innovative way which facilitates the solution process. The performance of our model is evaluated on two test problems and we carry out its implementation on a real‐world instance. Due to the special shape of the Pareto front function, significant practical policy implications, in particular budget allocation, are discussed to emphasize the fact that the trade‐off between cost and benefit may result in large investments with little outcomes and vice versa.     

Time‐Varying Lane‐Based Capacity Reversibility for Traffic Management

Abstract: This article presents a new bi‐level formulation for time‐varying lane‐based capacity reversibility problem for traffic management. The problem is formulated as a bi‐level program where the lower level is the cell‐transmission‐based user‐optimal dynamic traffic assignment (UODTA). Due to its Non‐deterministic Polynomial‐time hard (NP‐hard) complexity, the genetic algorithm (GA) with the simulation‐based UODTA is adopted to solve multiorigin multidestination problems. Four GA variations are proposed. GA1 is a simple GA. GA2, GA3, and GA4 with a jam‐density factor parameter (JDF) employ time‐dependent congestion measures in their decoding procedures. The four algorithms are empirically tested on a grid network and compared based on solution quality, convergence speed, and central processing unit (CPU) time. GA3 with JDF of 0.6 appears best on the three criteria. On the Sioux Falls network, GA3 with JDF of 0.7 performs best. The GA with the appropriate inclusion of problem‐specific knowledge and parameter calibration indeed provides excellent results when compared with the simple GA.     

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.     

Random Process Model for Urban Traffic Flow Using a Wavelet‐Bayesian Hierarchical Technique

Abstract: The existing well‐known short‐term traffic forecasting algorithms require large traffic flow data sets, including information on current traffic scenarios to predict the future traffic conditions. This article proposes a random process traffic volume model that enables estimation and prediction of traffic volume at sites where such large and continuous data sets of traffic condition related information are unavailable. The proposed model is based on a combination of wavelet analysis (WA) and Bayesian hierarchical methodology (BHM). The average daily “trend” of urban traffic flow observations can be reliably modeled using discrete WA. The remaining fluctuating parts of the traffic volume observations are modeled using BHM. This BHM modeling considers that the variance of the urban traffic flow observations from an intersection vary with the time‐of‐the‐day. A case study has been performed at two busy junctions at the city‐centre of Dublin to validate the effectiveness of the strategy.     

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.     

Allocation of Link Flow Detectors for Origin‐Destination Matrix Estimation—A Comparative Study

Abstract: Origin‐destination (OD) matrices are essential for various analyses in the field of traffic planning, and they are often estimated from link flow observations. We compare methods for allocating link flow detectors to a traffic network with respect to the quality of the estimated OD‐matrix. First, an overview of allocation methods proposed in the literature is presented. Second, we construct a controlled experimental environment where any allocation method can be evaluated, and compared to others, in terms of the quality of the estimated OD‐matrix. Third, this environment is used to evaluate and compare three fundamental allocation methods. Studies are made on the Sioux Falls network and on a network modeling the city of Linköping. Our conclusion is, that the most commonly studied approach for detector allocation, maximizing the coverage of OD‐pairs, seems to be unfavorable for the quality of the estimated OD‐matrix.     

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.     

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.     

城市交通网络设计问题中的双层规划模型

城市交通网络设计问题的主要内容就是通过规划的思想建立数学模型,通过优化计算方法寻找最优的用于道路网络新建或改善的交通建设投资决策方案,即研究如何能用最少的资金投入达到使整个交通网络中某种指标最优的目的。这些具体的系统性能指标可以是使整个网络中的系统总阻抗最小、交通拥挤程度最低、能源消耗最少等,从而为交通规划部门和决策人员提供科学、系统、合理、有效的决策方案和决策数据,使政府有限的资金投入能取得最佳的投资效益。本文首先简单介绍了城市交通网络设计问题研究的主要内容,然后给出了城市交通网络设计中一般形式的双层规划模型及其推广形式。     

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.