The estimation of a time-dependent OD trip table with vehicle trajectory samples

Abstract

In this paper we discuss a dynamic origin–destination (OD) estimation problem that has been used for identifying time-dependent travel demand on a road network. Even though a dynamic OD table is an indispensable data input for executing a dynamic traffic assignment, it is difficult to construct using the conventional OD construction method such as the four-step model. For this reason, a direct estimation method based on field traffic data such as link traffic counts has been used. However, the method does not account for a logical relationship between a travel demand pattern and socioeconomic attributes. In addition, the OD estimation method cannot guarantee the reliability of estimated results since the OD estimation problem has a property named the ‘underdetermined problem.’ In order to overcome such a problem, the method developed in this paper makes use of vehicle trajectory samples with link traffic counts. The new method is applied to numerical examples and shows promising capability for identifying a temporal and spatial travel demand pattern.     

An efficient algorithm for smoothing airspace congestion by fine-tuning take-off times

Current technological advances in communications and navigation have improved air traffic management (ATM) with new decision support tools to balance airspace capacity with user demands. Despite agreements achieved in flying reference business trajectories (RBTs) among different stakeholders, tight spatio-temporal connectivity between trajectories in dense sectors can cause perturbations that might introduce time or space deviations into the original RBTs, thus potentially affecting other 4D trajectories. In this paper, several challenging results are presented by properly tuning the Calculated Take-Off Times (CTOTs) as a tool for mitigating the propagation of perturbations between trajectories that can readily appear in dense sectors. Based on the identification of “collective microregions”, a tool for predicting potential spatio-temporal concurrence events between trajectories over the European airspace was developed, together with a CTOT algorithm to sequence the departures that preserve the scheduled slots while relaxing tight trajectory interactions. The algorithm was tested by considering a realistic scenario (designed and analyzed in the STREAM project (Stream, 2013)) to evaluate relevant ATM KPIs that provide aggregated information about the sensitivity of the system to trajectory interactions, taking into account the system dynamics at a network level. The proposed approach contributes to enhancing the ATM capacity of airports to mitigate network perturbations.     

Aircraft trajectory forecasting using local functional regression in Sobolev space

This paper considers the problem of short to mid-term aircraft trajectory prediction, that is, the estimation of where an aircraft will be located over a 10–30 min time horizon. Such a problem is central in decision support tools, especially in conflict detection and resolution algorithms. It also appears when an air traffic controller observes traffic on the radar screen and tries to identify convergent aircraft, which may be in conflict in the near future. An innovative approach for aircraft trajectory prediction is presented in this paper. This approach is based on local linear functional regression that considers data preprocessing, localizing and solving linear regression using wavelet decomposition. This algorithm takes into account only past radar tracks, and does not use any physical or aeronautical parameters. This approach has been successfully applied to aircraft trajectories between several airports on the data set that is one year air traffic over France. The method is intrinsic and independent from airspace structure.     

A hybrid machine learning model for short-term estimated time of arrival prediction in terminal manoeuvring area

4D trajectory prediction is the core element of future air transportation system, which is intended to improve the operational ability and the predictability of air traffic. In this paper, we introduce a novel hybrid model to address the short-term trajectory prediction problem in Terminal Manoeuvring Area (TMA) by application of machine learning methods. The proposed model consists of two parts: clustering-based preprocessing and Multi-Cells Neural Network (MCNN)-based prediction. Firstly, in the preprocessing part, after data cleaning, filtering and data re-sampling, we applied principal Component Analysis (PCA) to reduce the dimension of trajectory vector variable. Then, the trajectories are clustered into several patterns by clustering algorithm. Using nested cross validation, MCNN model is trained to find out the appropriate prediction model of Estimated Time of Arrival (ETA) for each individual cluster cell. Finally, the predicted ETA for each new flight is generated in different cluster cells classified by decision trees. To assess the performance of MCNN model, the Multiple Linear Regression (MLR) model is proposed as the comparison learning model, and K-means++ and DBSCAN are proposed as two comparison clustering models in preprocessing part. With real 4D trajectory data in Beijing TMA, experimental results demonstrate that our proposed model MCNN with DBSCAN in preprocessing is the most effective and robust hybrid machine learning model, both in trajectory clustering and short-term 4D trajectory prediction. In addition, it can make an accurate trajectory prediction in terms of Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) with regards to comparison models.     

Convexity and robustness of dynamic traffic assignment and freeway network control

We study the use of the System Optimum (SO) Dynamic Traffic Assignment (DTA) problem to design optimal traffic flow controls for freeway networks as modeled by the Cell Transmission Model, using variable speed limit, ramp metering, and routing. We consider two optimal control problems: the DTA problem, where turning ratios are part of the control inputs, and the Freeway Network Control (FNC), where turning ratios are instead assigned exogenous parameters. It is known that relaxation of the supply and demand constraints in the cell-based formulations of the DTA problem results in a linear program. However, solutions to the relaxed problem can be infeasible with respect to traffic dynamics. Previous work has shown that such solutions can be made feasible by proper choice of ramp metering and variable speed limit control for specific traffic networks. We extend this procedure to arbitrary networks and provide insight into the structure and robustness of the proposed optimal controllers. For a network consisting only of ordinary, merge, and diverge junctions, where the cells have linear demand functions and affine supply functions with identical slopes, and the cost is the total traffic volume, we show, using the Pontryagin maximum principle, that variable speed limits are not needed in order to achieve optimality in the FNC problem, and ramp metering is sufficient. We also prove bounds on perturbation of the controlled system trajectory in terms of perturbations in initial traffic volume and exogenous inflows. These bounds, which leverage monotonicity properties of the controlled trajectory, are shown to be in close agreement with numerical simulation results.     

A linear programming-based method for the network revenue management problem of air cargo

One critical operational issue of air cargo operation faced by airlines is the control over the sales of their limited cargo space. Since American Airlines’ successful implementation in the post-deregulation era, revenue management (RM) has become a common practice for the airline industry. However, unlike the air passenger operation supported by well-developed RM systems with advanced decision models, the decision process in selling air cargo space to freight forwarders is usually based on experience, without much support from optimization techniques. This study first formulates a multi-dimensional dynamic programming (DP) model to present a network RM problem for air cargo. In order to overcome the computational challenge, this study develops two linear programming (LP) based models to provide the decision support operationally suitable for airlines. In addition, this study further introduces a dynamic adjustment factor to alleviate the inaccuracy problem of the static LP models in estimating resource opportunity cost. Finally, a numerical experiment is performed to validate the applicability of the developed model and solution algorithm to the real-world problems.     

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.     

Feedback control speed harmonization algorithm: Methodology and preliminary testing

The capacity drop phenomenon, which reduces the maximum bottleneck discharge rate following the onset of congestion, is a critical restriction in transportation networks that produces additional traffic congestion. Consequently, preventing or reducing the occurrence of the capacity drop not only mitigates traffic congestion, but can also produce environmental and traffic safety benefits. In addressing this problem, the paper develops a novel bang-bang feedback control speed harmonization (SH) or Variable Speed Limit (VSL) algorithm, that attempts to prevent or delay the breakdown of a bottleneck and thus reduce traffic congestion. The novelty of the system lies in the fact that it is both proactive and reactive in responding to the dynamic stochastic nature of traffic. The system is proactive because it uses a calibrated fundamental diagram to initially identify the optimum throughput to maintain within the SH zone. Furthermore, the system is reactive (dynamic) because it monitors the traffic stream directly upstream of the bottleneck to adjustment the metering rate to capture the dynamic and stochastic nature of traffic. The steady-state traffic states in the vicinity of a lane-drop bottleneck before and after applying the SH algorithm is analyzed to demonstrate the effectiveness of the algorithm in alleviating the capacity drop. We demonstrate theoretically that the SH algorithm is effective in enhancing the bottleneck discharge rate. A microscopic simulation of the network using the INTEGRATION software further demonstrates the benefits of the algorithm in increasing the bottleneck discharge rate, decreasing vehicle delay, and reducing vehicle fuel consumption and CO₂ emission levels. Specifically, compared with the base case without the SH algorithm, the advisory speed limit increases the bottleneck discharge rate by approximately 7%, reduces the overall system delay by approximately 20%, and reduces the system-wide fuel consumption and CO₂ emission levels by 5%.     

Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories

This paper presents a trajectory clustering method to discover spatial and temporal travel patterns in a traffic network. The study focuses on identifying spatially distinct traffic flow groups using trajectory clustering and investigating temporal traffic patterns of each spatial group. The main contribution of this paper is the development of a systematic framework for clustering and classifying vehicle trajectory data, which does not require a pre-processing step known as map-matching and directly applies to trajectory data without requiring the information on the underlying road network. The framework consists of four steps: similarity measurement, trajectory clustering, generation of cluster representative subsequences, and trajectory classification. First, we propose the use of the Longest Common Subsequence (LCS) between two vehicle trajectories as their similarity measure, assuming that the extent to which vehicles’ routes overlap indicates the level of closeness and relatedness as well as potential interactions between these vehicles. We then extend a density-based clustering algorithm, DBSCAN, to incorporate the LCS-based distance in our trajectory clustering problem. The output of the proposed clustering approach is a few spatially distinct traffic stream clusters, which together provide an informative and succinct representation of major network traffic streams. Next, we introduce the notion of Cluster Representative Subsequence (CRS), which reflects dense road segments shared by trajectories belonging to a given traffic stream cluster, and present the procedure of generating a set of CRSs by merging the pairwise LCSs via hierarchical agglomerative clustering. The CRSs are then used in the trajectory classification step to measure the similarity between a new trajectory and a cluster. The proposed framework is demonstrated using actual vehicle trajectory data collected from New York City, USA. A simple experiment was performed to illustrate the use of the proposed spatial traffic stream clustering in application areas such as network-level traffic flow pattern analysis and travel time reliability analysis.     

Managing Traffic by Privatization of Road Capacity: A Property Rights Approach

Abstract

Road congestion remains a serious problem, despite all the efforts to limit road use and to manage growing road traffic volumes. Economic approaches (such as pricing) are introduced based on traditional welfare economic theory. Although they are sometimes very successful, the magnitude of traffic issues also requires alternative and unconventional approaches. Perhaps a more innovative perspective is needed. The paper discusses an alternative economic approach starting from property rights theory. It is translated in transport systems in concepts of infrastructure capacity slot management, where slots are dynamically priced and exclusively allocated to individual users. Debates and practices regarding this approach in air traffic and rail traffic are further developed than in the field of road traffic. The paper aims to explore the potential benefits and disadvantages of the property rights approach for road traffic. Attention is paid to major institutional and technical conditions. The conclusion is that the approach theoretically has clear advantages and seems technologically feasible. Nevertheless, serious political and institutional issues have to be solved first.     

Spatiotemporal intersection control in a connected and automated vehicle environment

Current research on traffic control has focused on the optimization of either traffic signals or vehicle trajectories. With the rapid development of connected and automated vehicle (CAV) technologies, vehicles equipped with dedicated short-range communications (DSRC) can communicate not only with other CAVs but also with infrastructure. Joint control of vehicle trajectories and traffic signals becomes feasible and may achieve greater benefits regarding system efficiency and environmental sustainability. Traffic control framework is expected to be extended from one dimension (either spatial or temporal) to two dimensions (spatiotemporal). This paper investigates a joint control framework for isolated intersections. The control framework is modeled as a two-stage optimization problem with signal optimization at the first stage and vehicle trajectory control at the second stage. The signal optimization is modeled as a dynamic programming (DP) problem with the objective to minimize vehicle delay. Optimal control theory is applied to the vehicle trajectory control problem with the objective to minimize fuel consumption and emissions. A simplified objective function is adopted to get analytical solutions to the optimal control problem so that the two-stage model is solved efficiently. Simulation results show that the proposed joint control framework is able to reduce both vehicle delay and emissions under a variety of demand levels compared to fixed-time and adaptive signal control when vehicle trajectories are not optimized. The reduced vehicle delay and CO₂ emissions can be as much as 24.0% and 13.8%, respectively for a simple two-phase intersection. Sensitivity analysis suggests that maximum acceleration and deceleration rates have a significant impact on the performance regarding both vehicle delay and emission reduction. Further extension to a full eight-phase intersection shows a similar pattern of delay and emission reduction by the joint control framework.     

Estimating traffic volumes for signalized intersections using connected vehicle data

Recently connected vehicle (CV) technology has received significant attention thanks to active pilot deployments supported by the US Department of Transportation (USDOT). At signalized intersections, CVs may serve as mobile sensors, providing opportunities of reducing dependencies on conventional vehicle detectors for signal operation. However, most of the existing studies mainly focus on scenarios that penetration rates of CVs reach certain level, e.g., 25%, which may not be feasible in the near future. How to utilize data from a small number of CVs to improve traffic signal operation remains an open question. In this work, we develop an approach to estimate traffic volume, a key input to many signal optimization algorithms, using GPS trajectory data from CV or navigation devices under low market penetration rates. To estimate traffic volumes, we model vehicle arrivals at signalized intersections as a time-dependent Poisson process, which can account for signal coordination. The estimation problem is formulated as a maximum likelihood problem given multiple observed trajectories from CVs approaching to the intersection. An expectation maximization (EM) procedure is derived to solve the estimation problem. Two case studies were conducted to validate our estimation algorithm. One uses the CV data from the Safety Pilot Model Deployment (SPMD) project, in which around 2800 CVs were deployed in the City of Ann Arbor, MI. The other uses vehicle trajectory data from users of a commercial navigation service in China. Mean absolute percentage error (MAPE) of the estimation is found to be 9–12%, based on benchmark data manually collected and data from loop detectors. Considering the existing scale of CV deployments, the proposed approach could be of significant help to traffic management agencies for evaluating and operating traffic signals, paving the way of using CVs for detector-free signal operation in the future.     

Stochastic eco-routing in a signalized traffic network

In this paper, an eco-routing algorithm is developed for vehicles in a signalized traffic network. The proposed method incorporates a microscopic vehicle emission model into a Markov decision process (MDP). Instead of using GPS-based vehicle trajectory data, which are used by many existing eco-routing algorithm, high resolution traffic data including vehicle arrival and signal status information are used as primary inputs. The proposed method can work with any microscopic vehicle model that uses vehicle trajectories as inputs and gives related emission rates as outputs. Furthermore, a constrained eco-routing problem is proposed to deal with the situation where multiple costs present. This is done by transferring the original MDP based formulation to a linear programming formulation. Besides the primary cost, additional costs are considered as constraints. Two numerical examples are given using the field data obtained from City of Pasadena, California, USA. The eco-routing algorithm for single objective is compared against the traditional shortest path algorithm, Dijkstra’s algorithm. Average reductions of CO emission around 20% are observed.     

An empirical study of simulation-based dynamic traffic assignment procedures

Abstract

Under Intelligent Transportation Systems (ITS), real-time operations of traffic management measures depend on long-term planning results, such as the origin–destination (OD) trip distribution; however, results from current planning procedures are unable to provide fundamental data for dynamic analysis. In order to capture dynamic traffic characteristics, transportation planning models should play an important role to integrate basic data with real-time traffic management and control. In this paper, a heuristic algorithm is proposed to establish the linkage between daily OD trips and dynamic traffic assignment (DTA) procedures; thus results from transportation planning projects, in terms of daily OD trips, can be extended to estimate time-dependent OD trips. Field data from Taiwan are collected and applied in the calibration and validation processes. Dynamic Network Assignment-Simulation Model for Advanced Road Telematics (DYNASMART-P), a simulation-based DTA model, is applied to generate time-dependent flows. The results from the validation process show high agreement between actual flows from vehicle detectors (VDs) and simulated flows from DYNAMSART-P.     

A rolling-horizon quadratic-programming approach to the signal control problem in large-scale congested urban road networks

The paper investigates the efficiency of a recently developed signal control methodology, which offers a computationally feasible technique for real-time network-wide signal control in large-scale urban traffic networks and is applicable also under congested traffic conditions. In this methodology, the traffic flow process is modeled by use of the store-and-forward modeling paradigm, and the problem of network-wide signal control (including all constraints) is formulated as a quadratic-programming problem that aims at minimizing and balancing the link queues so as to minimize the risk of queue spillback. For the application of the proposed methodology in real time, the corresponding optimization algorithm is embedded in a rolling-horizon (model-predictive) control scheme. The control strategy’s efficiency and real-time feasibility is demonstrated and compared with the Linear-Quadratic approach taken by the signal control strategy TUC (Traffic-responsive Urban Control) as well as with optimized fixed-control settings via their simulation-based application to the road network of the city centre of Chania, Greece, under a number of different demand scenarios. The comparative evaluation is based on various criteria and tools including the recently proposed fundamental diagram for urban network traffic.     

A dynamic lane-changing trajectory planning model for automated vehicles

This paper focuses on the lane-changing trajectory planning (LTP) process in the automatic driving technologies. Existing studies on the LTP algorithms are primarily the static planning method in which the states of the surrounding vehicles of a lane-changing vehicle are assumed to keep unchanged in the whole lane-changing process. However, in real-world traffic, the velocities of the surrounding vehicles change dynamically, and the lane-changing vehicle needs to adjust its velocity and positions correspondingly in real-time to maintain safety. To address such limitations, the dynamic lane-changing trajectory planning (DLTP) model is proposed in the limited literature. This paper proposes a novel DLTP model consisting of the lane-changing starting-point determination module, trajectory decision module and trajectory generation module. The model adopts a time-independent polynomial trajectory curve to avoid the unrealistic assumptions on lane-changing velocities and accelerations in the existing DLTP model. Moreover, a rollover-avoidance algorithm and a collision-avoidance algorithm containing a reaction time are presented to guarantee the lane-changing safety of automated vehicles, even in an emergent braking situation. The field lane-changing data from NGSIM data are used to construct a real traffic environment for lane-changing vehicles and verify the effectiveness of the proposed model, and CarSim is applied to investigate the traceability of the planned lane-changing trajectories using the proposed model. The results indicate that an automated vehicle can complete the lane-changing process smoothly, efficiently and safely following the trajectory planned by the proposed model, and the planned velocity and trajectory can be well-tracked by automated vehicles.     

Dynamic airspace sectorisation for flight-centric operations

Today’s air traffic operations follow the paradigm of ‘flow follows structure’, which already limits the operational efficiency and punctuality of current air traffic movements. Therefore, we introduce the dynamic airspace sectorisation and consequently change this paradigm to the more appropriate approach of ‘structure follows flow’. The dynamic airspace sectorisation allows an efficient allocation of scarce resources considering operational, economic and ecological constraints in both nominal and variable air traffic conditions. Our approach clusters traffic patterns and uses evolutionary algorithms for optimisation of the airspace, focusing on high capacity utilisation through flexible use of airspace, appropriate distribution of task load for air traffic controllers and fast adaptation to changed operational constraints. We thereby offer a solution for handling non-convex airspace boundaries and provide a proof of concept using current operational airspace structures and enabling a flight-centric air traffic management. We are confident that our developed dynamic airspace sectorisation significantly contributes to the challenges of future airspace by providing appropriate structures for future 4D aircraft trajectories taking into account various operational aspects of air traffic such as temporally restricted areas, limited capacities, zones of convective weather or urban air mobility. Dynamic sectorisation is a key enabling technology in the achievement of the ambitious goals of Single European Sky and Flightpath 2050 through a reduction in coordination efforts, efficient resource allocation, reduced aircraft emissions, fewer detours, and minimisation of air traffic delays.     

Modeling measurement errors and missing initial values in freeway dynamic origin–destination estimation systems

Most existing dynamic origin–destination (O–D) estimation approaches are grounded on the assumption that a reliable initial O–D set is available and traffic volume data from detectors are accurate. However, in most traffic systems, both types of critical information are either not available or subjected to some level of measurement errors such as traffic counts and speed measurement from sensors. To contend with those critical issues, this study presents two robust algorithms, one for estimation of an initial O–D set and the other for tackling the input measurement errors with an extended estimation algorithm. The core concept of the initial O–D estimation algorithm is to decompose the target network in a number of sub-networks based on proposed rules, and then execute the estimation of the initial O–D set iteratively with the observable information at the first time interval. To contend with the inevitable detector measurement error, this study proposes an interval-based estimation algorithm that converts each model input data as an interval with its boundaries being set based on some prior knowledge. The performance of both proposed algorithms has been tested with a simulated system, the I-95 freeway corridor between I-495 and I-695, and the results are quite promising.     

A Heuristic Algorithm for the Allocation of Airport Runway System Capacity

Abstract

This paper develops a heuristic algorithm for the allocation of airport runway capacity to minimise the cost of arrival and departure aircraft/flight delays. The algorithm is developed as a potential alternative to optimisation models based on linear and integer programming. The algorithm is based on heuristic (‘greedy’) criteria that closely reflect the ‘rules of thumb’ used by air traffic controllers. Using inputs such as arrival and departure demand, airport runway system capacity envelopes and cost of aircraft/flight delays, the main output minimises the cost of arrival and departure delays as well as the corresponding interdependent airport runway system arrival and departure capacity allocation. The algorithm is applied to traffic scenarios at three busy US airports. The results are used to validate the performance of the proposed heuristic algorithm against results from selected benchmarking optimisation models.     

Hierarchical network-based equilibrium model and algorithm for a mixed-traffic urban transport system

Abstract

Many equilibrium models and algorithms based on homogeneous motorized traffic have been devised to model urban transport systems in developed countries, but they are inadequate when it comes to represent mixed-traffic urban transport systems, including automobiles, transit, bicycles, and pedestrians, in developing countries such as China or India. In these cases, traffic flow on a road segment is an aggregated result of travellers' combined mode/route choices and corresponding interactions. Therefore, a special assignment model and algorithm are needed for modeling these distinct behaviors. In this article, the structure of a mixed-traffic urban transport system is analyzed and then expanded and represented using a hierarchical network model based on graph theory. Based on the analysis of travelers' combined mode/route choices, generalized travel cost functions and link impedance functions for different modes are formulated, where the interferences between different modes on the same road segments are taken into account. Due to the ‘asymmetric’ nature of these functions, a variational inequality model is proposed to represent the equilibrium assignment problem in a mixed-traffic urban transport system. The corresponding solution algorithm is also presented. Finally, a numerical example is provided to illustrate the practicality of the proposed model and algorithm.