System optimal dynamic traffic assignment: Properties and solution procedures in the case of a many-to-one network

Thanks to its high dimensionality and a usually non-convex constraint set, system optimal dynamic traffic assignment remains one of the most challenging problems in transportation research. This paper identifies two fundamental properties of the problem and uses them to design an efficient solution procedure. We first show that the non-convexity of the problem can be circumvented by first solving a relaxed problem and then applying a traffic holding elimination procedure to obtain the solution(s) of the original problem. To efficiently solve the relaxed problem, we explore the relationship between the relaxed problems based on different traffic flow models (PQ, SQ, CTM) and a minimal cost flow (MCF) problem for a special space-expansion network. It is shown that all the four problem formulations produce the same minimal system cost and share one common solution which does not involve inside queues in the network. Efficient solution algorithms such as the network simplex method can be applied to solve the MCF problem and identify such an optimal traffic pattern. Numerical examples are also presented to demonstrate the efficiency of the proposed solution procedure.     

Cooperative traffic control of a mixed network with two urban regions and a freeway

Currently most optimization methods for urban transport networks (i) are suited for networks with simplified dynamics that are far from real-sized networks or (ii) apply decentralized control, which is not appropriate for heterogeneously loaded networks or (iii) investigate good-quality solutions through micro-simulation models and scenario analysis, which make the problem intractable in real time. In principle, traffic management decisions for different sub-systems of a transport network (urban, freeway) are controlled by operational rules that are network specific and independent from one traffic authority to another. In this paper, the macroscopic traffic modeling and control of a large-scale mixed transportation network consisting of a freeway and an urban network is tackled. The urban network is partitioned into two regions, each one with a well-defined Macroscopic Fundamental Diagram (MFD), i.e. a unimodal and low-scatter relationship between region density and outflow. The freeway is regarded as one alternative commuting route which has one on-ramp and one off-ramp within each urban region. The urban and freeway flow dynamics are formulated with the tool of MFD and asymmetric cell transmission model, respectively. Perimeter controllers on the border of the urban regions operating to manipulate the perimeter interflow between the two regions, and controllers at the on-ramps for ramp metering are considered to control the flow distribution in the mixed network. The optimal traffic control problem is solved by a Model Predictive Control (MPC) approach in order to minimize total delay in the entire network. Several control policies with different levels of urban-freeway control coordination are introduced and tested to scrutinize the characteristics of the proposed controllers. Numerical results demonstrate how different levels of coordination improve the performance once compared with independent control for freeway and urban network. The approach presented in this paper can be extended to implement efficient real-world control strategies for large-scale mixed traffic networks.     

Dynamic traffic metering in urban street networks: Formulation and solution algorithm

Traffic metering offers great potential to reduce congestion and enhance network performance in oversaturated urban street networks. This paper presents an optimization program for dynamic traffic metering in urban street networks based on the Cell Transmission Model (CTM). We have formulated the problem as a Mixed-Integer Linear Program (MILP) capable of metering traffic at network gates with given signal timing parameters at signalized intersections. Due to the complexities of the MILP model, we have developed a novel and efficient solution approach that solves the problem by converting the MILP to a linear program and several CTM simulation runs. The solution algorithm is applied to two case studies under different conditions. The proposed solution technique finds solutions that have a maximum gap of 1% of the true optimal solution and guarantee the maximum throughput by keeping some vehicles at network gates and only allowing enough vehicles to enter the network to prevent gridlocks. This is confirmed by comparing the case studies with and without traffic metering. The results in an adapted real-world case study network show that traffic metering can increase network throughput by 4.9–38.9% and enhance network performance.     

Optimizing one‐way traffic network reconfiguration and lane‐based non‐diversion routing for evacuation

Unfortunately, situations such as flood, hurricanes, chemical accidents, and other events occur frequently more and more. To improve the efficiency and practicality of evacuation management plan, an integrated optimization model of one‐way traffic network reconfiguration and lane‐based non‐diversion routing with crossing elimination at intersection for evacuation is constructed in this paper. It is an integrated model aiming at minimizing the network clearance time based on Cell Transmission Model. A hybrid algorithm with modified genetic algorithm and tabu search method is devised for approximating optimal problem solutions. To verify the effectiveness of the proposed model and solving method, two cases are illustrated in this paper. Through the first example, it can be seen that the proposed model and algorithm can effectively solve the integrated problems, and compared with the objective value of the original network, the network clearance time of the final solution reduces by 47.4%. The calculation results for the realistic topology and size network of Ningbo in China, which locates on the east coast of the Pacific Ocean, justify the practical value of the model and solution method, and solutions under different settings of reduction amount of merging cell capacity embody obvious differences. Copyright © 2015 John Wiley & Sons, Ltd.     

Store-and-forward based methods for the signal control problem in large-scale congested urban road networks

The problem of designing network-wide traffic signal control strategies for large-scale congested urban road networks is considered. One known and two novel methodologies, all based on the store-and-forward modeling paradigm, are presented and compared. The known methodology is a linear multivariable feedback regulator derived through the formulation of a linear-quadratic optimal control problem. An alternative, novel methodology consists of an open-loop constrained quadratic optimal control problem, whose numerical solution is achieved via quadratic programming. Yet a different formulation leads to an open-loop constrained nonlinear optimal control problem, whose numerical solution is achieved by use of a feasible-direction algorithm. A preliminary simulation-based investigation of the signal control problem for a large-scale urban road network using these methodologies demonstrates the comparative efficiency and real-time feasibility of the developed signal control methods.     

A sensitivity-based approach for adaptive decomposition of anticipatory network traffic control

Anticipatory optimal network control is defined as the problem of determining the set of control actions that minimizes a network-wide objective function. This not only takes into account local consequences on the propagation of flows, but also the global network-wide routing behavior of the users. Such an objective function is, in general, defined in a centralized setting, as knowledge regarding the whole network is needed to correctly compute it. Reaching a level of centralization sufficient to attain network-wide control objectives is however rarely realistic in practice. Multiple authorities are influencing different portions the network, separated either hierarchically or geographically. The distributed nature of networks and traffic directly influences the complexity of the anticipatory control problem.This is our motivation for this work, in which we introduce a decomposition mechanism for the global anticipatory network traffic control problem, based on dynamic clustering of traffic controllers. Rather than solving the full centralized problem, or blindly performing a full controller-wise decomposition, this technique allows recognizing when and which controllers should be grouped in clusters, and when, instead, these can be optimized separately.The practical relevance with respect to our motivation is that our approach allows identification of those network traffic conditions in which multiple actors need to actively coordinate their actions, or when unilateral action suffices for still approximating global optimality.This clustering procedure is based on well-known algebraic and statistical tools that exploit the network’s sensitivity to control and its structure to deduce coupling behavior. We devise several case studies in order to assess our newly introduced procedure’s performances, in comparison with fully decomposed and fully centralized anticipatory optimal network control, and show that our approach is able to outperform both centralized and decomposed procedures.     

Multi-scale perimeter control approach in a connected-vehicle environment

This paper proposes a novel approach to integrate optimal control of perimeter intersections (i.e. to minimize local delay) into the perimeter control scheme (i.e. to optimize traffic performance at the network level). This is a complex control problem rarely explored in the literature. In particular, modeling the interaction between the network level control and the local level control has not been fully considered. Utilizing the Macroscopic Fundamental Diagram (MFD) as the traffic performance indicator, we formulate a dynamic system model, and design a Model Predictive Control (MPC) based controller coupling two competing control objectives and optimizing the performance at the local and the network level as a whole. To solve this highly non-linear optimization problem, we employ an approximation framework, enabling the optimal solution of this large-scale problem to be feasible and efficient. Numerical analysis shows that by applying the proposed controller, the protected network can operate around the desired state as expressed by the MFD, while the total delay at the perimeter is minimized as well. Moreover, the paper sheds light on the robustness of the proposed controller. This multi-scale hybrid controller is further extended to a stochastic MPC scheme, where connected vehicles (CV) serve as the only data source. Hence, low penetration rates of CVs lead to strong noises in the controller. This is a first attempt to develop a network-level traffic control methodology by using the emerging CV technology. We consider the stochasticity in traffic state estimation and the shape of the MFD. Simulation analysis demonstrates the robustness of the proposed stochastic controller, showing that efficient controllers can indeed be designed with this newly-spread vehicle technology even in the absence of other data collection schemes (e.g. loop detectors).     

Distributed optimization and coordination algorithms for dynamic speed optimization of connected and autonomous vehicles in urban street networks

Dynamic speed harmonization has shown great potential to smoothen the flow of traffic and reduce travel time in urban street networks. The existing methods, while providing great insights, are neither scalable nor real-time. This paper develops Distributed Optimization and Coordination Algorithms (DOCA) for dynamic speed optimization of connected and autonomous vehicles in urban street networks to address this gap. DOCA decomposes the nonlinear network-level speed optimization problem into several sub-network-level nonlinear problems thus, it significantly reduces the problem complexity and ensures scalability and real-time runtime constraints. DOCA creates effective coordination in decision making between each two sub-network-level nonlinear problems to push solutions towards optimality and guarantee attaining near-optimal solutions. DOCA is incorporated into a model predictive control approach to allow for additional consensus between sub-network-level problems and reduce the computational complexity further. We applied the proposed solution technique to a real-world network in downtown Springfield, Illinois and observed that it was scalable and real-time while finding solutions that were at most 2.7% different from the optimal solution of the problem. We found significant improvements in network operations and considerable reductions in speed variance as a result of dynamic speed harmonization.     

Traffic guidance–perimeter control coupled method for the congestion in a macro network

Macroscopic fundamental diagram (MFD) describes the macro relationship between a network vehicle density and a network space mean flow, without requiring the mastery of complex origin to destination data. Thus, MFD provides an opportunity for the macro control of urban road network. However, most of the existing MFD control methods ignore the active role of traffic guidance in solving congestion problems. This study presents a traffic guidance–perimeter control coupled (TGPCC) method to improve the performance of macroscopic traffic networks. The method considers the optimal cumulative volume of a network as the goal and establishes a programming function according to the network equilibrium rule of traffic flow amongst multiple MFD sub-regions, which regards the minimum delay of network, as the objective. The Logit model for the compliance rate of driver route guidance is established by the stated preference survey. Moreover, the perimeter control (PC) method is proposed for adjusting the phase split of intersections. Finally, three schemes, namely, the TGPCC, PC and the method without PC and guidance are tested on a network with four well-defined MFD sub-regions. Results show that the TGPCC addresses the issue of congestion and decreases the total delay accordingly.     

A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

Connectivity-based optimization of vehicle route and speed for improved fuel economy

Traditionally, vehicle route planning problem focuses on route optimization based on traffic data and surrounding environment. This paper proposes a novel extended vehicle route planning problem, called vehicle macroscopic motion planning (VMMP) problem, to optimize vehicle route and speed simultaneously using both traffic data and vehicle characteristics to improve fuel economy for a given expected trip time. The required traffic data and neighbouring vehicle dynamic parameters can be collected through the vehicle connectivity (e.g. vehicle-to-vehicle, vehicle-to-infrastructure, vehicle-to-cloud, etc.) developed rapidly in recent years. A genetic algorithm based co-optimization method, along with an adaptive real-time optimization strategy, is proposed to solve the proposed VMMP problem. It is able to provide the fuel economic route and reference speed for drivers or automated vehicles to improve the vehicle fuel economy. A co-simulation model, combining a traffic model based on SUMO (Simulation of Urban MObility) with a Simulink powertrain model, is developed to validate the proposed VMMP method. Four simulation studies, based on a real traffic network, are conducted for validating the proposed VMMP: (1) ideal traffic environment without traffic light and jam for studying the fuel economy improvement, (2) traffic environment with traffic light for validating the proposed traffic light penalty model, (3) traffic environment with traffic light and jam for validating the proposed adaptive real-time optimization strategy, and (4) investigating the effect of different powertrain platforms to fuel economy using two different vehicle platforms. Simulation results show that the proposed VMMP method is able to improve vehicle fuel economy significantly. For instance, comparing with the fastest route, the fuel economy using the proposed VMMP method is improved by up to 15%.     

Globally energy-optimal speed planning for road vehicles on a given route

This paper provides a globally optimal solution to an important problem: given a real-world route, what is the most energy-efficient way to drive a vehicle from the origin to the destination within a certain period of time. Along the route, there may be multiple stop signs, traffic lights, turns and curved segments, roads with different grades and speed limits, and even leading vehicles with pre-known speed profiles. Most of such route information and features are actually constraints to the optimal vehicle speed control problem, but these constraints are described in two different domains. The most important concept in solving this problem is to convert the distance-domain route constraints to some time-domain state and input constraints that can be handled by optimization methods such as dynamic programming (DP). Multiple techniques including cost-to-go function interpolation and parallel computing are used to reduce the computation of DP and make the problem solvable within a reasonable amount of time on a personal computer.     

Machine learning for multi-jurisdictional optimal traffic corridor control

Urban traffic corridors are often controlled by more than one agency. Typically in North America, a state of provincial transportation department controls freeways while another agency at the municipal or city level controls the nearby arterials. While the different segments of the corridor fall under different jurisdictions, traffic and users know no boundaries and expect seamless service. Common lack of coordination amongst those authorities due to lack of means for information exchange and/or possible bureaucratic ‘institutional grid-lock’ could hinder the full potential of technically-possible integrated control. Such institutional gridlock and related lack of timely coordination amongst the different agencies involved can have a direct impact on traffic gridlock. One potential solution to this problem is through integrated automatic control under intelligent transportation systems (ITS). Advancements in ITS and communication technology have the potential to considerably reduce delay and congestion through an array of network-wide traffic control and management strategies that can seamlessly cross-jurisdictional boundaries. Perhaps two of the most promising such control tools for freeway corridors are traffic-responsive ramp metering and/or dynamic traffic diversion possibly using variable message signs (VMS). Technically, the use of these control methods separately might limit their potential usefulness. Therefore, integrated corridor control using ramp metering and VMS diversion simultaneously might be synergetic and beneficial. Motivated by the above problem and potential solution approach, the aim of the research presented in this paper is to develop a self-learning adaptive integrated freeway-arterial corridor control for both recurring and non-recurring congestion. The paper introduces the use of reinforcement learning, an Artificial Intelligence method for machine learning, to provide optimal control using ramp metering and VMS routing in an integrated agent for a freeway-arterial corridor. Reinforcement learning is an approach whereby the control agent directly learns optimal strategies via feedback reward signals from its environment. A simple but powerful reinforcement learning method known as Q-learning is used. Results from an elaborate simulation study on a key corridor in Toronto are very encouraging and discussed in the paper.     

Intermodal freight transport planning – A receding horizon control approach

This paper investigates intermodal freight transport planning problems among deep-sea terminals and inland terminals in hinterland haulage for a horizontally fully integrated intermodal freight transport operator at the tactical container flow level. An intermodal freight transport network (IFTN) model is first developed to capture the key characteristics of intermodal freight transport such as the modality change phenomena at intermodal terminals, physical capacity constraints of the network, time-dependent transport times on freeways, and time schedules for trains and barges. After that, the intermodal freight transport planning problem is formulated as an optimal intermodal container flow control problem from a system and control perspective with the use of the proposed IFTN model. To deal with the dynamic transport demands and dynamic traffic conditions in the IFTN, a receding horizon intermodal container flow control (RIFC) approach is proposed to control and to reassign intermodal container flows in a receding horizon way. This container flow control approach involves solving linear programming problems and is suited for transport planning on large-sized networks. Both an all-or-nothing approach and the proposed RIFC approach are evaluated through simulation studies. Simulation results show the potential of the proposed RIFC approach.     

A Topological Method to Choose Optimal Solutions after Solving the Multi-criteria Urban Road Network Design Problem

The paper proposes and applies a method for systematically sorting and reducing the number of different possible solutions to a network design problem (NDP). This is achieved first by defining a topological similarity measurement and then by applying cluster analysis. The NDP can be derived from the scientific literature. In general, the method consists of some models and subsequent algorithms that generate different solutions (enumerative, branch and bound, genetic, expert panel, ...) and evaluate for each solution an objective function (with deterministic or stochastic network assignment and with elastic or inelastic demand). The NDP, mainly in urban areas, needs multi-criteria evaluation and in each case a large set of non-dominated solutions is generated. In this paper, in order to select solutions and identify latent optimal network layouts, cluster analysis is carried out. The methodology utilises a “cluster” formation in relation to the solution topology and a “best” (representative) solutions extraction in relation to the criteria values. It can be utilised after solving the existing multi-criteria NDP and in other network problems, where the best solutions (for global or local network layouts) are extracted (with respect to the network topology) from a large set. The method is applied in a test system and on different real networks in two Italian towns, in order to analyse the goodness of the solution algorithm and assess its possible application to different networks.     

Selection of a trip table which reproduces observed link flows

In urban traffic management and planning, an important problem is estimating the number of drivers traveling between each origin-destination zone. We review a model due to Nguyen for estimating these numbers of drivers, based on counts of the traffic flows on each street, and develop an effective algorithm for solving it. The multiplicity of solutions of this model poses the additional question of which solution to use; we introduce a secondary optimization problem to overcome this difficulty. Efficient solution techniques are described for these problems and computational results are reported. It is noted that the most efficient solution methods involve user interaction to specify values of parameters which improve the convergence rates.     

Modeling and solving discrete network design problem with stochastic user equilibrium

In this paper, we address the discrete network design problem, which determines the addition of new roads to existing transportation network to optimize the transportation system performance. Road users are assumed to follow the traffic assignment principle of stochastic user equilibrium. A mixed‐integer nonlinear nonconvex problem is developed to model this discrete network design problem with stochastic user equilibrium. The original problem is relaxed into a convex mixed‐integer nonlinear program, whose solution provides a lower bound of the original problem. The relaxed problem is then embedded into two proposed global optimization solution algorithms to obtain the global optimal solution of the problem. Copyright © 2016 John Wiley & Sons, Ltd.     

A new approach to time-of-day control based on a dynamic freeway traffic model

This paper presents a new approach to time-of-day control. While time-of-day control strategies presented up-to-now are only optimal under steady-state conditions, the control algorithm derived in this paper takes into account the evolution of traffic flow according to the time delay between a volume change at a ramp and its subsequent disturbance at a freeway point downstream. The new control strategy is based on the solution of a linear programming optimization problem and makes freeway volume hold the capacity constraints for the total time of control operation. In order to reduce the computational effort a simplified version of the new algorithm is also discussed. Simulation results obtained by use of two different traffic flow models show that control derived through the new algorithm can avoid congestion and ensure operation with peak performance even if a steady-state condition is never attained.     

A semi-analytical approach for solving the bottleneck model with general user heterogeneity

This paper proposes a novel semi-analytical approach for solving the dynamic user equilibrium (DUE) of a bottleneck model with general heterogeneous users. The proposed approach makes use of the analytical solutions from the bottleneck analysis to create an equivalent assignment problem that admits closed-form commute cost functions. The equivalent problem is a static and asymmetric traffic assignment problem, which can be formulated as a variational inequality problem (VIP). This approach provides a new tool to analyze the properties of the bottleneck model with general heterogeneity, and to design efficient solution methods. In particular, the existence and uniqueness of the DUE solution can be established using the P-property of the Jacobian matrix. Our numerical experiments show that a simple decomposition algorithm is able to quickly solve the equivalent VIP to high precision. The proposed VIP formation is also extended to address simultaneous departure time and route choice in a single O–D origin-destination network with multiple parallel routes.     

Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation

Allocating movable resources dynamically enables evacuation management agencies to improve evacuation system performance in both the spatial and temporal dimensions. This study proposes a mixed integer linear program (MILP) model to address the dynamic resource allocation problem for transportation evacuation planning on large-scale networks. The proposed model is built on the earliest arrival flow formulation that significantly reduces problem size. A set of binary variables, specifically, the beginning and the ending time of resource allocation at a location, enable a strong formulation with tight constraints. A solution algorithm is developed to solve for an optimal solution on large-scale network applications by adopting Benders decomposition. In this algorithm, the MILP model is decomposed into two sub-problems. The first sub-problem, called the restricted master problem, identifies a feasible dynamic resource allocation plan. The second sub-problem, called the auxiliary problem, models dynamic traffic assignment in the evacuation network given a resource allocation plan. A numerical study is performed on the Dallas–Fort Worth network. The results show that the Benders decomposition algorithm can solve an optimal solution efficiently on a large-scale network.