A light-propagation model for aircraft trajectory planning

Predicted air traffic growth is expected to double the number of flights over the next 20 years. If current means of air traffic control are maintained, airspace capacity will reach its limits. The need for increasing airspace capacity motivates improved aircraft trajectory planning in 4D (space+time). In order to generate sets of conflict-free 4D trajectories, we introduce a new nature-inspired algorithm: the light propagation algorithm (LPA). This algorithm is a wavefront propagation method that yields approximate geodesic solutions (minimal-in-time solutions) for the path planning problem, in the particular case of air-traffic congestion. In simulations, LPA yields encouraging results on real-world traffic over France while satisfying the specific constraints in air-traffic management.     

Solving the minimum toll revenue problem in real transportation networks

As a means to relieve traffic congestion, toll pricing has recently received significant attention by transportation planners. Inappropriate use of transportation networks is one of the major causes of network congestion. Toll pricing is a method of traffic management in which traffic flow is guided to proper time and path in order to reduce the total delay in the network. This article investigates a method for solving the minimum toll revenue problem in real and large-scale transportation networks. The objective of this problem is to find link tolls that simultaneously cause users to efficiently use the transportation network and to minimize the total toll revenues to be collected. Although this model is linear, excessive number of variables and constraints make it very difficult to solve for large-scale networks. In this paper, a path-generation algorithm is proposed for solving the model. Implementation of this algorithm for different networks indicates that this method can achieve the optimal solution after a few iterations and a proper CPU time.     

On air traffic flow management with rerouting. Part I: Deterministic case

In this paper a deterministic mixed 0-1 model for the air traffic flow management problem is presented. The model allows for flight cancelation and rerouting, if necessary. It considers several types of objective functions to minimize, namely, the number of flights exceeding a given time delay (that can be zero), separable and non-separable ground holding and air delay costs, penalization of alternative routes to the scheduled one for each flight, time unit delay cost to arrive to the nodes (i.e., air sectors and airports) and penalization for advancing arrival to the nodes over the schedule. The arrival and departure capacity at the airports is obviously considered, as well as the capacity of the different sectors in the airspace, being allowed to vary along the time horizon. So, the model is aimed to help for better decision-making regarding the ground holding and air delays imposed on flights in an air network, on a short term policy for a given time horizon. It is so strong that there is no additional cut appending, nor does it require the execution of the branch-and-bound phase to obtain the optimal solution for the problem in many cases of the testbeds with which we have experimented. In the other cases, the help of the cut identifying and heuristic schemes of the state-of-the art optimization engine of choice is required in order to obtain the solution of the problem, and the branch-and-bound phase is not required either. An extensive computational experience is reported for large-scale instances, some of which have been taken from the literature and some others were coming from industry.     

A Multi-agent Based Self-adaptive Genetic Algorithm for the Long-term Car Pooling Problem

Rising vehicles number and increased use of private cars have caused significant traffic congestion, noise and energy waste. Public transport cannot always be set up in the non-urban areas. Car pooling, which is based on the idea that sets of car owners having the same travel destination share their vehicles has emerged to be a viable possibility to reduce private car usage around the world. In this paper, we present a multi-agent based self-adaptive genetic algorithm to solve long-term car pooling problem. The system is a combination of multi-agent system and genetic paradigm, and guided by a hyper-heuristic dynamically adapted by a collective learning process. The aim of our research is to solve the long-term car pooling problem efficiently with limited exploration of the search space. The proposed algorithm is tested using large scale instance data sets. The computational results show that the proposed method is competitive with other known approaches for solving long-term car pooling problem.     

Integrating link-based discrete credit charging scheme into discrete network design problem

In this paper, we present an optimization model for integrating link-based discrete credit charging scheme into the discrete network design problem, to improve the transport performance from the perspectives of both transport network planning and travel demand management. The proposed model is a mixed-integer nonlinear bilevel programming problem, which includes an upper level problem for the transport authority and a lower level problem for the network users. The lower level sub-model is the traffic network user equilibrium (UE) formulation for a given network design strategy determined by the upper level problem. The network user at the lower level tries to minimize his/her own generalized travel cost (including both the travel time and the value of the credit charged for using the link) by choosing his/her route. While the transport authority at the upper level tries to find the optimal number of lanes and credit charging level with their locations to minimize the total system travel time (or maximize the transportation system performance). A genetic algorithm is used to solve the proposed mixed-integer nonlinear bilevel programming problem. Numerical experiments show the efficiency of the proposed model for traffic congestion mitigation, reveal that interaction effects across the tradable credit scheme and the discrete network design problem which amplify their individual effects. Moreover, the integrated model can achieve better performance than the sequential decision problems.     

A simplified kinematic wave model at a merge bottleneck

A merge is a point of a highway where two or more streams of traffic flow into one. It is always easy to solve the demand–supply problem at a merge when the merge is operating under uncongested condition. However, when congestion backs up exceeding the merging point where multiple streams of traffic meet, one is typically faced with splitting downstream supply among the merging branches. Solutions of this situation are multiple and several merge queuing models have been proposed in the past. To address the drawbacks of the past models, this paper proposes a capacity-based weighted fair queuing (CBWFQ) model that is characterized by its fidelity (approximation to real situation), simplicity, and extensibility. Based on the CBWFQ merge queuing model, a simplified kinematic wave model is formulated to model traffic operation at a merge bottleneck.     

Hybrid evolutionary algorithms in a SVR traffic flow forecasting model

Accurate urban traffic flow forecasting is critical to intelligent transportation system developments and implementations, thus, it has been one of the most important issues in the research on road traffic congestion. Due to complex nonlinear data pattern of the urban traffic flow, there are many kinds of traffic flow forecasting techniques in literature, thus, it is difficult to make a general conclusion which forecasting technique is superior to others. Recently, the support vector regression model (SVR) has been widely used to solve nonlinear regression and time series problems. This investigation presents a SVR traffic flow forecasting model which employs the hybrid genetic algorithm-simulated annealing algorithm (GA-SA) to determine its suitable parameter combination. Additionally, a numerical example of traffic flow data from northern Taiwan is used to elucidate the forecasting performance of the proposed SVRGA-SA model. The forecasting results indicate that the proposed model yields more accurate forecasting results than the seasonal autoregressive integrated moving average (SARIMA), back-propagation neural network (BPNN), Holt-Winters (HW) and seasonal Holt-Winters (SHW) models. Therefore, the SVRGA-SA model is a promising alternative for forecasting traffic flow.     

An optimization model and a solution algorithm for the many-to-many car pooling problem

Car pooling is one method that can be easily instituted and can help to resolve a variety of problems that continue to plague urban areas, ranging from energy demands and traffic congestion to environmental pollution. Although car pooling is becoming more common, in practice, participant matching results are still being obtained by an inefficient manual approach, which may possibly result in an inferior solution. In the past, when car pooling studies have been done the problem has been treated as either a to-work problem (from different origins to the same destination) or return-from-work problem (from the same origin to different destinations). However, in this study we employ a time-space network flow technique to develop a model for the many-to-many car pooling problem with multiple vehicle types and person types. The model is formulated as an integer multiple commodity network flow problem. Since real problem sizes can be huge, it could be difficult to find optimal solutions within a reasonable period of time. Therefore, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model. To test how well the model and the solution algorithm can be applied to real world, we randomly generated several examples based upon data reported from a past study carried out in northern Taiwan, on which we performed numerical tests. The test results show the effectiveness of the proposed model and solution algorithm.     

How Airlines and Airports Recover from Schedule Perturbations: A Survey

The explosive growth in air traffic as well as the widespread adoption of Operations Research techniques in airline scheduling has given rise to tight flight schedules at major airports. An undesirable consequence of this is that a minor incident such as a delay in the arrival of a small number of flights can result in a chain reaction of events involving several flights and airports, causing disruption throughout the system. This paper reviews recent literature in the area of recovery from schedule disruptions. First we review how disturbances at a given airport could be handled, including the effects of runways and fixes. Then we study the papers on recovery from airline schedule perturbations, which involve adjustments in flight schedules, aircraft, and crew. The mathematical programming techniques used in ground holding are covered in some detail. We conclude the review with suggestions on how singular perturbation theory could play a role in analyzing disruptions to such highly sensitive schedules as those in the civil aviation industry.     

On air traffic flow management with rerouting. Part II: Stochastic case

We present a framework for modeling multistage mixed 0-1 problems for the air traffic flow management problem with rerouting (ATFMRP) under uncertainty in the airport arrival and departure capacity, the air sector capacity and the flight demand. The model allows for flight cancelation, if necessary. It considers several types of objective functions to minimize, namely, total ground and air holding cost, penalization of the alternative routes to the scheduled one for each flight, delay cost for the flights to arrive to the airports and the air sector nodes, and penalization for advancing the arrival of the flights to the airport over the scheduled period. A scenario tree based scheme is used to represent the Deterministic Equivalent Model (DEM) of the stochastic mixed 0-1 program with full recourse. The nonanticipativity constraints that equate the so named common 0-1 and continuous variables from the same group of scenarios in each period are implicitly satisfied in the compact representation of DEM. Some computational experience is reported for medium-scale instances. The model is so tight that none of the instances of the testbed but two of them requires to execute the branch-and-cut phase of the MIP optimization engine of choice.     

交通拥堵与空气质量——来自汽车尾号限行的证据

由于空气的污染来源众多,交通拥堵是否加剧了空气质量的恶化,一般情况下很难界定和区分。本文利用一个特殊的工具变量——北京市工作日高峰时段汽车根据尾号限行,来分析和回答上述问题。由于受文化习惯影响,居民在挑选车牌号码时一般都不选4,因此包含数字4的车牌号很少。每当限行尾号为4和9的工作日,北京市的道路交通相比其他工作日会更拥堵,这为我们提供了一个识别交通拥堵的独特指标。通过使用双重差分模型排除了大量干扰因素后,我们对北京市35个空气质量监测站点PM2.5浓度逐时数据的分析发现,在限行尾号为4和9的工作日,高峰时段与非高峰时段的PM2.5浓度差异,比其他工作日的差异高出9.46%。交通拥堵显著降低了空气质量。     

New heuristics for over-constrained flight to gate assignments

We consider the over-constrained Airport Gate Assignment Problem where the number of flights exceed the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances. The problem is formulated as a binary quadratic programming problem. We design a greedy algorithm and use a Tabu Search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while we devise a new neighbourhood search technique, the Interval Exchange Move, which allows us flexibility in seeking good solutions, especially when flight schedules are dense in time. Experiments conducted give good results.     

Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model

This paper proposes a novel extended traffic network model to solve the logit-based stochastic user equilibrium (SUE) problem with elastic demand. In this model, an extended traffic network is established by properly adding dummy nodes and links to the original traffic network. Based on the extended traffic network, the logit-based SUE problem with elastic demand is transformed to the SUE problem with fixed demand. Such problem is then further converted to a linearly constrained convex programming and addressed by a predictor–corrector interior point algorithm with polynomial complexity. A numerical example is provided to compare the proposed model with the method of successive averages (MSA). The numerical results indicate that the proposed model is more efficient and has a better convergence than the MSA.     

枢纽机场终端区PBN模式下最优跑道数需求

针对我国枢纽机场日起降高峰小时的航班拥堵常态化问题,从系统整体运行效能的角度,针对枢纽机场终端区跑道系统容量瓶颈,①分析性能基导航(Perormance-Based Navigation,PBN)模式下枢纽机场终端区的空域结构、飞行、管制程序,根据随机服务系统理论,建立其运行模型;②考虑PBN模式下航班、旅客的延误滞留函数和机场单位时间服务支出函数;③再应用排队论和系统运行效能理论,建立枢纽机场最佳跑道数目需求算法,能根据相关参数计算航班滞留时间和队长等指标;④最后引用某枢纽机场相关数据,演算结果符合实际抽样调查统计资料.     

基于SD-VF理论的城市限行政策效应研究

随着我国城市化进程不断加快,城市交通供需矛盾日益突出,交通拥堵问题愈发严重,我国各地纷纷实行各种政策措施来缓解交通拥堵。本文以北京市为例,针对城市交通拥堵的现象,从系统的角度出发,运用系统动力学与灰色Verhulst预测相结合的方法(SD-VF),建立城市交通治堵模型,并采用Vensim软件对模型进行动态仿真分析,从经济、社会、环境等方面探究政策措施对城市环境生态承载力、道路生态承载力等的影响。研究结果表明,限行限号政策虽然在一定程度上提高道路生态承载力,但也可能引发“悖论”效应;修路政策并没有根本上解决城市交通拥堵问题,仅仅是把拥堵状况向后推迟;而相对于单一政策,将发展公共交通与限行政策相结合可以有效缓解交通拥堵,改善空气质量,提升环境承载力,是更加科学合理的政策措施。     

基于SD-GM理论的城市交通拥堵收费模型研究

随着中国城市化建设步伐的不断加快,交通拥堵在不断地加剧。同时,因机动车污染物的排放,每年将产生大量的NO_x,从而又会引起严重的大气污染(如“雾霾”污染)。针对这些问题,本文从环境和社会的角度出发,采用系统动力学与灰色系统相结合的方法(SD-GM),构建了城市交通拥堵收费模型,并对模型中主要变量进行动态仿真和决策分析,以此来寻找缓解交通拥堵和减少机动车尾气排放的可行策略。通过现实性测试和敏感性测试,得到拥堵收费的范围不超过100元/天*辆。通过进一步的仿真和结果分析可得到以下结论:(1)在区间[25,40] 内,随着拥堵收费的提高,NO_x存量,机动车出行吸引度和交通拥堵程度都呈下降趋势,而车均道路面积呈上升趋势。(2)但并非拥堵收费越高越好, 超过40 元/天*辆,会产生相反的效果。最后,通过比较分析,得到NO_x存量,机动车出行量,机动车出行吸引度和交通拥堵程度分别下降了约33.76%,39.64%,43.26%,82.25%,而车均道路面积提高了大约65.68%,进而验证了模型的有效性和实用性。     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。     

Forecasting urban traffic flow by SVR with continuous ACO

Accurate forecasting of inter-urban traffic flow has been one of the most important issues globally in the research on road traffic congestion. Because the information of inter-urban traffic presents a challenging situation, the traffic flow forecasting involves a rather complex nonlinear data pattern. In the recent years, the support vector regression model (SVR) has been widely used to solve nonlinear regression and time series problems. This investigation presents a short-term traffic forecasting model which combines the support vector regression model with continuous ant colony optimization algorithms (SVRCACO) to forecast inter-urban traffic flow. Additionally, a numerical example of traffic flow values from northern Taiwan is employed to elucidate the forecasting performance of the proposed SVRCACO model. The forecasting results indicate that the proposed model yields more accurate forecasting results than the seasonal autoregressive integrated moving average (SARIMA) time series model. Therefore, the SVRCACO model is a promising alternative for forecasting traffic flow.     

城市道路交通信号实时控制的数学模型与算法研究

研究了交通信号的实时配时控制问题.建立了在已有交通设施条件下,控制信号具有线性约束的非线性实时配时系统优化模型,设计了与模型相适应的实时CLY系列算法.重点讨论了点控制问题,建立了相应的数学优化模型,设计了CLY-Point1算法求解.还对线控制问题和面控制问题,建立了多层优化控制模型,并设计CLY-Point2、CLY-Line和CLY-Area算法进行求解.数值模拟结果表明,CLY系列算法具有很强的实时性,车辆平均等待时间比固定配时减少了约20%.     

Models for single-sector stochastic air traffic flow management under reduced airspace capacity

Air traffic efficiency is heavily influenced by unanticipated factors that result in capacity reduction. Of these factors, weather is the most significant cause of delays in airport and airspace operations. Considering weather-related uncertainty, air traffic flow management involves controlling air traffic through allocation of available airspace capacity to flights. The corresponding decision process results in a stochastic dynamic problem where aircraft on the ground and in the air are controlled based on the evolution of weather uncertainty. We focus on the single-sector version of the problem that is applicable to a majority of cases where a volume of airspace has reduced capacity due to convective weather. We model the decision process through stochastic integer programming formulations and computationally analyse it for tractability. We then demonstrate through actual flight schedule data that a simplistic but practically implementable approximation procedure is a generally effective solution approach for these models.