An aggregate stochastic programming model for air traffic flow management

In this paper, we present an aggregate mathematical model for air traffic flow management (ATFM), a problem of great concern both in Europe and in the United States. The model extends previous approaches by simultaneously taking into account three important issues: (i) the model explicitly incorporates uncertainty in the airport capacities; (ii) it also considers the trade-off between airport arrivals and departures, which is a crucial issue in any hub airport; and (iii) it takes into account the interactions between different hubs.The level of aggregation proposed for the mathematical model allows us to solve realistic size instances with a commercial solver on a PC. Moreover it allows us to compute solutions which are perfectly consistent with the Collaborative Decision-Making (CDM) procedure in ATFM, widely adopted in the USA and which is currently receiving a lot of attention in Europe. In fact, the proposed model suggests the number of flights that should be delayed, a decision that belongs to the ATFM Authority, rather than assigning delays to individual aircraft.     

A gate reassignment framework for real time flight delays

Flight delays (such as early or late arrivals and late departures) are a frequent occurrence in actual day to day airport operations and it is often not possible to assign such flights to their original gates. Flight delay information may also vary with time. As a consequence, the airport authority needs to reassign flights to different gates in real-time. The traditional manual flight reassignment method is neither efficient nor effective in cases with variable flight delay information, and the reassignment is frequently time constrained. Consequently, in this study the goal is to develop a gate reassignment framework, and a systematic computerized tool, for repeatedly handling gate reassignments given varied flight delay information. The results of a test case related to Taiwan international airport operations, show that the proposed framework performs well.     

A set packing model for the ground holding problem in congested networks

Air traffic flow management (ATFM) consists of several activities performed by control authorities in order to reduce delays due to traffic congestion. Ground holding decisions restrict certain flights from tacking off at the scheduled departure time if congestion is expected at the destination airport. They are motivated by the fact that it is safer to hold an aircraft on the ground than in the air. Several integer linear programming models have been proposed to efficiently solve the ground holding problem (GHP). In this paper we investigate a set packing formulation of the GHP and design a branch-and-cut algorithm to solve the problem in high congestion scenarios, i.e., when lack of capacity induces flights cancellation. The constraint generation is carried out by heuristically solving the separation problem associated with a large class of rank inequalities. This procedure exploits the special structure of the GHP's intersection graphs. The computational results indicate that the proposed algorithm outperforms other algorithms in which flight cancellation has been allowed.     

A combined statistical approach and ground movement model for improving taxi time estimations at airports

With the expected continued increases in air transportation, the mitigation of the consequent delays and environmental effects is becoming more and more important, requiring increasingly sophisticated approaches for airside airport operations. Improved on-stand time predictions (for improved resource allocation at the stands) and take-off time predictions (for improved airport-airspace coordination) both require more accurate taxi time predictions, as do the increasingly sophisticated ground movement models which are being developed. Calibrating such models requires historic data showing how long aircraft will actually take to move around the airport, but recorded data usually includes significant delays due to contention between aircraft. This research was motivated by the need to both predict taxi times and to quantify and eliminate the effects of airport load from historic taxi time data, since delays and re-routing are usually explicitly considered in ground movement models. A prediction model is presented here that combines both airport layout and historic taxi time information within a multiple linear regression analysis, identifying the most relevant factors affecting the variability of taxi times for both arrivals and departures. The promising results for two different European hub airports are compared against previous results for US airports.     

Parking buses in a depot with stochastic arrival times

Given buses of different types arriving at a depot during the evening, the bus parking problem consists of assigning these buses to parking slots in such a way that they can be dispatched adequately to the next morning routes without moving them between their arrivals and departures. In practice, the bus arrival times deviate stochastically from the planned schedule. In this paper, we introduce for this problem two solution approaches that produce solutions which are robust to variations in the arrival times. The first approach considers that each arrival can deviate from its planned arrival order (sooner or later) by at most k positions, where k is a predefined parameter. In the second approach, the objective aims at minimizing the expectation of a function positively correlated with the number of buses that make the planned solution infeasible because they arrive too late or too early. In both approaches, the problem is modeled as an integer linear program that can be solved by a commercial mip solver. Computational results obtained on instances derived from a real-world dataset are reported.     

Flight gate scheduling with respect to a reference schedule

This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation where certain gate assignments may cause blocking of neighboring gates. The objectives include maximization of the total assignment preference score, a minimal number of unassigned flights during overload periods, minimization of the number of tows, maximization of a robustness measure as well as a minimal deviation from a given reference schedule. We show that in case of a one period time horizon this objective can easily be integrated into our existing model based on the Clique Partitioning Problem. Furthermore we present a heuristic algorithm to solve the problem for multiple periods.     

Performance of CSMA in multi-channel wireless networks

We analyze the performance of CSMA in multi-channel wireless networks, accounting for the random nature of traffic. Specifically, we assess the ability of CSMA to fully utilize the radio resources and in turn to stabilize the network in a dynamic setting with flow arrivals and departures. We prove that CSMA is optimal in the ad-hoc mode, when each flow goes through a unique dedicated wireless link from a transmitter to a receiver. It is generally suboptimal in infrastructure mode, when all data flows originate from or are destined to the same set of access points, due to the inherent bias of CSMA against downlink traffic. We propose a slight modification of CSMA that we refer to as flow-aware CSMA, which corrects this bias and makes the algorithm optimal in all cases. The analysis is based on some time-scale separation assumption which is proved valid in the limit of large flow sizes.     

乘客到达时间不确定的机场动态拼车策略与算法研究

网约车拼车服务作为共享经济领域重要应用,已成为国内外研究热点。针对机场在线拼车平台运营中乘客等待时间过长和车辆行驶成本较高的突出问题,本文提出前瞻式动态拼车匹配策略。该策略将未来随机到达乘客信息纳入当前已到达乘客的拼车匹配决策中,建立了乘客匹配与车辆路径联合优化两阶段随机规划模型。为了在动态环境中实时产生高质量的匹配与路径规划方案,首先基于贝叶斯估计压缩乘客随机到达情景空间,建立了问题的确定性近似最优模型。为了快速求解模型,提出基于订单目的地和乘客期望到达时间相似度的匹配规则,并以此开发改进的差分进化算法。最后,基于某拼车平台真实订单数据,通过对比测试验证了前瞻式匹配策略和改进差分进化算法的有效性与计算效率。     

机场任务指派问题的优化方案研究

本文研究了机场任务指派问题,该问题是指将具有特殊属性的任务指派给有限数量的班次。由于机场任务和班次属性的多样性,机场任务指派问题是一个复杂的组合优化问题,属于NP-完全问题。本文以任务完成产生的效益总和最大化为目标建立数学优化模型,提出有效不等式,应用CPLEX软件对实际数据进行求解,结果表明,CPLEX可以在较短时间内对一定规模的算例求得最优解。同时对影响目标函数的四个因素:任务数量、班次数量、班次工作时长和任务属性分别进行分析,通过实际算例测试对比,得出具有指导意义的结论,即根据机场特征分别调整四个因素不仅能够提高机场资源的有效利用率,而且能够提高机场的运行效率和服务水平。     

面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究

在给定航班时刻表条件下,对于进出港航班的机位分配,除了必须满足航班、飞机和机位之间的技术性要求之外,还要考虑尽量提高整个机场的机位利用率,且方便旅客出入港及时、安全和便捷.文章以飞机机型、所属航空公司、客运/货运航班、国内/国际航班等匹配条件为约束条件,以航班-机位分配完成率、靠桥率、道口非冲突率为目标,建立了一个航班-机位指派问题的全局优化模型.基于国内某机场的真实应用场景及其待决策变量维度的超大规模,导致模型求解成为一个NP-COMPLETE的混合整数规划问题.文章提出一种启发式快速求解算法,基于贪婪规则建立若干优先级队列的航班冲突调整方案,按照3个指标重要程度渐次探求近似最优解.而且,对于每一步贪婪规则的改进,文章都进行了算法有效性检验以及计算性能的对比实验.最终多重对比实验的结果表明,新算法的结果在与理论最优解差距不足3%的代价下,可节约超过90%求解时间.     

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.     

Scheduling de-icing vehicles within airport logistics: a heuristic algorithm and performance evaluation

Most delays in the air transport occur at the airport. A particular reason is the complexity of managing the large number of supporting flows in airport logistics. We consider the optimisation problem of scheduling de-icing vehicles that is one of the key supporting logistic flows in the turn-around process of aircraft. The objective is to minimise the delay of flights due to de-icing, and the travel distance of the de-icing vehicles. We study the complexity of the problem, and develop a solution algorithm using greedy randomised adaptive search. A case study of real-life data from Stockholm Arlanda Airport shows that optimised schedule leads to significantly better performance in comparison to intuitive and simple scheduling strategies. The benefit of optimisation in reducing the waiting time for de-icing is further demonstrated via dynamic simulations.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems

This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem and a randomized rounding procedure. We handle the case where the number of hubs is three, which is known to be NP-hard, and present a (5/4)-approximation algorithm.The single allocation problem includes a special class of the metric labeling problem, defined by introducing an assumption that both objects and labels are embedded in a common metric space. Under this assumption, we can apply our algorithms to the metric labeling problem without losing theoretical approximation ratios. As a byproduct, we also obtain a (4/3)-approximation algorithm for an ordinary metric labeling problem with three labels.     

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

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

A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY

1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera…     

Robust model selection criteria for robust Liu estimator

In linear regression analysis, outliers often have large influence in the model/variable selection process. The aim of this study is to select the subsets of independent variables which explain dependent variables in the presence of multicollinearity, outliers and possible departures from the normality assumption of the error distribution in robust regression analysis. In this study to overcome this combined problem of multicollinearity and outliers, we suggest to use robust selection criterion with Liu and Liu-type M(LM) estimators.     

机场新增卫星厅对登机口影响的评估方法

为了解决航站楼客流量饱和的问题,采用一种增加卫星厅的方法,实现了旅客分流.基于单目标整数线性规划和多目标优化的方法,分别构建了登机口优化分配网络模型和多目标优化模型.利用登机口优化分配网络算法筛选出所使用的共同登机口,建立了目标函数并列出约束条件,采用目标约束法对建立的模型进行求解.在此基础上,根据目标建模的思想,建立了可供中转旅客总体流程时间最短且使用登机口数量最小的航班-登机口分配模型.利用MATLAB计算可知,利用42个登机口即可实现303架航班的正常运转.     

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.