《基于遗传算法的机场停机位分配问题研究》由会员分享，可在线阅读，更多相关《基于遗传算法的机场停机位分配问题研究（4页珍藏版）》请在金锄头文库上搜索。
1、2 0 0 6 中国控制与决策学术年会论文集P r o c e e d i “弘o f2 0 0 6C h i M s fC o n t r o ln dD e c i s i o nc M 五r e m1 0 7 7基于遗传算法的机场停机位分配问题研究刘长有，卫东选( 中国民用航空学院交通工程学院。天津3 0 0 3 0 0 )播要，分配航班刭适当的停机位对子航空公司和机场的运营都有着重要影响在舟析机场停机位分配1 日惠曲基础上，以旅客行走距高最小化为耳标建立静寿A G A P 问是的教学优化模型，给出解央谖优化问题的遣传算法，并在遗传算手中加入禁忌搜索思想牲保证停机位空闷时闻的相对平衡最后
2、用M A T L A B 程序设计实现了谈算法美键词：停机位分配；最忧亿 遗传算弦| 荣忌筏索R e s e a r c ho nt h eA i r p o r tG a t eA s s i g n m e n tP r o b l e mb yU s i n gG AL UC h a n g y o u ，W E ，D o n g ? “( C o l l 。g e 。f T r a n s p o r t a r i o nE n g i n e e r i “g ，C i V i l A v i a t i o n U n i v e r s i t yo f C h i n a ，
3、T i a n j i n3 0 0 3 0 0 ，C h i n a - C o r r e $ p o n d e n tL I UC h a n g y o u E m a i l ：c y l i u S l l 1 6 3 c o r n )A b s t r a c t ：A s s i g n i n ga i r c r a f tt oa v a i l a b l eg a t e sc a nh a v eam a j o ri m p a c to nt h em a n a g e m e n to fa i r l i n e sa n da i r p o r t
4、 B a s e do na n a l y z i n gt h eA G A P u s i n gm i n i m u mt h et o t a lw a l k i n gd i s t a n c eo fp a s s e n g e r sa so b j e c t i v ef u n c t i o n i tp r o p o s e st h es t a t i cA G A Pm o d e I a n di m p l e m e n tg e n e t i ca l g o r i t h mt os o l v et h ep r o b l e m I
5、 no r d e rt oe n s u r et h eb a l a n c eo fg a t e ss p a r et i m e , at a b us e a r c ht e c h n i q u ei su s e d A tl a s t tM A T L A Bi sp r o p o s e dt oi m p l e m e n tt h ea l g o r i t h m 。K e yw o r d s ：G a t ea s s i g n m e n t O p t i m i z a t i o npG A lT a b us e a r c h1 引言
6、机场停机位分配问题( A G A P ) 是指考虑飞机机型、停机位类型以及航班时刻等因素，为未来一个时间段内到港和离港的航班选择并分配合适的停机位机场停机位的合理分配是机场地面作业中的一项核心任务，涉及到各航空公司进出航班的航线类型、航线距离、机型、航班数量、航班密度、停机时间、中转旅客行走距离、行李搬运距离等多方面的约束停机位分配得适当与否，直接关系到航空公司与机场的运营和效益状况不恰当的分配方式会导致航班延误，降低旅客满意度，影响相关部门的正常运营，甚至会造成事故的发生现在国内太部分机场采用的都是落后的人工分配方法为进出港航班分配机位，往往造成航班无机位可分配。只好分配列远机坪而采用巴土对
7、旅客进行接送这不仅严重影响了旅客对服务的满意度，而且造成资源的浪费和增加额外费用国外已有很多专家提出多种方法来解决A G A P问题，如基于专家系统的方法【1 ，禁忌搜索法o 。】，分支定界法“1 和。一1 整数规划口3 等但专家系统只能提出可行但非最优的分配方案；另外几种优化算法虽然可以提出最优分配方案，而且是基于单目标，最后也仅能提供一种优化分配方案而实际运营中，航班的进离港时间受天气、地面设备等多方面不确定性因素的影响，总会出现延误，只考虑单目标的单一优化分配方案不能满足实际需要在以往的A G A P 问题的研究中，优化目标函数主要有两种：第1 种是以保证各个机位相邻航班问的空闲时间分布
8、均匀为目标，提高停机位利用率，并满足在航班发生短时间延误时，有足够的机位空闲时阅对其进行调整，而不影响其他航班；第2 种以旅客总的行走距离( 或登转机时间) 最小为目标，以提高旅客满意度，减少运营成本而实际的A G A P 问题是多目标的，只考虑行走距离最优，则会造成部分基金项目，国家自然科学基金项目( 6 0 4 7 2 1 3 0 ) 作者俩介刘长有1 9 5 6 男河北卢苊人教授，博士生导师从事自动控制理论与应用、系统工程等研究1 0 7 8Z 0 0 6 中国控制与块策学术年会论文集机位繁忙而其他机位相对空闲；考虑机位空闲最优则会造成旅客满意度下降增加地面服务成本本文以旅客行走距离最小
9、为主目标函数同时考虑使得机位的相邻航班的空闲时间尽可能均衡采用遗传算法对其进行优化，并在初始种群的产生和遗传操作过程中采用禁忌搜索算法控制同一机位相邻航班问的空闲时间尽可能的平衡该方法的应用是将双目标优化问题转化为单目标优化同题最后利用M A T L A B 实现该算法，通过实验数据验证，可以在理想的时间内得到一组优化分配方案2 有关定义及数据模型本文假设机场中共有K 个停机位可以利用，设为G = G ，G 2 ”+ G z ，其中停机位类型设为相同的，即每个停机位均可以停放任意类型飞机；在考虑的时间段内有架航班到离港，航班按照到达时间排序，集合为F = F ，F ：，F ， 所用到的数学符号
10、定义如下：A ，为航班j 的预定到达时刻；D ，为航班，的预定离开时刻；口为同一停机位内航班离开和下一航班到达之闯的最小缓冲时间；口为相邻航班间停机位的平均空闲时间；P 为机位空闲时间的容忍度；7 1 。为停机位 与停机位z 之同的距离，显然有n + t= 兀“T 。表示执机柜台到停机位 的距离，L 。表示停机位 到行李提取处的距离，但7 。丁。；。为从到达航班r 转移到离港航班J 的旅客数量，其中i k n ，vi V 点K ，( 4 )衙y p = ：2 vJ N 。v K ，( 5 )r N A D + 口，Vi N ( 6 )目标函数表示全部旅客的行走距离之和，我们的优化目标即是使其最
11、小约束条件( 2 ) 表明蛳 一为二进制变量；约束条件3 ) 说明每架航班必须且仅需分配一个停机位：约束条件( 4 ) 和( 5 ) 指出每个航班的前后最多只有一个航班被分配到同一个停机位；约束条件( 6 ) 表明分配到同停机位 的相邻航班J 和航班z 之间必须为停机位留有足够的缓冲时间以保证航班顺利进出停机位以及地面服务人员和设备的准备工作3算法设计机场停机位配置问题是一个N P 一难度的二次配置问题( Q A P ) 采用精确法求解不可避免地会遇到维散灾难问题遗传算法( G A ) 是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，相对于传统的优化算法有着对可行解表示的广泛性，群体搜索
12、性固有的并行性和并行计算能力以及可扩展性等优点遗传算法已在很多时序安排的优化问题中得以应用并取得了很好的效果本文根据所建立的机位分配模型，整个寻优过程采用遗传算法，而对初始解的生成变异算子中采用禁忌搜索算法，以保证搜索到的均为可行解，且满足一定的空闲时间平衡为简化问题，本文中只考虑航班均可以分配到所需的停机位，不存在某个航班无机位可分配的情况3 1遗传染色体编码表示在本文中，采用一个维整数字符串来表示这架航班在片个停机位的分配方式，其中第J 位的取值表示第，架航班所分配的停机位例如编码4 2 5l6 324i6 表示1 0 个航班在6 个停机位上的分配方案：第1 架航班分配到第4 号停机位，第
13、2架航班分配到第z 号停机位，第3 槊航班分配到第5号停机位，以此类推第7 架到达时，占据第2 号停机位的第2 架航班已经离港所以它可以被分配到第z 号停机位该编码方式符合G A 的编码原理，具有不冗余性、合法性、完备性以及L a m a r c k l a n 性质相对于二进制编码，该编码方法直接表示了问题的解也易于解决各类约束条件的满足问题3 2 初始种群的生成在本文的遗传算法的设计中为提高算法的收敛速度，从初始群体的建立到每一代子群体的形成，都采用约束控制手段，使其均为可行解对于初始群体的建立，首先，按照航班进港时间顺序初始化，设为集合F = F ，。F ”，F ”) ，停机位集合按照机
14、场的安排方式记为G = G ，G “，G ； 每个航班的数据包括其割港和离港时问两个数据元，程序设计中用一个二维数组表示旅客转移矩阵设为L 停机位集合用二维数组表示第1 行表示机位序号，第2行表示缓箨机位当前所停放的航班号空闲则为0 对航班集合接照航班顺序依次分配停机位刘长有等：基于遗传算法的机场等机位分配问题研究1 0 7 9首先根据航班和机位信息以及经验值计算出需要的平均空闲时间口和容忍度P ，然后对每架航班分配机位对每架到达的航班，首先检验当前的机位状况，得出空闲机位集合每个停机位必须在其服务的前一航班离开时间至少为。时才为空对于空用机位，为保证空闲时间的相对平衡，设置一个禁忌方案：将当
15、前空闲时间小于口P 的停机位列入禁忌表中，不予分配航班，其中口为平均空闲时问，P 为容忍度解禁规则一是自然解禁，当下一航班到达，该机位的空闲时间大于口一P 时，自然解禁解禁规N - - ，若当前所有空闲机位均不满足可分配条件时，将其中空闲时间最大的机位解禁，即将航班分配到该机位最后在这些允许分配的空闻停机位集合中随机为该航班分配一个停机位循环往下，直到为所有的航班均分配到满足约束的停机位流程图如图1 所示由于每个航班都是随机分配到可用的停机位，所以每次循环都可以得到一个不同的分配方案，循环N 次，即得到种群数量为的一个初始群体毖 彗卜 撵I 缸检查机位状况， 得出空闲机位 集合N G 满足条件
16、C O 非空从C G 中照机为航班分配机位不满足禁 忌条件的机位集合分配该航班到BG 由空闲时间虽大 的机位记录分配信息机位状况改航班分配完 箍出分配方图1初始解产生过程流程3 3适应度计算及遗传算子设计函数乏：乏：凡7 乙扎Y i t 的取值在7 均值左右 r J N t l K且各配置方法所对应该函数值相差较大，目标函数是求其最小值，为保证算法的收敛速度和程序设计的需要，本文设计适应值函数为f i t n e s s = 7 f ，其中7 根据实际数据需要来确定适应函数值越大，所对应的，越小，分配方法越好考虑到遗传算法根本上是一种随机搜索算法，交叉变异等遗传算子可能会将优良的个体破坏，而只保留优良个体的部分基因，最后的群体很可能不是所能搜索到的最优解，而
