终端区空中交通流量管理的模型及算法研究
|
摘要
随着我国民航事业迅猛的发展，航空器数量的不断增加，航班飞行架次平均增长率都在15％以上，同时因流量控制不当所造成的航班延误量也日益增加。因此，如何加强终端区内的空中交通流量管理，保证飞行的安全、流畅、有序和减少飞机延误，就成为民航当前极为迫切的任务。
本文主要针对终端区空中交通流量管理中的飞机排序问题，运用单机排序方法，将其转化为一带准备时间的累积旅行商问题(CTSP—RT)。首先建立此问题的数学模型，并采用启发式贪心算法对模型进行求解。考虑到某些接近下降跑道的飞机的随意改变可能会加重管制员的工作负担并造成危险以及这些飞机的过度延误。因此，本文提出了一种改进模型，该模型引入了两个与飞机移动位置相关的约束参数：最大移动位置(MPS)和相对移动位置(RPS)。由这两个参数来控制飞机在队列中的位置，从而有效的解决了上述问题。
采用本文给出的终端区飞机排序算法，对4个典型的飞机队列进行计算，其结果均优于先到先服务算法。因此可以更大限度的减少飞机的延误，进而降低因延误产生的相关费用。本文研究的方法对我国空中交通的流量管理具有一定的借鉴作用。
The urgent problem facing the present civil airline is how to enhance the air traffic management in terminal area and to ensure the save of flight.
This paper mainly focuses on the air sequencing problem in terminal area. By means of the single-machine scheduling method,the practical problem is reformulated into the Cumulative Traveling Salesman Problem with Ready Times(CTSR-RT). A mathematical model is firstly proposed. Then the greedy heuristic algorithm is applied to solve the model.
While rearranging the sequence,the position of the individual aircraft approaching the runway might be shifted many times,which causes an excessive schedule delay and aggravate the burden on the air traffic controller. Taking into account of this problem,the model is modified by introducing two constraints parameters related to the number of shifting of an individual aircraft:Maximum Position Shifting (MPS) and Relative Position Shifting(RPS). To control the position of the aircraft with these two parameters, we solve the above problems with efficiency.
Four practical sequencing examples are given to test the algorithms. In each one of the considered ease, the greedy heuristic algorithm proves to be superior to FCFS, and the minimization of schedule delay and reduction of related costs are achieved.
本文主要针对终端区空中交通流量管理中的飞机排序问题，运用单机排序方法，将其转化为一带准备时间的累积旅行商问题(CTSP—RT)。首先建立此问题的数学模型，并采用启发式贪心算法对模型进行求解。考虑到某些接近下降跑道的飞机的随意改变可能会加重管制员的工作负担并造成危险以及这些飞机的过度延误。因此，本文提出了一种改进模型，该模型引入了两个与飞机移动位置相关的约束参数：最大移动位置(MPS)和相对移动位置(RPS)。由这两个参数来控制飞机在队列中的位置，从而有效的解决了上述问题。
采用本文给出的终端区飞机排序算法，对4个典型的飞机队列进行计算，其结果均优于先到先服务算法。因此可以更大限度的减少飞机的延误，进而降低因延误产生的相关费用。本文研究的方法对我国空中交通的流量管理具有一定的借鉴作用。
The urgent problem facing the present civil airline is how to enhance the air traffic management in terminal area and to ensure the save of flight.
This paper mainly focuses on the air sequencing problem in terminal area. By means of the single-machine scheduling method,the practical problem is reformulated into the Cumulative Traveling Salesman Problem with Ready Times(CTSR-RT). A mathematical model is firstly proposed. Then the greedy heuristic algorithm is applied to solve the model.
While rearranging the sequence,the position of the individual aircraft approaching the runway might be shifted many times,which causes an excessive schedule delay and aggravate the burden on the air traffic controller. Taking into account of this problem,the model is modified by introducing two constraints parameters related to the number of shifting of an individual aircraft:Maximum Position Shifting (MPS) and Relative Position Shifting(RPS). To control the position of the aircraft with these two parameters, we solve the above problems with efficiency.
Four practical sequencing examples are given to test the algorithms. In each one of the considered ease, the greedy heuristic algorithm proves to be superior to FCFS, and the minimization of schedule delay and reduction of related costs are achieved.
引文
[1] http://www.caac.cn.net
[2] 潘立登，黄晓峰，用启发式贪心法求解旅行商问题。北京化工大学学报Vol．25．No．2 1998
[3] 谢金星，邢文训，现代优化计算方法。清华大学出版社，1999
[4] 刘慧英，周勇，空中交通管理系统导论。国防工业出版社，2002
[5] L.Bianco,P.Dell'Olmo and Stefano Giordani. Scheduling Models and Simulation in Air Traffic Manage. 2001
[6] 唐恒永，赵传立，排序引论。科学出版社，2002
[7] 袁亚湘，孙文瑜，最优化理论与方法。科学出版社2001
[8] 谢金星，邢文训；网络优化。清华大学出版社，2000
[9] 齐东元，汪泽焱，邵军力，点、边约束成本的最短路问题及其算法。东南大学学报(自然科学版)Vol．33．No．1 2003
[10] L.Bianco and M.Bielli,System Aspects and Optimization Models in ATC Planning, in: L.Bianco, A. R. Odoni(Eds.),Large Scale Comptuation and Information Processing in Air Traffic Control,Springer Verlag,47-99,1993.
[11] L.Bianco,P.Dell 'Olmo and G.Giordani,One machine scheduling with ready times and sequence dependent processing times:preliminary results,Report 408,IASI-CNR,Rome,1995.
[12] L.Bianco,A.Mingozzi and S.Ricciardelli,The Traveling Salesman Problem with Cumulative Costs, Networks, 23,81-91,1993.
[13] L.Bianco,GRinaldi and A.Sassano,Scheduling tasks with sequence dependent processing times,Naval Res.Log.,35,177-184,1988.
[14] N.Chritstofides,A.Mingozzi and P.Toth,State space relaxation for the computation of bounds to routing problems,Networks, 11,145-164,1981.
[15] R.G.Dear, The Dynamic Scheduling of Aircraft in the Near Terminal Area, FLT R76.9,Flight Transportation Laboratory, M.I.T.,Cambridge, 1976.
[16] M.Fischetti,G, Laporte and S.Martello,The delivery man problem and cumulative matroids,b Opns.Res.,41, 1055-1064, 1993.
[17] M.Held,P.Wolfe and H.P. Crowder,Validation of subgradient optimization,Math.Prog.,6,62-88,1974.
[18] R.L. Graham,E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan,Optimization and approximation in deterministic sequencing and scheduling theory:a survey, Ann.Discrete Math.,5,287-326,1979.
[19] H.N. Psaraftis,A Dynamic Programming Approach to the Aircraft Sequencing problem,FTLR78-4,FlightTransportation Laboratory, M.I.T.,Cambridge, 1978.
[20] J.-C.Picard and M.Queyranne,The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling,Opns.Res.,26,86-110,1978.
[21] A.H.G. Rinnooy Kan, Machine scheduling problem:classification,complexity and computations,Matinus Nijhoff, The Hague,Netherlands,1976.
[22] W.E. Schrage,A proof of the optimality of the shortest remaining processing time discipline,Opns. Res.,687-690,1968.
[23] G.Andreatta, G.Romanin-Jacur, Aircraft flow management under congestion,Trans. Science,21,249-253,1987
[2] 潘立登，黄晓峰，用启发式贪心法求解旅行商问题。北京化工大学学报Vol．25．No．2 1998
[3] 谢金星，邢文训，现代优化计算方法。清华大学出版社，1999
[4] 刘慧英，周勇，空中交通管理系统导论。国防工业出版社，2002
[5] L.Bianco,P.Dell'Olmo and Stefano Giordani. Scheduling Models and Simulation in Air Traffic Manage. 2001
[6] 唐恒永，赵传立，排序引论。科学出版社，2002
[7] 袁亚湘，孙文瑜，最优化理论与方法。科学出版社2001
[8] 谢金星，邢文训；网络优化。清华大学出版社，2000
[9] 齐东元，汪泽焱，邵军力，点、边约束成本的最短路问题及其算法。东南大学学报(自然科学版)Vol．33．No．1 2003
[10] L.Bianco and M.Bielli,System Aspects and Optimization Models in ATC Planning, in: L.Bianco, A. R. Odoni(Eds.),Large Scale Comptuation and Information Processing in Air Traffic Control,Springer Verlag,47-99,1993.
[11] L.Bianco,P.Dell 'Olmo and G.Giordani,One machine scheduling with ready times and sequence dependent processing times:preliminary results,Report 408,IASI-CNR,Rome,1995.
[12] L.Bianco,A.Mingozzi and S.Ricciardelli,The Traveling Salesman Problem with Cumulative Costs, Networks, 23,81-91,1993.
[13] L.Bianco,GRinaldi and A.Sassano,Scheduling tasks with sequence dependent processing times,Naval Res.Log.,35,177-184,1988.
[14] N.Chritstofides,A.Mingozzi and P.Toth,State space relaxation for the computation of bounds to routing problems,Networks, 11,145-164,1981.
[15] R.G.Dear, The Dynamic Scheduling of Aircraft in the Near Terminal Area, FLT R76.9,Flight Transportation Laboratory, M.I.T.,Cambridge, 1976.
[16] M.Fischetti,G, Laporte and S.Martello,The delivery man problem and cumulative matroids,b Opns.Res.,41, 1055-1064, 1993.
[17] M.Held,P.Wolfe and H.P. Crowder,Validation of subgradient optimization,Math.Prog.,6,62-88,1974.
[18] R.L. Graham,E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan,Optimization and approximation in deterministic sequencing and scheduling theory:a survey, Ann.Discrete Math.,5,287-326,1979.
[19] H.N. Psaraftis,A Dynamic Programming Approach to the Aircraft Sequencing problem,FTLR78-4,FlightTransportation Laboratory, M.I.T.,Cambridge, 1978.
[20] J.-C.Picard and M.Queyranne,The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling,Opns.Res.,26,86-110,1978.
[21] A.H.G. Rinnooy Kan, Machine scheduling problem:classification,complexity and computations,Matinus Nijhoff, The Hague,Netherlands,1976.
[22] W.E. Schrage,A proof of the optimality of the shortest remaining processing time discipline,Opns. Res.,687-690,1968.
[23] G.Andreatta, G.Romanin-Jacur, Aircraft flow management under congestion,Trans. Science,21,249-253,1987