多阶段启发式算法求解机场地勤服务优化问题*

唐 非， 刘树安， 董昕禹

(1. 东北大学 信息科学与工程学院， 沈阳 110819； 2. 沈阳工业大学 软件学院， 沈阳 110023； 3. 纽约州立大学石溪分校 计算机系， 美国 石溪 11790-2424)

多阶段启发式算法求解机场地勤服务优化问题*

唐 非1，2， 刘树安1， 董昕禹3

(1. 东北大学 信息科学与工程学院， 沈阳 110819； 2. 沈阳工业大学 软件学院， 沈阳 110023； 3. 纽约州立大学石溪分校 计算机系， 美国 石溪 11790-2424)

针对保障航班离港无延误的地勤服务调度优化问题，建立了以特种车辆数最小化、无效服务时间比率最小化和特种车辆服务时间方差最小化的多目标模型，提出了一种新的多阶段启发式算法.根据航班服务时间窗和特种车辆在航班间服务转移的特点，该算法能够为机场航班合理分配特种车辆，优化航班服务序列.通过仿真实例验证了模型及算法的正确性，结果表明，所提出的多阶段启发式算法提高了特种车辆的服务效率，减少了用车数量和无效服务时间，达到了特种车辆服务的负荷均衡.

延误； 特种车辆； 无效服务时间； 时间方差； 服务时间窗； 多阶段； 松弛时间； 负荷均衡

根据民航局统计，到2015年我国境内有民用机场210个，其中有26个机场的乘客年吞吐量超过1 000万人次、16个机场年起降架次超过20万，导致机场旅客数量、航班到港频次的快速增长和地面运行效率之间的矛盾越发明显.航班延误对社会和经济效益存在着显性或隐性的影响，恢复延误需要通过地勤保障作业、停机位分配、滑行道及路径选择等提高服务效率[1].其中，地勤服务作业是作业项目多环境影响较复杂的重要研究课题，主要包括单航班多服务优化、多航班单服务优化和多航班多服务优化等问题.这些问题主要是对地勤服务进行合理优化调度，降低航班延误带来的损失[2-4].地勤服务组优化调度问题可以看作有时间窗的车辆路径问题(vehicle routing problem with time windows，VRPTW)的一种延伸.VRPTW问题是NP难问题，多采用迭代搜索算法、邻域搜索算法和元启发式搜索算法等非精确算法[5-8].

与VRPTW相比，地勤服务优化问题中特种车辆在航班间服务转移时间相当于VRPTW的路径代价，但是到达航班停机位后需要根据航班的需求继续进行服务保障，这是服务过程的重点.在机场地勤车辆调度的研究中，文献[9]以地勤服务车辆最低数量为目标，采用禁忌搜索算法进行求解，通过拖车服务调度结果可以看出存在一定的可调节时间余量.类似地勤服务优化问题的文献还有很多，但是通过对求解方法的分析并结合VRPTW问题的求解方法可知，地勤服务车辆调度问题很难求得精确最优解.因此，为保障航班无延误离港，本文在满足航班过港服务时间窗约束下，建立了以服务特种车辆数最小化、无效服务时间比率最小化和特种车辆服务时间方差最小化的多目标模型，并提出了一种新的多阶段启发式算法对问题进行求解.

1 多目标模型

1.1 问题描述

一个时段内N架航班进入指定停机位，航班过港时间及航班服务需求等信息均可知.机场有一定数量的资源保障航班的过港服务需求，如清洁车、行李车、加油车和食品车等，通过特种车辆的服务作业使航班满足需求并满足预计离港时间约束.

1.2 变量及假设

本文做出如下假设：

1) 航班需求量不同，服务时间不同，但只需一辆特种车辆完成；

2) 特种车辆同一时刻只能为一个航班提供服务，且一旦开始服务不可中断.

其中，k∈M，l∈Nk.特种车辆k的航班服务集合及航班服务序列编号集合分别表示为Nk={xk，1，xk，2，…，xk，l，…，xnk}和Lk={1，2，…，l，…，nk}，且满足

(1)

1.3 数学模型

机场航班起降频次逐年上升，为其提供地勤保障的特种车辆存在设备老化和维修等状况，在保障不会因地勤服务作业导致航班发生延误的情况下，确定地勤服务的最少用车数量尤为重要.此外，提高服务效率，减少特种车辆无效服务作业时间，并且尽量使特种车辆服务作业均衡也是地勤服务调度的关键指标.本文中无效服务时间指特种车辆在航班间服务的转移和等待服务时间，相反，为航班提供服务作业的时间为有效作业时间.

本文以地勤服务特种车辆数最小化为第一目标，无效服务时间比率最小化为第二目标以及特种车辆服务时间方差最小化为第三目标建立多目标函数模型，其表达式分别为

Z1=minm

(2)

(3)

(4)

s.t

(5)

xk，l≠xk′，l′(k、k′∈M，l、l′∈Lk)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

xk，l=i(i∈N，k∈M，l∈Lk)

(15)

模型中式(2)～(4)表示目标函数；式(5)、(6)表示所有的航班均得到服务，且每个航班只需一辆特种车辆服务；式(7)、(8)表示特种车辆k为航班提供服务的时间约束；式(9)～(12)表示特种车辆k为航班提供服务的结束时间、所有航班的最早服务时间、最晚结束服务时间和服务总时间；式(13)、(14)表示所有车辆的服务总时间及平均服务时间；式(15)表示航班i在特种车辆k的序列l位置.

在模型中涉及到的sign(·)表示为

(16)

2 多阶段启发式算法设计

本文模型为多目标非线性模型，在航班无延误情况下，很难获得特种车辆服务车辆数、无效服务时间和服务作业均衡最优的精确解.根据这个特点基于两阶段启发式算法的思想设计了新的多阶段启发式算法.

2.1 算法的基本思想

本文所设计算法的基本思想是特种服务车辆应尽量满负荷进行服务作业以减少服务车辆数.在此基础上减少无效服务时间，并尽量使车辆的服务作业均衡.因此，多阶段启发式算法包括构造特种车辆航班服务序列初始分配阶段、优化服务系列阶段和均衡特种车辆间服务作业阶段.

算法的第一阶段采用局部邻域搜索方法实现航班的初始分配.航班集合在满足航班离港需求前提下，将航班最大化数量分配给特种车辆，使其为航班提供服务作业.因此，在航班集合中以最迟离港的航班来初始化特种车辆服务序列，以初始航班为基础，采用局部邻域搜索的方法以松弛时间最小优先规则依次对满足时间约束的航班进行初始分配，直到航班集合中没有满足条件的航班.松弛时间Δti是指特种车辆在服务序列相邻的两航班间等待服务的时间.根据式(8)和(15)，Δti的计算表达式为

(17)

如果存在等待服务分配的航班，则特种车辆k的局部邻域搜索范围为符合式(7)、(8)约束的航班.

算法的第二阶段是在初始分配的基础上，采用循环调整服务时间窗的方法尽可能减少无效服务时间，并采用插入法在所有Δtxk，l，k>0中以松弛时间最小优先规则将符合时间约束的航班插入特种车辆服务序列的相应位置.

通过调整服务开始时间循环调节服务时间窗的区间，调整后服务开始时间计算表达式为

(18)

算法的第三阶段在前两阶段的基础上以松弛时间最小优先规则对特种车辆未进行服务的剩余服务时间重新调整航班的分配，尽量使特种车辆服务作业均衡.

2.2 多阶段启发式算法的实现

2) 对特种车辆服务序列进行初始分配.

① 如果N非空，则以N中最迟离港的任意航班初始分配为特种车辆k服务序列末尾位置，并在N中删除该航班，转步骤②；否则转步骤4).

3) 对航班序列进行优化.

② 判断服务序列是否结束，如果是转步骤①.

③ 航班集合N中搜索满足时间约束且可插入特种车辆k服务序列的航班，如果有，以松弛时间最小为原则插入相应位置，调整特种车辆的服务序列和从N中删除该航班，否则转步骤2).

图1 算法流程图Fig.1 Flow chart of algorithm

4) 均衡服务作业.对于提前结束航班服务序列作业的特种车辆，搜索其他车辆服务序列中是否有满足时间约束未开始服务的航班，如果有，按照松弛时间最小原则在车辆间调整服务序列，否则转步骤5).

5) 输出需要的目标函数值Z1、Z2和Z3.

3 仿真结果与分析

算法运行环境为ThinkPad PC i7-4710MQ，CPU为2.50 GHz.

3.1 算例数据

机型h与服务时间之间的关系矩阵为

3.2 仿真结果

根据航班信息表1、转移时间矩阵S和服务时间矩阵P的数据，运行系统得到地勤服务调度方案如表2所示，其中，tk为特种车辆k的服务时间，sg为在航班停机位转移时间，tw为等待服务时间.目标函数值为Z1=4，Z2=13.92%，Z3=16.86.根据表2的地勤服务调度方案，具体地勤服务作业时间计划如图2所示.

表1 航班数据Tab.1 Data of flights

表2 地勤服务调度方案Tab.2 Scheduling schemes for ground service

图2 地勤服务作业时间计划Fig.2 Working time plan for ground service

由表2和图2可以看出，在保障航班无延误情况下，至少需要4辆特种车辆，航班转移和等待的无效服务时间比率较小，航班的工作效率较高，并且特种车辆间的服务负荷相对均衡.

3.3 结果比较

机场地勤服务调度问题作为VRPTW问题的一种延伸，很难获得精确解，对于算法的有效性，本文采用VRPTW常用的启发式算法和遗传算法进行比较.

机场对到港航班进行地勤服务调度所采用的启发式算法为先到先服务(first come first service，FCFS)算法，在相同数据情况下，系统运行获得的地勤服务调度方案如表3所示，目标函数值为Z1=5，Z2=18.92%，Z3=8.03.根据表3地勤服务调度方案，先到先服务地勤服务作业具体时间安排如图3所示.

表3 地勤服务调度方案(FCFS)Tab.3 Scheduling schemes for ground service(FCFS)

图3 地勤服务作业时间计划(FCFS)Fig.3 Working time plan for ground service (FCFS)

对于VRPTW研究中常采用的遗传算法，在相同数据条件下，为保障航班无延误时使用特种车辆数最少，采用逐次增加使用车辆数的方法，不断调整参数多次运行系统，当种群规模参数为500、交叉概率为0.65、变异概率为0.15、最大终止代数为2 000时，获得地勤服务调度方案如表4所示，目标函数值为Z1=5，Z2=18.25%，Z3=33.14.根据表4地勤服务调度方案，采用遗传算法获得的地勤服务作业时间计划如图4所示.

在本文所提算法中，特种车辆服务作业时间安排紧密、空闲时隙较小.三种算法所用地勤服务作业的特种车辆数目分别为4、5和5，目标Z1优势明显；无效服务时间比率分别为13.92%、18.92%和18.25%，目标Z2优势比较明显，另外三种算法的无效服务时间总和分别为104.7、141.8和203.1 min，从时间值上看优势也比较明显，说明服务作业效率是比较有优势的.特种车辆服务作业时间方差分别为16.86、8.03和33.14，在目标Z3服务作业均衡方面居中，比先到先服务算法的服务均衡性稍差.

表4 地勤服务调度方案(GA)Tab.4 Scheduling schemes for ground service (GA)

图4 地勤服务作业时间计划(GA)Fig.4 Working time plan for ground service (GA)

本文提出的多阶段启发式算法在不同计算机上运行时间基本在1～2 s之间，运行得到的调度方案也比较合理，有效减少了地勤服务用车数，减少了服务转移及等待时间，降低了无效服务时间比率，并尽量使特种服务车辆的服务作业负荷均衡.

4 结 论

本文在机场到港航班频次逐年上升环境下，考虑了满足动态到港且服务时间窗约束的航班服务请求，在保障航班不会因地勤服务发生离港延误情况下，提高地勤服务效率，尽量优化地勤服务作业安排.根据服务时间窗的约束条件建立了多目标优化模型，主要考虑地勤服务作业的最少使用特种车辆问题、在不同航班间服务转移及等待服务时间问题和特种车辆之间的服务负荷均衡问题.根据模型特点，在两阶段启发式算法的基础上，提出了一种新的多阶段启发式算法.研究结果表明，提出的模型及算法能够快速反应并较好地为机场提供地勤服务调度方案，提高了特种车辆的服务效率，减少了服务用车及无效的服务时间，保障了航班按时离港.此外，根据调度结果对机场在配置及维护特种车辆的管理方面也具有一定的参考意义.

[1] 丁建立，王新茹，徐涛.航班延误恢复调度的混合粒子群算法 [J].交通运输工程学报，2008，8(2)：90-95.

(DING Jian-li，WANG Xin-ru，XU Tao.Hybrid particle swarm optimization arithmetic for recovery sche-duling of flight delays [J].Journal of Traffic and Transportation Engineering，2008，8(2)：90-95.)

[2] 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.

[3] Lp W H，Wang D，Cho V.Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme [J].IEEE Systems Journal，2013，7(4)：649-657.

[4] Ravizza S，Atkin J A D，Burke E K.A more realistic approach for airport ground movement optimisation with stand holding [J].Journal of Scheduling，2014，17(5)：507-520.

[5] Cattaruzza D，Absi N，Feillet D，et al.An iterated local search for the multi commodity multi trip vehicle routing problem with time windows [J].Computers & Operations Research，2014，51(3)：257-267.

[6] Michallet J，Prins C，Amodeo L，et al.Multi-start ite-ated local search for the periodic vehicle routing problem with time windows and time spread constraints on services [J].Computers & Operations Research，2014，41：196-207.

[7] Jin J，Crainic T G， Løkketangen A.A cooperative parallel metaheuristic for the capacitated vehicle routing [J].Computers & Operations Research，2014，44：33-41.

[8] 刘艳秋，曹歌，张颖，等.基于分组策略的补货配送问题优化模型 [J].沈阳工业大学学报，2017，39(2)：165-169.

(LIU Yan-qiu，CAO Ge，ZHANG Ying，et al.Optimization model for replenishment and distribution problems based on grouping strategy [J].Journal of Shen-yang University of Technology，2017，39(2)：165-169.)

[9] 苟晶晶.机场规划所需地勤保障车辆最低数量预测 [J].中国民航飞行学院学报，2015，27(2)：50-53.

(GOU Jing-jing.Prediction of the minimum requirement of ground vehicles for airport planning [J].Journal of Civil Aviation Flight University of China，2015，27(2)：50-53.)

Multi-phaseheuristicalgorithmforsolvingairportgroundserviceoptimizationproblem

TANG Fei1,2, LIU Shu-an1, DONG Xin-yu3

(1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China; 2. School of Software, Shenyang University of Technology, Shenyang 110023, China; 3. Computer Science Department, Stony Brook University, Stony Brook 11790-2424, USA)

Aiming at the ground service scheduling optimization problem without the departure delay in airport, a multi-objective model which could minimize the quantity of special vehicles, the ratio of invalid service time and the service time variance for special vehicles was established, and a multi-phase heuristic algorithm was proposed. According to the features of airline service time window and the mobility of special vehicles service between flights, the allocation of special vehicles for the airpaort flights could be arranged with the proposed algorithm, and the flight service sequence could be optimized. Through the simulation examples, the correctness of both model and algorithm was proved. The results show that the proposed multi-phase heuristic algorithm improves the service efficiency of special vehicles, reduces the quantity of used vehicles and the time of invalid service, and achieves the workload balance of special vehicles.

delay; special vehicle; invalid service time; time variance; service time window; multi-phase; slack time; workload balance

2017-03-06.

国家自然科学基金面上项目(71571037).

唐 非(1975-)，女，辽宁北镇人，讲师，博士生，主要从事系统建模、系统优化与分析等方面的研究.

* 本文已于2017-10-25 21∶13在中国知网优先数字出版. 网络出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20171025.2113.072.html

10.7688/j.issn.1000-1646.2017.06.12

TP 18

A

1000-1646(2017)06-0664-06

(责任编辑：钟 媛 英文审校：尹淑英)