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.     

Effect of Pulse‐and‐Glide Strategy on Traffic Flow for a Platoon of Mixed Automated and Manually Driven Vehicles

The fuel consumption of ground vehicles is significantly affected by how they are driven. The fuel‐optimized vehicular automation technique can improve fuel economy for the host vehicle, but their effectiveness on a platoon of vehicles is still unknown. This article studies the performance of a well‐known fuel‐optimized vehicle automation strategy, i.e., Pulse‐and‐Glide (PnG) operation, on traffic smoothness and fuel economy in a mixed traffic flow. The mixed traffic flow is assumed to be a single‐lane highway on flat road consisting of both driverless and manually driven vehicles. The driverless vehicles are equipped with fuel economy‐oriented automated controller using the PnG strategy. The manually driven vehicles are simulated using the Intelligent Driver Models (IDM) to mimic the average car‐following behavior of human drivers in naturalistic traffics. A series of simulations are conducted with three scenarios, i.e., a single car, a car section, and a car platoon. The simulation results show that the PnG strategy can significantly improve the fuel economy of individual vehicles. For traffic flows, the fuel economy and traffic smoothness vary significantly under the PnG strategy.     

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.     

Relay Requirement and Traffic Assignment of Electric Vehicles

This article defines, formulates, and solves a new equilibrium traffic assignment problem with side constraints—the traffic assignment problem with relays. The relay requirement arises from the driving situation that the onboard fuel capacity of vehicles is lower than what is needed for accomplishing their trips and the number and distribution of refueling infrastructures over the network are under the expected level. We proposed this problem as a modeling platform for evaluating congested regional transportation networks that serve plug‐in electric vehicles (in addition to internal combustion engine vehicles), where battery‐recharging or battery‐swapping stations are scarce. Specifically, we presented a novel nonlinear integer programming formulation, analyzed its mathematical properties and paradoxical phenomena, and suggested a generalized Benders decomposition framework for its solutions. In the algorithmic framework, a gradient projection algorithm and a labeling algorithm are adopted for, respectively, solving the primal problem and the relaxed master problem—the shortest path problem with relays. The modeling and solution methods are implemented for solving a set of example network problems. The numerical analysis results obtained from the implementation clearly show how the driving range limit and relay station location reshape equilibrium network flows.     

A Customized Hybrid Approach to Infrastructure Maintenance Scheduling in Railroad Networks under Variable Productivities

Railroads are maintained routinely by using various types of rail‐bound machines so as to achieve the longest possible rail life and reduce the safety risks associated with unanticipated rail failures. The rail maintenance routing and scheduling problem (RMRSP), which involves routing of multiple maintenance vehicles and scheduling of hundreds of maintenance jobs over a large‐scale network, is usually subject to various types of complex constraints and extremely difficult to solve. This article proposes a vehicle routing problem with time windows (VRPTW) formulation for RMRSP and develops a customized stepwise algorithm to solve the problem. A series of numerical experiments are conducted to demonstrate that the proposed algorithm works very effectively, significantly outperforming the state‐of‐the‐art commercial solver. The results of two real‐world instances from a Class I railroad company show that the proposed model and solution algorithm enable the expensive maintenance vehicles to achieve a higher level of utilization, that is, spending more time on working and less time on deadhead traveling.     

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.     

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.     

Two‐Dimensional Simulation of Turning Behavior in Potential Conflict Area of Mixed‐Flow Intersections

The potential conflict area of intersection is the space where conflicting traffic flows pass through in the same signal phase. At this area, turning vehicles interact with most traffic flows, which introduce complex features including variation of trajectories and shared‐priority phenomenon. The traditional one‐dimensional simulation oversimplifies these features with lane‐based assumption. This study integrates the modified social force model with behavior decision and movement constraints to reproduce the two‐dimensional turning process. The method is framed into a three‐layered mathematical model. First, the decision layer dynamically makes decision for turning patterns. Then the operation layer uses the modified social force model to initially generate vehicle movements. Finally, the constraint layer modifies the vehicular motion with vehicle dynamics constraints, boundary of intersection and the collision avoidance rule. The proposed model is validated using trajectories of left‐turn vehicles at a real‐world mixed‐flow intersection with nonprotected signal phases, resulting in a more realistic simulation than previous methods. The distributions of decision points and travel time in simulation are compared with the empirical data in statistics. Moreover, the spatial distribution of simulated trajectories is also satisfactory.     

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.     

Column Generation‐Based Approach for Solving Large‐Scale Ready Mixed Concrete Delivery Dispatching Problems

Ready mix concrete (RMC) dispatching forms a critical component of the construction supply chain. However, optimization approaches within the RMC dispatching continue to evolve due to the specific size, constraints, and objectives required of the application domain. In this article, we develop a column generation algorithm for vehicle routing problems (VRPs) with time window constraints as applied to RMC dispatching problems and examine the performance of the approach for this specific application domain. The objective of the problem is to find the minimum cost routes for a fleet of capacitated vehicles serving concrete to customers with known demand from depots within the allowable time window. The VRP is specified to cover the concrete delivery problem by adding additional constraints that reflect real situations. The introduced model is amenable to the Dantzig–Wolfe reformulation for solving pricing problems using a two‐staged methodology as proposed in this article. Further, under the mild assumption of homogeneity of the vehicles, the pricing sub‐problem can be viewed as a minimum‐cost multi‐commodity flow problem and solved in polynomial time using efficient network simplex method implementations. A large‐scale field collect data set is used for evaluating the model and the proposed solution method, with and without time window constraints. In addition, the method is compared with the exact solution found via enumeration. The results show that on average the proposed methodology attains near optimal solutions for many of the large sized models but is 10 times faster than branch‐and‐cut.     

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.     

Patrol Route Planning for Incident Response Vehicles under Dispatching Station Scenarios

Traffic incidents often contribute to major safety concerns, impose additional congestion in the neighboring transportation networks, and induce indirect costs to economy. As roughly a third of traffic crashes are secondary accidents, effective incident management activities are critical, especially on roadways with high traffic volume, to detect, respond to, and clean up incidents in a timely fashion, which supports safety constraints and restores traffic capacity in the transportation network. Hence, it is beneficial to simultaneously plan for first respondents’ dispatching station location and patrol route design to mitigate congestion. This article presents an optimal route planning for patrolling vehicles to facilitate quick response to potential accidents. A mixed‐integer nonlinear program is proposed that minimizes the respondents’ patrolling travel cost based on the expected maximum response time from each arbitrary location to all incident locations (a.k.a. hotspots) with various incident occurrence probabilities. We have developed a column generation‐based solution technique to solve the route optimization model under different station design scenarios. To investigate the impact of dispatching station design on the routing cost, an integrated genetic algorithm framework with embedded continuous approximation approach is developed that reduces the complexity of the hybrid location design and route planning problem. Numerical experiments on hypothetical networks of various sizes are conducted to indicate the performance of the proposed algorithm and to draw managerial insights. The models and solution techniques, developed in this article, are applicable to a number of network problems that simultaneously involve routing and facility location choices.     

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 network traffic assignment model for autonomous vehicles with parking choices

This article is the first in the literature to investigate the network traffic equilibrium for traveling and parking with autonomous vehicles (AVs) under a fully automated traffic environment. Given that AVs can drop off the travelers at their destinations and then drive to the parking spaces by themselves, we introduce the joint equilibrium of AV route choice and parking location choice, and develop a variational inequality (VI)‐based formulation for the proposed equilibrium. We prove the equivalence between the proposed VI model and the defined equilibrium conditions. We also show that the link flow solution at equilibrium is unique, even though both the route choices and parking choices are endogenous when human‐occupied AV trips (from origin to destination) and empty AV trips (from destination to parking) are interacting with each other on the same network. We then develop a solution methodology based on the parking‐route choice structure, where we adjust parking choices in the upper level and route choices in the lower level. Numerical analysis is conducted to explore insights from the introduced modeling framework for AV network equilibrium. The results reveal the significant difference in network equilibrium flows between the AV and non‐AV situations. The results also indicate the sensitivity of the AV traffic pattern to different factors, such as value of time, parking pricing, and supply. The proposed approach provides a critical modeling device for studying the traffic equilibrium under AV behavior patterns, which can be used for the assessment of parking policies and infrastructure development in the future era of AVs.     

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.     

Methodology for spatio‐temporal predictions of traffic counts across an urban road network and generation of an on‐road greenhouse gas emission inventory

On‐road emission inventories in urban areas have typically been developed using traffic data derived from travel demand models. These approaches tend to underestimate emissions because they often only incorporate data on household travel, not including commercial vehicle movements, taxis, ride hailing services, and other trips typically underreported within travel surveys. In contrast, traffic counts embed all types of on‐road vehicles; however, they are only conducted at selected locations in an urban area. Traffic counts are typically spatially correlated, which enables the development of methods that can interpolate traffic data at selected monitoring stations across an urban road network and in turn develop emission estimates. This paper presents a new and universal methodology designed to use traffic count data for the prediction of periodic and annual volumes as well as greenhouse gas emissions at the level of each individual roadway and for multiple years across a large road network. The methodology relies on the data collected and the spatio‐temporal relationships between traffic counts at various stations; it recognizes patterns in the data and identifies locations with similar trends. Traffic volumes and emissions prediction can be made even on roads where no count data exist. Data from the City of Toronto traffic count program were used to validate the output of various algorithms, indicating robust model performance, even in areas with limited data.     

Real‐Time Estimation of Pollution Emissions and Dispersion from Highway Traffic

Traffic‐related air pollution is a serious problem with significant health impacts in both urban and suburban environments. Despite an increased realization of the negative impacts of air pollution, assessing individuals' exposure to traffic‐related air pollution remains a challenge. Obtaining high‐resolution estimates are difficult due to the spatial and temporal variability of emissions, the dependence on local atmospheric conditions, and the lack of monitoring infrastructure. This presents a significant hurdle to identifying pollution concentration hot spots and understanding the emission sources responsible for these hot spots, which in turn makes it difficult to reduce the uncertainty of health risk estimates for communities and to develop policies that mitigate these risks. We present a novel air pollution estimation method that models the highway traffic state, highway traffic‐induced air pollution emissions, and pollution dispersion, and describe a prototype implementation for the San Francisco Bay Area. Our model is based on the availability of real‐time traffic estimates on highways, which we obtain using a traffic dynamics model and an estimation algorithm that augments real‐time data from both fixed sensors and probe vehicles. These traffic estimates combined with local weather conditions are used as inputs to an emission model that estimates pollutant levels for multiple gases and particulates in real‐time. Finally, a dispersion model is used to assess the spread of these pollutants away from the highway source. Maps generated using the output of the dispersion model allow users to easily analyze the evolution of individual pollutants over time, and provides transportation engineers and public health officials with valuable information that can be used to minimize health risks.     

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.     

Strategies to Enhance the Performance of Path‐Based Static Traffic Assignment Algorithms

There are three important stages of path‐based algorithms (PBAs) for solving the static user equilibrium traffic assignment problem (STA): finding shortest paths between various origins and destinations based on the present flow conditions to update the path set, updating path flows based on the move direction of the PBA, and updating the link flows and costs. This article proposes strategies to improve the computational efficiency of these three stages. The first strategy provides a simple method to preclude the through‐routing via the zone centroid and helps to avoid unrealistic flow without affecting the flow update process of a PBA. The second strategy seeks to improve the efficiency of the path flow update process by circumventing unnecessary computation. The third strategy proposes faster link flow and link cost update processes along with a link data structure to support it. The computational experiments using two recently developed PBAs validate the effectiveness of these strategies and help to understand their rationale. The strategies are significant from both theoretical and practical perspectives. From a theoretical viewpoint, they help in designing an efficient execution process for PBAs and provide an improved common platform for comparing their performances. For practice, they can reduce the computational cost in finding the solution of the STA without increasing the complexity of the execution of the algorithm.     

Solving Detour‐Based Fuel Stations Location Problems

This article studies the problem of locating fuel stations to minimize the extra cost spent in refueling detours, which belongs to a class of discretionary service facility location problems. Unlike many studies of similar problems in the literature, the proposed model considers capacity constraints and compares different ways to incorporate them in the formulation. Note that ignoring the capacity constraint results in nonoptimal and unrealistic solutions. The proposed models are solved using both an off‐the‐shelf solver (CPLEX) and a specialized meta‐heuristic method (Simulated Annealing) developed in this study. The solution methods are tested and compared in two case studies; a test benchmark network and a large‐scale network. An effort to overcome the memory limitation of CPLEX through more compact formulation was partially successful: it results in a model that is less tightly bounded by its linear relaxation and hence is much more difficult to solve. In contrast, the Simulated Annealing algorithm scales better and is able to consistently yield high‐quality solutions with a reasonable amount of computation time.