周蔷
(.南京航空航天大学 民航学院,江苏 南京 210016)
摘 要:针对飞机除冰作业流程的复杂性,以及对起飞时刻会产生扰动的重要性,本文着重研究飞机除冰作业的简化模型,在给予常规的一些假设前提下,建立了一种基于固定天气条件下,并设计了含多除冰坪多除冰位的飞机除冰作业的线性调度规划模型,并考虑到不同的除冰坪对于接纳飞机的型号约束和容量约束的规则,在模型中涉及有关优先级和除冰能力的原则,并对该模型采用层级分析法(AHP),并给出了机场延误时间的仿真图,结果说明了该模型的有效性。
关键词:多除冰坪;飞机除冰作业;调度模型;层次分析法
中图分类号: 文献标识码: 文章编号:
Analyze on A Simplified Multi-pad De-icing Scheduling Model
ZHOU Qiang
(College of Civil Aviation, Nanjing University of Aeronautics and Astronautic,Nanjing 210016, China)
Abstract:For the complexity of processes of aircraft deicing, as well as take-off time will have the importance of disturbance, this paper focuses on the simplified model of aircraft deicing operations, giving some of the conventional assumptions, the establishment of a weather condition based on fixed and designed with multi-pad and multi-position of aircraft de-icing operation bit linear programming model for scheduling, taking into account the different de-icing of aircraft floor model for the acceptance of constraints and capacity constraints of the rules, in the model involving the priorities and principles of de-icing capabilities, and the model using analytic hierarchy (AHP), and gives the simulation of the airport delay simulation diagram,the results show the validity from the model.
Key words: Multi-deicing Pad;Aircraft Deicing Operations;Scheduling Model;AHP Method
近年来,在冬季持续冰雪等恶劣的气候影响下,很多国家和地区的民航交通运输安全出现不同程度的隐患,部分空难事件直接与飞机除冰作业完成质量有着不可分割的联系,这就要求对飞机起飞之前的除冰调度作业提出了严格的要求。然而,对于飞机除冰作业调度问题的研究尚处于起步阶段,一些理论和模型还不是非常健全,2005年美国运输部交通研究中心的JonathanT. Lee等人在《Detroit Deicing Decision Support Tool》一文中以含有两个除冰坪的底特律机场为蓝本, 建立除冰作业模型,设计了对天气类型的分类,以及机型大小与除冰坪的匹配度,和常见概率分布,建立了除冰序列模型,并用蒙特卡洛方法在Matlab中仿真,作为除冰作业的调度决策机制,并以底特律机场(DTW)实际数据来验证模型的正确性,但是在研究过程中对于天气类型的分类模糊无数值的确定性。
2007-2008年之间其中比较有影响的Xiaoyu Mao,Adriaan Ter Mors,Nico Roos,and Cees Witteveen等研究者的几篇论文《Using Neuro-Evolution in Aircraft Deicing Scheduling》,《Multi-Agent System Support for Scheduling Aircraft De-icing》,《Agent-based Scheduling for Aircraft Deicing》,《Coordinating Competitive Agents in Dynamic Airport Resource Schedulin》其中对于机场除冰作业调度问题使用了多Agent技术,将此问题中涉及到的三方(机场,除冰服务公司,以及航空公司)作为Agent,并引入了协同竞争决策机制,逆序惩罚机制,以及拍卖决策机制,从而使在除冰作业中对于时隙的分配达到了公平性的评价指标,但是文中将飞机作为决策主体,缺乏主动性,以及一些假设限制,但该问题在某种程度上并不具有一般性。
国内在研究飞机除冰作业相关问题滞后于国外,近年来国内不断有一些研究者,如中国民航大学以下几位学者分别对该问题的不同角度做了相应的研究,如2009年顾若愚《基于规则的启发式搜索算法在飞机除冰调度中的应用》,顾彬《分散式飞机除冰作业调度优化》,2010年杨太鹏在《飞机地面除冰运行决策模型研究》中对 ,另外石旭东,刘胜飞等人在《飞机集中除冰车辆优化调度方法研究》这些文章都有通过对实际除冰调度业务流程进行研究,分析需要考虑的约束条件,建立一些启发式规则,然后根据规则设计了启发式搜索算法,并与飞机除冰调度问题的最基本的FCFS算法展开对比。优化了原有的除冰策略调度模型。
虽然国内外都对进行了研究,但基本上都是对除冰作业的模型的某一方面的研究,而对于引入复杂外界因素的研究非常少。目前,对于还没有现成规范可供参考,为了了解水下不分散混凝土的力学性能,以便为实际工程提供参考,有必要对其研究。本文对除冰调度作业进行了建模,并将天气情况进行了分类,并进行了比较分析,得出了一些有参考价值的数据。
1、飞机除冰调度作业问题模型的简化描述
有n种类型飞机共N架,有m种规格的除冰坪用来为这些飞机除冰,其中不同类型的飞机按照一定的规则和除冰坪匹配,比如大型除冰坪接受大型飞机以及以下规格飞机除冰,中型除冰坪接受中型飞机以及以下规格机型除冰,小型除冰坪只能接受小型飞机除冰要求所有飞机在经过除冰坪除冰后才可以起飞。考虑飞机分配到除冰坪的优先原则下,如何分配飞机到除冰坪中,使得所有飞机在除冰结束后立即起飞的机场作业时间最少
天气类型,飞机类型如下表:
|
天气类型 |
A |
霜,冻雾或雾 |
B |
雾凇冰温和的干雪 |
C |
潮湿的雪 |
D |
大雪 |
E |
冻雨 |
飞机类型 |
B747 |
A330/DC10 |
B757 |
A319/A320 |
DC9 |
RJs |
2.1模型假设
1.假设飞机除冰作业中天气类型是已知的,且在除冰过程中天气保持相对稳定,即在此类天气状况下,所对应的除冰液配比是固定值;
2.假设所有的飞机现在都处于离桥状态;
3.假设每个除冰坪有多个除冰位置可同时对多架飞机进行除冰;
4.假设机场地面上所有的飞机都需要经过除冰才能起飞,且除冰结束后立即经过滑行道起飞,不同类型飞机除冰后到起飞前滑行时间是一个常数。
5.假设飞机在除冰后不会出现二次除冰;
2.2符号说明
:机场总的除冰作业时间;
:第类飞机分配到第个除冰坪的飞机数量;
:第类飞机分配到第个除冰坪中的第个位置除冰的飞机数量;
:第个除冰坪除冰所花费的时间
:第个除冰坪第个位置除冰所花费的时间
:第类飞机每个飞机除冰后的滑行时间
:第个除冰坪同时进行除冰飞机的数量
:第类飞机中每一个飞机除冰所花费的时间
:待除冰飞机的类型数
:第类飞机的数量
:除冰坪的数量
:所有除冰飞机数量
4.模型分析与建立
由假设知道所有的飞机目前都处于离桥状态,由假设知道所有的飞机都需要经过除冰才能起飞,再根据假设和假设可知,在某特定天气下,机场总延误时间即为所有飞机除冰所花费的时间。故此,建立飞机除冰流程图(见图1)。
图1 机场地面飞机除冰作业流程
Fig.1 Aircraft deicing operations process in airport ground
根据假设,由于飞机除冰后的滑行时间是一个常值,机场总除冰时间最短就是要求所有除冰坪除冰时间最短,
即;又根据假设,对于每个除冰坪,由于可以同时对多架飞机进行除冰,要求该除冰坪的作业时间最短,即每个除冰位置上除冰时间最短,也就是;故第个除冰坪第个除冰位置除冰所花费的时间为分配到该位置的所有类型的飞机的除冰时间之和,即;第类飞机分配到第个除冰坪的飞机数量为第个除冰坪中个位置的除冰飞机的数量之和,即;而在整个除冰过程中,由于所有飞机都要除冰,所以所有除冰坪中同类型的飞机的数量之和等于所有的同类型的飞机,即();同时所有除冰坪上的所有类型的除冰飞机的数量为机场待除冰飞机的数量,即;又由于不同飞机的类型对除冰坪的要求不同,即对某些,,
有;所以建立多目标函数如下:
5、算法描述以及算例分析
|
|
平均时间(分钟) |
飞机数量 |
|
机型\天气类型 |
A |
B |
C |
D |
E |
|
除冰
液喷
洒时
间
|
B747 |
18 |
23 |
30 |
40 |
60 |
4 |
A330/DC10 |
13 |
18 |
23 |
34 |
45 |
6 |
B757 |
8 |
11 |
16 |
20 |
45 |
10 |
A319/A320 |
7 |
9 |
14 |
19 |
45 |
12 |
DC9 |
3 |
5 |
12 |
15 |
45 |
8 |
RJs |
3 |
5 |
12 |
15 |
45 |
10 |
飞机滑行时间 |
|
1 |
|
A,B两类飞机只能在第I规格除冰坪除冰;C,D规格的飞机可以在第I,II,III规格除冰坪除冰;E,F规格的飞机可以在第I,II,III,IV规格除冰坪除冰;同时每种规格的除冰坪容量有限,第I规格除冰坪可以同时为6架飞机除冰,第II,III规格除冰坪各自可以同时为4架飞机除冰,第IV规格除冰坪可以同时为3架飞机除冰;且每类飞机在除冰坪上除冰时间为 30,23,16,14,12,12分钟。
对于多目标问题的求解,一般方法是将多目标问题转化为单目标问题。对于此模型,由于需要考虑到飞机除冰的优先原则,即不同类型的飞机除冰的优先顺序不同,同时需要将不能量化的优先顺序转化为量化问题,故本文采用AHP法(层次分析法)将该多目标问题转化为单目标问题。模型中给出5种天气类型,分别是;假设模型中给出4个除冰坪,其中第一个除冰坪有6个除冰位,第二个除冰坪有4个除冰位,第三个除冰坪有4个除冰位,第四个除冰坪有3个除冰位,考虑在这5种天气类型下4个除冰坪给6类飞机除冰所延误的时间,而且第一、二类飞机只能分配给第一个除冰坪;第三、四类飞机只能分配给第一、二、三个除冰坪;第四、五类飞机可以给每个除冰坪分配。
建立层次结构模型,确定单目标函数
图2 机场延误时间的层次结构模型
Fig.2 Hierarchical structure model of delay times in airport
根据上述分析,如何分配飞机到除冰坪而使得机场总延误时间最短,即为如何分配不同类型的飞机到不同除冰坪的不同除冰位置,使得所有机场的除冰时间最短。这样就要求每个除冰坪所花费的时间最短,由于每个除冰坪有多个除冰位置而且每个位置的工作效率即除冰时间不同,即对机场延误时间所做出的贡献有所不同,因此根据图2,建立固定天气下机场总延误时间为:
(9)
其中,,,为不同除冰坪的不同除冰位置对机场总延误时间的权重。
建立逆对称矩阵,计算不同层次对上层目标的权重
考虑到飞机除冰的优先顺序,由于不同类型的飞机需要在不同的除冰坪进行除冰,我们将不同类型的飞机的除冰优先原则,可以转化为不同除冰坪的能力的比较。根据所已知的除冰坪除冰能力的数据,建立对于不同除冰坪对整个作业时间的影响矩阵(逆对称矩阵)为:
同时建立不同除冰坪的每个除冰位置对除冰坪的逆对称矩阵为
(11)
其中,,可以分别计算
,,,,,及,,。
调用AHP函数,进行迭代
对于矩阵,令,迭代,其中,,为的4个分量之和;
对于,令,迭代,其中,,为的个分量之和。
一致性检验
对于,令,
,比较是否小于,进行一致性检验;
对于,令,,比较是否小于,进行一致性检验,其中,,
调用线性规划函数
对给定的种天气类型,令为第类飞机中每一个飞机在固定天气类型下除冰所花费的时间;同时将约束条件用矩阵表示,调用主函数进行求解。
6、结果分析
每个天气下不同类型的飞机分配到各除冰坪的数量()
天气:
=
天气:
=
天气:
=
天气:
=
天气:
=
每个天气下不同类型的飞机分配到各除冰坪的除冰位置的飞机数量()
天气下种类型的飞机分配到第个除冰坪各除冰位置的飞机数量:
天气下种类型的飞机分配到第个除冰坪各除冰位置的飞机数量:
天气下种类型的飞机分配到第个除冰坪各除冰位置的飞机数量:
天气下种类型的飞机分配到第个除冰坪各除冰位置的飞机数量:
每个天气下不同飞机分配到不同除冰坪的不同位置的数量相同。
每个天气下机场总延误时间()
图3. 5种天气类型下机场总延误时间
Fig.3 The total delay time of Airport under 5 types of weather types
不同天气下每个除冰坪花费的除冰时间()
天气:
天气:
天气:
天气:
天气:
图4. 在不同天气类型下4个除冰坪除冰花费时间
Fig.4. The time in spending De-icing under the 4 deicing-Pad weather types
每个除冰坪的各除冰位置在不同天气下花费的除冰时间()
第个除冰坪的个除冰位置在种天气类型下所花费的除冰时间:
第个除冰坪的个除冰位置在种天气类型下所花费的除冰时间:
第个除冰坪的个除冰位置在种天气类型下所花费的除冰时间:
第个除冰坪的个除冰位置在种天气类型下所花费的除冰时间:
7、结论
本文为了简化飞机除冰作业调度问题的描述,进行了一些假设,并在此基础上建立了一个考虑了优先级原则上的飞机除冰调度线性规划模型。该模型具有多层目标,多个约束条件,能够方便地描述现实中的飞机除冰作业调度优化问题。为了能够快速求解模型,我们采用了层次分析的方法,比较了各种除冰坪的优先级(实质是对飞机除冰分配的优先顺序),对在满足假设条件之下的飞机除冰做出了合理的分配使所有飞机除冰作业时间(即机场延误时间)最少,给出了相应的图像说明。
当然,任何一个数学模型都不可能完全将现实的问题全部考虑。由于一些客观原因,该模型也有一定的不足之处。如在没有航班时刻表的情形下,我们做出了假设,假设所有的飞机现在都处于离桥状态;在没有考虑飞机除冰合格的情形下,我们做出了假设、假设所有的飞机都需要经过除冰才能起飞,且除冰结束后立即起飞,假设飞机在除冰后不会出现二次除冰;然而在实际生活中,飞机除冰作业时间和机场延误时间大多不同,而且飞机除冰后可能由于其他因素需要二次除冰,所以在模型后期的修正中,可以在该模型的基础上,考虑这些因素,做出更加符合现实情形的数学模型。
参考文献:
[1]王莲芬,许树柏.层次分析法引论[M].北京:中国人民大学出版社,1990
[2] B.E吉勒特普.运筹学导论[M],北京:机械工业出版社
[3]苏金明,阮沈勇,王勇利.MATLAB工程数学[M].北京:电子工业出版社,2005
[4]周义仓,赫孝良.数学建模实验[M].西安:西安交通大学出版社,1999
[5] Shangyao Yan, Ching-Hui Tang.A heuristic approach for airport gate assignments for stochastic flight delays [J].
European Journal of Operational Research,180(2007) 547–567
[6]Small and Large Aircraft Aircraft Critical Surface Contamination Training For Aircrew and Groundcrew Seventh Edition December 2004
[7] Environmental Protection Washington. Preliminary Data Summary Airport Deicing Operations(Revised) [Z]United States Office of Water (4303) , August 2000 Agency
[8]Xiaoyu Mao,Adriaan ter Mors,Nico Roos,Cees Witteveen.
Agent-Based Scheduling for Aircraft Deicing[C].CFW proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence,Belgium,August,2008:229-236.
[9]JonathanT.Lee,SuzanneChen,Anastasios (Chris)Daskalakis.
Detroit Deicing Decision Support Tool[J].U.S. Department of Transportation Volpe National Transportation Systems Center.May 4, 2005
[10]Xiaoyu Mao, Adriaan ter Mors, Nico Roos, and Cees Witteveen. Coordinating Competitive Agents in Dynamic
Airport Resource Scheduling
[11]Suzanne Chen, and Anastasios Daskalakis,Volpe National Transportation Systems Center, Cambridge, MA
[12]Deicing Pad EvaluationGeneral Mitchell International
Airport AAAE Natiionall Enviironmentall Conference
Miillwaukee,, WII June 23,,2008 Jeff Macomber..
[13]Chinyao Lowa, YulingYeha, Genetic algorithm-based heuristics for an open shop scheduling problem with set up ,processing and removal timesse parated[J]Robotics and Computer Integrated Manufacturing 25(2009)314–322.
[14] Obrad Babic, Milica Kalic, Goran Pavkovic, Slavica Dozic and Mirjana angalovic. Heuristic approach to the airline schedule disturbances problem.[J]Transportation Planning and Technology.Vol. 33, No. 3, April 2010, 257-280.
[15]Xiaoyu Mao, Adriaan ter Mors, Nico Roos, and Cees Wittevee.Multi-Agent System Support for Scheduling Aircraft De-icing [C]Proceeding of ISCRAM,Intelligent Human Computer Systems for Crisis Response and Management, SouthCalifornia,USA,March,2007:467-478.
[16] Xiaoyu Mao, Adriaan ter Mors, Nico Roos, and Cees Witteveen. Using Neuro-Evolution in Aircraft Deicing SCheduling[D].In Karl Tuyls and Steven de Jong and Marc Ponsen and Katja Verbeeck (Eds,).ALAMAS 2007 Adaptive and Learning Agents and Multi-Agent Systems,2007,PP.138-145.MICC Technical Report Series.
[17] Wayne S. Pennell C.M.巴尔的摩华盛顿国际机场机场冬季运营及飞机除冰管理
[18]杨太鹏.飞机地面除冰运行决策模型研究[J]中国民航大学学报,2010年6月第28卷第3期
[19] 石旭东,刘胜飞,陈慕华,王立文.飞机集中除冰车辆优化调度问题方法研究.[J]计算机工程与应用.45 (4)2009,45
[20]顾彬.分散式飞机除冰作业调度优化[J] 2010全国计算机网络与通信学术会议