唐非^1,2, 刘树安¹
1. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 沈阳工业大学 软件学院, 辽宁 沈阳 110023
收稿日期：2017-07-01
基金项目：国家自然科学基金资助项目(71571037)。
作者简介：唐非(1975-), 女, 辽宁北镇人, 东北大学博士研究生。

摘要：为了减少地勤服务作业调度影响的航班延误, 以总航班延误最小化及航班延误方差最小化为目标建立了多目标非线性整数优化模型.地勤服务作业调度优化问题是NP难问题, 因此, 提出了一种双重变异单亲遗传算法求解该类问题.该算法避免了遗传算法求解同类问题时产生非法个体的现象, 并且双重变异策略具有全局搜索能力.结果表明:双重变异单亲遗传算法可以很好地解决航班分配服务组及服务组内航班服务序列优化的地勤服务调度问题, 减少了因地勤服务作业导致的航班总延误, 避免了单个航班长时间延误.
关键词：机场地勤服务总航班延误最小化延误方差最小化多目标非线性整数优化模型双重变异单亲遗传算法
Double-Mutation Partheno-Genetic Algorithm for Airport Ground Service Optimization
TANG Fei^1,2, LIU Shu-an¹
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. College of Software, Shenyang University of Technology, Shenyang 110023, China
Corresponding author: TANG Fei, E-mail: 446092364@qq.com
Abstract: In order to reduce the flight delays caused by airport ground service task scheduling, a multi-objective nonlinear integer optimization model was established to minimize total flight delays and flight delay variance. Ground service task scheduling optimization is an NP-hard problem, so, a double-mutation partheno-genetic algorithm was proposed to solve this problem. The algorithm avoids the phenomenon that the genetic algorithm generates illegal individuals when solving similar problems, and the double-mutation strategy has global search capability. The simulation result showed that the double-mutation partheno-genetic algorithm can solve the ground service scheduling optimization problem including assignment of service teams to airlines and airline-service sequence optimization inside a service team, reduce the total flight delays caused by ground service tasks and avoid long single-flight delay.
Key words: airport ground serviceminimize total flight delaysminimize delay variancemulti-objective nonlinear integer optimization modeldouble-mutation partheno-genetic algorithm
民航业对社会和经济的影响有目共睹, 机场地勤服务作业是保障航班飞行安全和正常过港的关键环节^[1].航班延误问题是困扰民航业的世界性问题, 而航班延误到港及地勤服务作业是导致航班延误的两大重要因素^[2-3].高效的地勤服务作业调度是降低航空公司成本的重要途径和重要研究课题^[4].
由于机场地勤服务环境复杂及航班到港时间波动的不确定性使机场地勤服务安排很难获得追求目标的最优解决方案.目前, 减少航班延误进行的地勤服务优化调度研究主要涉及地勤服务组的服务作业路径规划、航班分配服务组和服务组内航班服务顺序安排等几个方面.Mao等^[5]采用遗传算法解决了航班延误总成本和地勤服务利用率问题.Ho等^[6]采用禁忌搜索算法解决配餐服务作业调度问题, 但是并没有考虑停机位置因素的影响.Ball等^[7]采用距离优先(转化为时间最短优先)启发式算法实现地勤服务调度问题.Vossen等^[8]采用服务时间槽内航班平均延误小的优先启发式算法解决了航班总延误问题.Ip等^[9]采用遗传算法对航班延误问题求解, 但在进化过程中会产生非法解, 需要对个体进行合法化.Han等^[10]采用模糊关键路径方法进行求解, 但没有考虑单个航班延误时间过长的问题.
上述研究在解决航班总延误、平均延误等问题的过程中, 没有考虑单个航班延误时间过长、服务组工作效率差别或航班服务需求量差别等因素.为了更符合机场地勤服务作业的实际过程, 本文综合考虑航班服务时间窗、航班需求量、服务组工作效率不同及停机位距离因素影响的地勤服务优化问题.首先建立了以总航班延迟时间最小化、航班延误方差最小化为目标的非线性整数优化模型, 提出求解此类地勤服务调度优化问题的双重变异单亲遗传算法.通过对高峰时段航班数据及调整算法参数进行仿真实验, 并与同类问题的其他文献进行比较, 证明本文所提算法具有一定的优越性.
1 地勤服务优化问题描述及模型1.1 问题描述机场地勤服务问题可以描述如下:一段时间内有N架航班到达机场指定停机位并提出N个地勤服务请求, 其服务请求由M个地勤服务组完成, i表示航班序号, k表示停机位, m表示服务组编号, 且有i∈N, k∈K, m∈M.航班i的理想服务时间窗为[e_i, l_i, ], e_i表示航班到港时间, 是允许地勤服务组进行服务的最早时刻; l_i表示航班计划离港时间, 是不会导致航班发生延误的地勤服务结束的最晚时间.航班i的服务作业时间与机型及服务组有关, 表示为t_{i, m}^h, h表示机型且有h∈H.服务组为停机位置k′, k的航班i′, i服务时的转移时间为t_{k′, k}, 以g(i)表示航班i的停机位置获取函数, 则t_{k′, k}可以表示为t_{g(i′), g(i)}.
优化目标是如何分配航班到服务组及服务组内航班服务的顺序, 使得总航班延误时间最短, 同时避免单个航班延误时间过长.
1.2 多目标非线性整数优化模型本文作如下假定:
1) 所有航班的服务请求必须得到满足, 且每个航班的服务请求只需1个服务组完成;
2) 服务结束时刻为满足航班离港的最早时刻.
决策变量定义如下:

(1)

式中:x_{j, s}表示航班i分配给服务组j的航班服务序列位置s进行服务作业.其中, s的最大值为N_j, N_j表示服务组j进行服务作业的航班数, 其值是未知的, 由最后的分配方案决定.
航班i的服务完成时间可以表示为t_i或t_{xj, s}, 延误时间可表示为d_i或d_{xj, s}, 这里的延误是指航班晚于计划离港时刻离港, 航班的平均延误时间表示为.本文建立总航班延误最小化和航班延误方差最小化为目标的数学模型:

(2)

(3)

(4)

(5)

(6)

(7)

模型中涉及的函数sign(·)为二值函数:

(8)

式(2)和式(3)分别表示总航班延误最小化和航班延误方差最小化目标函数.式(4)表示所有航班均被分配服务组进行服务, 且只需服务组一次完成服务.式(5)表示航班的服务完成时间, 其值满足航班的开始时间约束和服务组航班服务序列的服务约束.式(6)和式(7)表示航班的延误时间及航班平均延误时间.
上述问题是一个典型的组合优化问题, 可以归结为带有时间窗的车辆路径问题, 其不同之处在于地勤服务过程取代车辆路径问题的交付货物, 并且服务时间在整个地勤服务过程中占据比重更大.地勤服务组和航班的合理、有效组合及服务组内服务序列顺序优化是非常复杂的NP难问题.从决策变量的定义可以计算每个航班对服务组有M种分配, 每个服务组服务序列有N_j!种排列, 因此, 解决方案空间N_s大小为

(9)

由式(9)知, 随着问题规模的增大, 最优解决方案的空间规模将非常大.单亲遗传算法解决组合优化问题时保留了遗传算法的遗传特征, 并且计算量相对减少, 在避免“早熟收敛”和寻优效率方面均有优势.因此, 本文提出了一种新的双重变异单亲遗传算法解决地勤服务调度优化问题.
2 双重变异单亲遗传算法设计2.1 编码方案地勤服务优化的目标是航班总延误的最小化和航班延误方差最小化, 根据决策变量可知对模型的求解包括为航班分配服务组和安排航班服务顺序两个层次的调度.因此, 合理、可行编码方案应具有以下几个特点:
1) 既能体现航班分配服务组又能体现服务组内航班服务顺序, 同时能够表达地勤服务调度的所有可能方案;
2) 易于解码，通过遗传操作获得更合适的编码;
3) 编码具有可行性、合法性和唯一性.
因此, 本文设计了既包含航班分配服务组信息又包含服务组内服务顺序信息的实数编码方案, 实数的整数部分代表航班分配的服务组, 小数部分代表航班在服务组内的服务顺序序列.染色体的长度为服务请求的航班数, 基因的序列位置对应航班序号.根据以上论述可以将N架航班M个地勤服务组算法的编码描述为

(10)

染色体位串长为N, 染色体从左到右依次产生合法的基因x_i, x_i取值范围为[1, M+1), 因为有M个服务组, 避免产生编号为M+1的服务组, 所以采用半开半闭区间.
为了更好地描述编码方案, 以8架航班、2个服务组的染色体编码为例, 随机产生染色体X, 则X对应的地勤服务调度方案如图 1所示.
图 1(Fig. 1)

图 1 地勤服务调度方案示意图Fig.1 Ground service scheduling scheme

在模型中决策变量x_{j, s}的取值i代表航班号, j代表服务组编号, s代表服务组内服务顺序序列.因此, 8架航班表示决策变量的取值为1~8, 对应染色体的基因序列位置且染色体的长度为8, 满足约束(4)所有航班均需得到服务保障且仅需要一个服务组; 2个服务组构成实数基因的整数部分, 取值代表服务组编号1和2;根据编码方案从左到右依次产生[1, 3)之间实数构成的染色体.图 1清楚地显示了染色体代表的地勤服务调度方案, 根据编码方案可知服务组1的航班服务顺序序列为航班号2-4-8-7, 服务组2的航班服务顺序序列为航班号3-1-6-5.
2.2 初始种群产生过程根据编码方案产生初始种群过程如下:
1) 根据请求服务的航班数N及服务组数M确定染色体的结构;
2) 设定种群规模, 根据编码方案随机产生基因值为[1, M+1)区间实数的染色体, 形成初始种群.
2.3 遗传操作单亲遗传算法的遗传过程有换位变异、移位变异和倒位变异, 且这几种变异操作是等价的.
针对本文的地勤服务调度问题, 在每一代进化中, 上述3种变异方式只能改变染色体基因的位置, 均不会改变染色体基因值, 即通过变异改变航班分配服务组编号和服务组内的航班服务顺序序列, 从而使进化过程不能满足全局搜索.但是, 根据模型可知服务组服务的航班数是不确定且可调整的, 因而, 在遗传过程中应具备搜索到所有可能调度方案的能力.受限于种群规模, 初始种群中不可能产生所有的服务组与分配航班数的组合, 最终可能导致算法求解时失去更好的调度方案.因此, 本文在移位变异的基础上, 设计了新的双重变异策略.
所谓双重变异是指在移位变异的基础上, 增加一种小概率基因变异, 使同一染色体执行两种变异操作, 即对种群中的个体依据变异概率P_m1移位变异, 使航班重新分配服务组和服务序列, 依据变异概率P_m2进行基因变异调整服务组内的航班数.双重变异示意图如图 2所示.
图 2(Fig. 2)

图 2 双重变异示意图Fig.2 Double mutation

双重变异过程描述如下:
1) 按照变异概率P_m1随机选择种群中的染色体;
2) 随机产生[1, N]之间的2个随机数u₁, u₂, 对2个位置之间的基因执行移位变异操作;
3) 根据变异概率P_m2在2)的基础上计算染色体变异的基因个数, 随机选择[1, N]区间位置的基因并随机产生[1, M+1)的值进行基因变异操作.
通过双重变异操作为航班和服务组进行不同的组合分配及航班服务顺序序列优化, 并且地勤服务作业调度按照自然进化规律不会产生非法基因, 有利于在所有可能的解决方案空间搜索到更好的解.
2.4 选择策略模型的目标函数Z₁(x)和Z₂(x)是离港总航班延误最小化和航班延误方差最小化, 种群中的染色体X对应着一种地勤服务调度解决方案, 其染色体的适值优化方向与目标函数优化方向相反, 因此可以确定适值函数为

(11)

根据地勤服务优化追求目标的重要程度将Z₁(x)和Z₂(x)以加权和方式表示为一个单目标函数, 加权系数α和β满足α+β=1, γ为极小的正数, 防止当所有航班均未发生延误时分母为零的情况.Z₁(x)和Z₂(x)的计算必须满足式(5)~式(7)的航班服务时间窗和航班服务序列约束.另外, 为了减少计算量, 子代染色体适值计算时可在父代染色体的基础上根据式(5)~式(7)计算差异的部分即可.
为了保证种群中染色体适值的合理差距, 避免出现早熟收敛现象, 保持恒定的选择压力, 针对最小化问题采用正规化方法将原适值函数映射为动态标定适值:

(12)

式中:f_max和f_min分别表示种群中适值最高的染色体和适值最低的染色体；为了防止分母为零, 设定ε为一个极小的正数.
选择是按照选择策略从父辈种群中选择染色体进入子代的过程.选择的过程中为了保证父代与子代个体具有平等的竞争机会, 采用正比选择策略在父代和子代共同组成的扩大种群中完成选择操作.同时为了保障进化过程中最优染色体不会消失, 在正比选择的基础上保留最优染色体, 即采用正比选择+精英个体保留策略.
3 数据实验与结果分析3.1 数据采集为了能够切实解决机场繁忙时段的地勤服务调度问题, 验证所提模型及算法的实用性, 选取某大型机场密集时段到港的100架航班数据, 包括机型、停机位、到港时间和计划离港时间等信息, 其航班数据表如表 1所示.
表 1(Table 1)

表 1 航班数据Table 1 Flight data 序号 机型 停机位 到港时刻 计划离港时刻 1 1 5 09:00 10:10 2 2 3 09:00 10:20 3 3 4 09:05 10:20 4 3 8 09:05 10:15 5 3 7 09:05 10:15 ? ? ? ? ? 97 1 4 10:50 13:00 98 3 2 10:55 12:05 99 1 3 10:55 12:15 100 2 5 11:00 12:05

表 1 航班数据 Table 1 Flight data

由于机场地勤服务组实际工作中服务效率不同, 因此, 本文仿真实验由2种效率的8个服务组完成, 其作业时间(min)与机型关系如表 2所示.
表 2(Table 2)

表 2 服务组作业时间与机型关系Table 2 Relationship between service crew job time and flight type min 机型 服务组1~4号 服务组5~8号 1 12 10 2 10 8 3 7.5 6

表 2 服务组作业时间与机型关系 Table 2 Relationship between service crew job time and flight type

根据服务组在不同停机位间的实际距离和转移速度, 将服务组在1~8号停机位之间转移时间(min)表示为矩阵T.

(13)

3.2 运行结果及分析系统运行时, 采用最大遗传代数终止准则, 根据表 1、表 2和式(12)调整算法参数：种群规模为500, 变异概率P_m1=0.55, P_m2=0.15, 最大遗传代数为2000, 适值函数α为0.9, β为0.1时, 系统运行20次后求得的平均航班总延误曲线如图 3所示.
图 3(Fig. 3)

图 3 平均总延误最好值进化曲线Fig.3 Evolution curve of optimal values of average total delay

从图 3可以看出, 在进化代数较小时很难获得比较好的解, 随着进化代数增加，在1000代左右最好值趋于平稳, 可获得比较满意的航班总延误目标值.根据系统多次运行获得的结果也说明了本文提出算法具有收敛性、有效性.
多次运行得到最好解为
系统运行获得的最优解对应的地勤服务调度结果如表 3所示.
表 3(Table 3)

表 3 地勤服务调度结果Table 3 Scheduling results of ground service 服务组号 航班服务序列 1 3, 11, 27, 34, 48, 64, 73, 75, 89, 88, 87, 83 2 2, 8, 13, 26, 37, 47, 57, 76, 82, 90, 96, 100, 79 3 4, 12, 20, 15，38, 58, 65, 61, 78, 93, 85, 94 4 1, 9, 18, 28, 36, 43, 46, 71, 70, 86, 74, 72, 81 5 5, 19, 23, 35, 51, 54, 67, 69, 68, 66, 77, 84, 98, 99 6 6, 17, 14, 24, 30, 41, 49, 63, 62, 60, 50, 59, 92, 55 7 10, 15, 22, 29, 25, 42, 52, 45, 44, 53, 95, 91 8 7, 16, 21, 33, 32, 31, 39, 40, 56, 80, 97

表 3 地勤服务调度结果 Table 3 Scheduling results of ground service

根据表 1、表 3及图 4可知有2架航班发生延误, 分别是服务组6的59号航班延误5.8min和服务组7的53号航班延误2.1min, 根据航空局的航班离港延误定义，小于等于15min的延误可视为非延误.由此可见, 本算法可为此类地勤服务调度问题提供比较满意的解决方案.
图 4(Fig. 4)

图 4 地勤服务调度方案Fig.4 Scheduling plan of ground service

由表 3对应的地勤服务调度方案如图 4所示.
另外, 根据调度结果, 模型中的目标函数min Z₁=7.9min, min Z₂=2.62min, 最长和最短延误分别为5.8和2.1min, 平均延误4min, 可见航班总延误时间较短, 并且避免了某架航班延误时间过长.
3.3 结果比较将本文提出的双重变异单亲遗传算法(DMGA)与同类问题文献[8]所提的混合编码遗传算法(HEGA)、文献[7]所提的距离优先启发式算法(DPHA)和机场普遍实行的先到先服务启发式算法(FCFS)进行比较, 在比较的过程中均选择表 2所示的8个服务组, 结果如表 4所示.
表 4(Table 4)

表 4 结果比较Table 4 Comparison of results min 项目 DMGA HEGA DPHA FCFS 延误航班数 2 10 16 7 总延误时间 7.9 109.1 235.8 83.6 最长延误时间 5.8 37 43.2 27.3 最短延误时间 2.1 0.7 0.9 1.7 平均延误时间 3.95 10.91 14.74 11.94 系统运行时间 17~35 20~38 6~9 5~7

表 4 结果比较 Table 4 Comparison of results

由表 4可知:
1) DMGA的运行结果在延误航班数量、总延误时间、最长延误时间和平均延误时间方面优势比较明显.
2) DMGA运行时间与DPHA和FCFS算法相比稍长, 但是仍然在可接受的运行时间获得了比较满意的解决方案, 有效地减少了航班总延误时间, 避免了单个航班延误时间过长.
3) 根据前述式(9)可知地勤服务调度方案空间非常大, 并且受到航班停机位置、实际到港时间等因素的影响, 任何的启发式算法都可能陷入局部最优, 通过几种算法的对比, 可以看出本文提出的算法可以在某种程度上取得更好的解决方案.验证了本文模型和算法在解决同类地勤服务调度问题时的有效性和实用性.
4 结论1) 本文提出的地勤服务作业调度优化问题有效地减少了航班的总延误时间，并避免了个别航班延误时间过长, 提高了地勤服务的效率.
2) 根据模型特点提出了双重变异单亲遗传算法, 有效地解决了地勤服务调度问题.通过仿真获得的航班分配服务组及服务作业时间序列优化结果是比较满意的、可行的地勤服务调度方案.
3) 通过与不同算法运行结果比较均说明了本文所建模型和算法的有效性和实用性.
参考文献

[1]	Berrittella M, Franca L L, Zito P. An analytic hierarchy process for ranking operating costs of low cost and full service airlines[J].Journal of Air Transport Management, 2009, 15(5): 249–255.DOI:10.1016/j.jairtraman.2008.11.006
[2]	马正平, 崔德光. 机场航班延误优化模型[J].清华大学(自然科学版), 2004, 44(4): 474–477, 484. ( Ma Zheng-ping, Cui De-guang. Optimizing airport flight delays[J].Journal of Tsinghua University(Science and Technology), 2004, 44(4): 474–477, 484.)
[3]	樊玮, 吴建波, 衡红军. 基于多Agent的机场地面服务车辆调度方法研究[J].计算机应用与软件, 2015, 32(10): 256–259. ( Fan Wei, Wu Jian-bo, Heng Hong-jun. Research on multi-agent based dispatching method for airport ground service vehicles[J].Computer Applications and Software, 2015, 32(10): 256–259.DOI:10.3969/j.issn.1000-386x.2015.10.061)
[4]	Trabelsi F S, Cosenza C.Managing uncertainty at airports ground handling[C]// Airports in Urban Networks.Paris, 2014: 1-8.
[5]	Mao X, Roos N, Salden A.Stable multi-project scheduling of airport ground handling services by heterogeneous agents[C]//8th International Conference on Autonomous Agents and Multiagent Systems.Budapest, 2009: 537-544.
[6]	Ho S C, Leung J M Y. Solving a manpower scheduling problem for airline catering using metaheuristics[J].European Journal of Operational Research, 2010, 202(3): 903–921.DOI:10.1016/j.ejor.2009.06.030
[7]	Ball M O, Lulli G. Ground delay programs:optimizing over the included flight set based on distance[J].Air Traffic Control Quarterly, 2016, 12(1): 1–25.
[8]	Vossen T, Ball M. Optimization and mediated bartering models for ground delay programs[J].Naval Research Logistics, 2006, 53(1): 75–90.DOI:10.1002/(ISSN)1520-6750
[9]	Ip W H, Wang D, Cho V. Aircraft ground service scheduling problems and their genetic algorithm with assignment and sequence encoding scheme[J].IEEE Systems Journal, 2013, 7(4): 649–657.DOI:10.1109/JSYST.2012.2196229
[10]	Han T C, Chung C C, Liang G S. Application of fuzzy critical path method to airport's cargo ground operation systems[J].Journal of Marine Science & Technology, 2006, 14(3): 139–146.