第39卷 第6期
2 0 1 7 年 1 1 月
沈 阳 工 业 学 学 报
Journal of Shenyang University of Technology
Vo l 39 No 6
Nov 2 0 1 7
收稿日期 2017 － 03 － 06．
基金项目 国家然科学基金面项目( 71571037) ．
作者简介 唐 非( 1975 － )女辽宁北镇讲师博士生事系统建模系统优化分析等方面研究．
* 文已 2017 － 10 － 25 21 ∶ 13 中国知网优先数字出版． 网络出版址 http ∥www． cnki． netkcmsdetail21． 1189． T．
20171025． 2113． 072． html
doi 10． 7688 j． issn． 1000 － 1646． 2017． 06． 12
阶段启发式算法求解机场勤服务优化问题*
唐 非12 刘树安1 董昕禹3
( 1 东北学 信息科学工程学院沈阳 110819 2 沈阳工业学 软件学院沈阳 110023 3 纽约州立学石溪分校 计算机系
美国 石溪 11790 － 2424)
摘 针保障航班离港延误勤服务调度优化问题建立特种车辆数化效服
务时间率化特种车辆服务时间方差化目标模型提出种新阶段启发式
算法． 根航班服务时间窗特种车辆航班间服务转移特点该算法够机场航班合理分
配特种车辆优化航班服务序列． 通仿真实例验证模型算法正确性结果表明提出
阶段启发式算法提高特种车辆服务效率减少车数量效服务时间达特种车
辆服务负荷均衡．
关 键 词 延误 特种车辆 效服务时间 时间方差 服务时间窗 阶段 松弛时间 负荷均衡
中图分类号 TP 18 文献标志码 A 文章编号 1000 － 1646( 2017) 06 － 0664 － 06
Multiphase heuristic algorithm for solving airport
ground service optimization problem
TANG Fei12 LIU Shuan1 DONG Xinyu3
( 1． School of Information Science ＆ EngineeringNortheastern UniversityShenyang 110819China 2． School of Software
Shenyang University of TechnologyShenyang 110023China 3． Computer Science DepartmentStony Brook University
Stony Brook 117902424USA)
Abstract Aiming at the ground service scheduling optimization problem without the departure delay in
airporta multiobjective model which could minimize the quantity of special vehiclesthe ratio of invalid
service time and the service time variance for special vehicles was establishedand a multiphase heuristic
algorithm was proposed． According to the features of airline service time window and the mobility of special
vehicles service between flightsthe allocation of special vehicles for the airpaort flights could be arranged
with the proposed algorithmand the flight service sequence could be optimized． Through the simulation
examplesthe correctness of both model and algorithm was proved． The results show that the proposed
multiphase heuristic algorithm improves the service efficiency of special vehiclesreduces the quantity of
used vehicles and the time of invalid serviceand achieves the workload balance of special vehicles．
Key words delay special vehicle invalid service time time variance service time window multiphase
slack time workload balance
根民航局统计 2015 年国境民
机场 210 中 26 机场客年吞吐量超
1 000 万 次16 机 场 年 起 降 架 次 超
20 万导致机场旅客数量航班港频次快速
增长面运行效率间矛盾越发明显． 航班
延误社会济效益存着显性隐性影响恢复延误需通勤保障作业停机位分
配滑行道路径选择等提高服务效率［1］． 中
勤服务作业作业项目环境影响较复杂重
研究课题包括单航班服务优化航班
单服务优化航班服务优化等问题． 问
题勤服务进行合理优化调度降低航
班延误带损失［2 － 4］． 勤服务组优化调度问
题作时间窗车辆路径问题( vehicle
routing problem with time windowsVＲPTW)
种延伸． VＲPTW 问题 NP 难问题采迭代
搜索算法邻域搜索算法元启发式搜索算法等
非精确算法［5 － 8］．
VＲPTW 相勤服务优化问题中特种
车辆航班间服务转移时间相 VＲPTW 路
径代价达航班停机位需根航班
需求继续进行服务保障服务程重点．
机场勤车辆调度研究中文献［9］勤服
务车辆低数量目标采禁忌搜索算法进行
求解通拖车服务调度结果出存定
调节时间余量． 类似勤服务优化问题文
献通求解方法分析结合
VＲPTW 问题求解方法知勤服务车辆调
度问题难求精确优解． 保障航班
延误离港文满足航班港服务时间窗约束
建立服务特种车辆数化效服务时
间率化特种车辆服务时间方差化
目标模型提出种新阶段启发式算
法问题进行求解．
1 目标模型
1 1 问题描述
时段 N 架航班进入指定停机位航班
港时间航班服务需求等信息均知． 机场
定数量资源保障航班港服务需求清
洁车行李车加油车食品车等通特种车辆
服务作业航班满足需求满足预计离港时间
约束．
1 2 变量假设
文做出假设
1) 航班需求量服务时间需
辆特种车辆完成
2) 特种车辆时刻航班提供
服务旦开始服务中断．
模型建立程中涉变量包括 航班序号
iN 港航班集合N { 12…i…n} 航
班港服务时间窗［T e
i T d
i ］T e
i 航班 i 允许服务
时间T d
i 航班 i 离港时间 航班服务时间 Pi
航班停机位置获取函数 g( i)特种车辆
航班 ij 间转移时间 s ij 表 示
s g( i)g( j) 特种车辆 序 号 kM 特种车辆集合
M { 12…k…m} 特种车辆 k 服务开始时
间 ts
k 特种车辆 k 服务结束时间 te
k 特种车辆 k
服务时间 tk 特种车辆总服务时间 t．
模型建立程中涉决策变量包括 特
种车辆 k 航班 i 提供服务开始时间 ts
ik 特种
车辆 k 航班 i 提供服务结束时间 te
ik 航班 i
服务请求否分配特种车辆 k 服务序列 l
位置 xkl
xkl i ( i∈N)
0 (
{ )
中k∈Ml∈Nk ． 特种车辆 k 航班服务集合
航班服务序列编号集合分表示 Nk { xk1
xk2 …xkl …xnk
} L k { 12…l…nk }
满足
∑
m
k 1
nk n ( 1)
1 3 数学模型
机场航班起降频次逐年升提供勤
保障特种车辆存设备老化维修等状况
保障会勤服务作业导致航班发生延误情
况确定勤服务少车数量尤重．
外提高服务效率减少特种车辆效服务作业时
间量特种车辆服务作业均衡勤
服务调度关键指标． 文中效服务时间指特
种车辆航班间服务转移等服务时间相
反航班提供服务作业时间效作业时间．
文勤服务特种车辆数化第目
标效服务时间率化第二目标特
种车辆服务时间方差化第三目标建立目
标函数模型表达式分
Z1 min m ( 2)
Z2 min
t－∑
n
i 1
Pi
t ( 3)
Z3 min ( tk － 珋tk )槡 2 ( 4)
s． t
∑
m
k 1
∑
nk
l 1
sign( xkl ) n ( 5)
xkl ≠xk＇l＇ ( kk＇∈Mll＇∈L k )( 6)
T d
xkl － Pxkl ≥ts
xklk ≥T e
xkl
( k∈Ml∈L k )( 7)
ts
xklk － s g( xkl － 1)g( xkl) ≥te
xkl － 1k ( k∈Ml∈L k )( 8)
566第 6 期 唐 非等 阶段启发式算法求解机场勤服务优化问题te
xklk ( ts
xklk + Pxkl
)·sign( xkl)( k∈Ml∈Lk)( 9)
te
k max
i
{ te
xkll·sign( xkl )}( k∈Ml∈L k )( 10)
ts
k min
i
{ ts
xkll·sign( xkl )}( k∈Ml∈L k )( 11)
tk te
k － ts
k ( k∈M)( 12)
t ∑
m
k 1
tk ( k∈M)( 13)
珋tk t
m ( k∈M)( 14)
xkl i ( i∈Nk∈Ml∈L k )( 15)
模型中式( 2) ～ ( 4) 表示目标函数 式( 5) ( 6)
表示航班均服务航班需
辆特种车辆服务 式( 7) ( 8) 表示特种车辆 k
航班提供服务时间约束 式( 9) ～ ( 12) 表示特
种车辆 k 航班提供服务结束时间航班
早服务时间晚结束服务时间服务总时
间 式( 13) ( 14) 表示车辆服务总时间
均服务时间 式( 15) 表示航班 i 特种车辆 k
序列 l 位置．
模型中涉 sign(·) 表示
sign( y) 1 ( y ＞ 0)
0 ( y≤0
{ ) ( 16)
2 阶段启发式算法设计
文模型目标非线性模型航班延
误情况难获特种车辆服务车辆数效服
务时间服务作业均衡优精确解． 根
特点基两阶段启发式算法思想设计新
阶段启发式算法．
2 1 算法基思想
文设计算法基思想特种服务车辆
应量满负荷进行服务作业减少服务车辆数．
基础减少效服务时间量车辆
服务作业均衡． 阶段启发式算法包括构造
特种车辆航班服务序列初始分配阶段优化服务
系列阶段均衡特种车辆间服务作业阶段．
算法第阶段采局部邻域搜索方法实现
航班初始分配． 航班集合满足航班离港需求
前提航班化数量分配特种车辆
航班提供服务作业． 航班集合中迟
离港航班初始化特种车辆服务序列初始
航班基础采局部邻域搜索方法松弛时
间优先规次满足时间约束航班进行
初始分配直航班集合中没满足条件航班．
松弛时间 Δti 指特种车辆服务序列相邻两
航班间等服务时间． 根式( 8) ( 15)Δti
计算表达式
Δtxklk ts
xklk － s g( xkl － 1)g( xkl) － te
xkl － 1k
( k∈Ml∈L k )( 17)
果存等服务分配航班特种车辆 k
局部邻域搜索范围符合式( 7) ( 8) 约束航班．
算法第二阶段初始分配基础采
循环调整服务时间窗方法减少效服
务时间采插入法 Δtxklk ＞ 0 中松弛
时间优先规符合时间约束航班插入特
种车辆服务序列相应位置．
通调整服务开始时间循环调节服务时间窗
区间调整服务开始时间计算表达式
ts
xklk min{ T e
xkl
ts
xklk － Δtxkl
}
( k∈Ml∈L k )( 18)
算法第三阶段前两阶段基础松弛
时间优先规特种车辆未进行服务剩余
服务时间重新调整航班分配量特种车辆
服务作业均衡．
2 2 阶段启发式算法实现
根算法设计思想针航班港服务时
间窗［T e
i T d
i］约束勤服务作业问题设计
阶段启发式算法． 算法流程图图 1 示
实现程
1) 输入港航班集合 N 航班相关信
息包括航班服务时间窗［T e
i T d
i ］停机位置 g
航班服务时间 Pi 初始化航班 te
i T d
i ．
2) 特种车辆服务序列进行初始分配．
① 果 N 非空 N 中迟离港意
航班初始分配特种车辆 k 服务序列末尾位置
N 中删该航班转步骤② 否转步骤 4) ．
② 根式( 7) ( 8) 采局部邻域搜索方法
松弛时间优先规 N 中次符合条
件意航班分配特种车辆 k N 中删该
航班计算航班 ts
xklk te
xklk Δtxklk 直没
符合条件航班转步骤 3) ．
3) 航班序列进行优化．
① 航班服务序列中序判断否存未标
记航班 Δtxklk ＞0 航班果根式( 18)
重新计算 ts
xklk te
xklk Δtxklk ts
xklk T e
xkl
航
班标记调整服务时间窗结束转步骤②否转
步骤③．
② 判断服务序列否结束果转步骤①．
③ 航班集合 N 中搜索满足时间约束插
入特种车辆 k 服务序列航班果松弛时
间原插入相应位置调整特种车辆服
务序列 N 中删该航班否转步骤 2) ．
666 沈 阳 工 业 学 学 报 第 39 卷图 1 算法流程图
Fig 1 Flow chart of algorithm
4) 均衡服务作业． 提前结束航班服务序
列作业特种车辆搜索车辆服务序列中
否满足时间约束未开始服务航班果
松弛时间原车辆间调整服务序列否
转步骤 5) ．
5) 输出需目标函数值 Z1 Z2 Z3 ．
3 仿真结果分析
算法运行环境 ThinkPad PC i74710MQ
CPU 2 50 GHz．
3 1 算例数
选取首国际机场某日 8∶00 10∶00 港
部分航班例算法进行验证． 航班序号 i航班类
型 h停机位 g 服务时间窗［T e
i T d
i］等 40 架航班
服务数表 1 示． 特种车辆 8 停机位转
移时间矩阵
S
0 0 2 0 1 5 2 0 3 8 5 0 5 3 6 0
2 0 0 0 1 6 2 8 3 3 3 5 4 2 5 5
1 5 1 6 0 0 3 3 4 3 4 8 4 6 5 9
2 0 2 8 3 3 0 0 1 2 5 4 5 7 6 0
3 8 3 3 4 3 1 2 0 0 5 8 6 2 6 1
5 0 3 5 4 8 5 4 5 8 0 0 2 0 1 9
5 3 4 2 4 6 5 7 6 2 2 0 0 0 2 2
6 0 5 5 5 9 6 0 6 1 1 9 2 2 0 0
机型 h 服务时间间关系矩阵
P 1 2 3[]20 15 10
3 2 仿真结果
根航班信息表 1转移时间矩阵 S 服务
时间矩阵 P 数运行系统勤服务调度
方案表 2 示中tk 特种车辆 k 服务时
间s g 航班停机位转移时间tw 等服务
时间． 目标函数值Z1 4Z2 13 92 Z3
766第 6 期 唐 非等 阶段启发式算法求解机场勤服务优化问题表 1 航班数
Tab 1 Data of flights
i h g T e
i T d
i
1 1 5 8∶ 00 9∶ 10
2 2 3 8∶ 00 9∶ 20
3 2 1 8∶ 05 9∶ 20
4 1 4 8∶ 05 9∶ 05
5 3 8 8∶ 10 9∶ 30
6 2 1 8∶ 20 9∶ 35
7 1 3 8∶ 25 9∶ 40
8 3 4 8∶ 30 9∶ 45
9 1 5 8∶ 30 9∶ 40
10 2 4 8∶ 40 9∶ 45
11 1 2 8∶ 40 9∶ 45
12 2 2 8∶ 45 10∶ 00
13 1 4 8∶ 50 10∶ 05
14 3 2 8∶ 50 10∶ 00
15 2 1 8∶ 55 10∶ 05
16 1 5 8∶ 55 10∶ 20
17 2 1 9∶ 00 12∶ 10
18 2 6 9∶ 05 10∶ 30
19 1 5 9∶ 05 10∶ 30
20 2 4 9∶ 10 10∶ 15
i h g T e
i T d
i
21 3 7 9∶ 15 10∶ 25
22 2 8 9∶ 15 10∶ 25
23 2 3 9∶ 20 10∶ 30
24 3 5 9∶ 20 10∶ 35
25 2 6 9∶ 25 10∶ 40
26 1 6 9∶ 25 10∶ 45
27 1 8 9∶ 25 10∶ 40
28 2 3 9∶ 30 12∶ 40
29 2 7 9∶ 30 10∶ 50
30 2 5 9∶ 35 10∶ 35
31 2 1 9∶ 35 11∶ 00
32 3 5 9∶ 40 10∶ 50
33 2 1 9∶ 40 10∶ 55
34 1 4 9∶ 45 11∶ 05
35 2 8 9∶ 45 11∶ 10
36 2 3 9∶ 50 11∶ 00
37 2 2 9∶ 50 13∶ 00
38 2 7 9∶ 55 10∶ 50
39 2 4 9∶ 55 11∶ 05
40 3 8 10∶ 00 11∶ 20
16 86． 根表 2 勤服务调度方案具体勤
服务作业时间计划图 2 示．
表 2 勤服务调度方案
Tab 2 Scheduling schemes for ground service
k 航班服务序列
tk
min
s g
min
tw
min
1 2581318263331393435 182 6 28 3 1 9
2 361115192532293836 172 5 21 0 1 9
3 171216213024272817 191 0 23 6 5 0
4 4910142022234037 170 0 20 8 2 2
图 2 勤服务作业时间计划
Fig 2 Working time plan for ground service
表 2 图 2 出保障航班延误
情况少需 4 辆特种车辆航班转移等
效服务时间率较航班工作效率较高
特种车辆间服务负荷相均衡．
3 3 结果较
机场勤服务调度问题作 VＲPTW 问题
种延伸难获精确解算法效性
文采 VＲPTW 常启发式算法遗传算法
进行较．
机场港航班进行勤服务调度采
启发式算法先先服务( first come first service
FCFS) 算法相数情况系统运行获
勤服务调度方案表 3 示目标函数值
Z1 5Z2 18 92 Z3 8． 03． 根表 3 勤服
务调度方案先先服务勤服务作业具体时间
安排图 3 示．
表 3 勤服务调度方案(FCFS)
Tab 3 Scheduling schemes for ground service(FCFS)
k 航班服务序列
tk
min
s g
min
tw
min
1 17132025283537 155 5 18 7 10 0
2 26111419243036 150 4 21 6 6 4
3 3812172126313340 144 6 17 0 9 0
4 49151822273239 151 0 20 3 3 7
5 5101623293438 148 7 22 1 13 0
图 3 勤服务作业时间计划(FCFS)
Fig 3 Working time plan for ground service (FCFS)
VＲPTW 研究中常采遗传算法
相数条件保障航班延误时特种
车辆数少采逐次增加车辆数方法
断调整参数次运行系统种群规模参数
500交叉概率 0 65变异概率 0 15终
止代数 2 000 时获勤服务调度方案表 4
示目标函数值 Z1 5Z2 18 25 Z3
33 14． 根表 4 勤服务调度方案采遗传算
法获勤服务作业时间计划图 4 示．
文提算法中特种车辆服务作业时间
安排紧密空闲时隙较． 三种算法勤服务
作业特种车辆数目分455目标Z1 优
866 沈 阳 工 业 学 学 报 第 39 卷表 4 勤服务调度方案(GA)
Tab 4 Scheduling schemes for ground service (GA)
k 航班服务序列
tk
min
s g
min
tw
min
1 36102132336831 151 4 16 4 0
2 1118165322437 126 3 24 8 1 5
3 415172528193335 170 2 22 2 18 0
4 1222729303438 141 3 25 3 20 0
5 71492621391220 157 1 30 9 44 0
图 4 勤服务作业时间计划(GA)
Fig 4 Working time plan for ground service (GA)
势明 显 效服务时间率分 13 92
18 92 18 25 目标 Z2 优势较明显外
三种算法效服务时间总分 104 7
141 8 203 1 min时间值优势较明
显说明服务作业效率较优势． 特种车辆
服务作业时间方差分 16 868 03 33 14
目标 Z3 服务作业均衡方面居中先先服务
算法服务均衡性稍差．
文提出阶段启发式算法计算机
运行时间基 1 ～2 s 间运行调度方
案较合理效减少勤服务车数减少
服务转移等时间降低效服务时间
率量特种服务车辆服务作业负荷均衡．
4 结
文机场港航班频次逐年升环境
考虑满足动态港服务时间窗约束航班服
务请求保障航班会勤服务发生离港延
误情况提高勤服务效率量优化勤服务
作业安排． 根服务时间窗约束条件建立
目标优化模型考虑勤服务作业少
特种车辆问题航班间服务转移等
服务时间问题特种车辆间服务负荷均衡问
题． 根模型特点两阶段启发式算法基础
提出种新阶段启发式算法． 研究结果
表明提出模型算法够快速反应较
机场提供勤服务调度方案提高特种车辆
服务效率减少服务车效服务时间
保障航班时离港． 外根调度结果机场
配置维护特种车辆理方面具定
参考意义．
参考文献(Ｒeferences)
［1］ 丁建立王新茹徐涛． 航班延误恢复调度混合粒
子群算法 ［J］． 交通运输工程学报20088( 2) 90 －
95．
( DING JianliWANG XinruXU Tao． Hybrid parti
cle swarm optimization arithmetic for recovery sche
duling of flight delays ［J］． Journal of Traffic and
Transportation Engineering20088( 2) 90 － 95． )
［2］ Berrittella MFranca L LZito P． An analytic hierarchy
process for ranking operating costs of low cost and full
service airlines ［J］． Journal of Air Transport Manage
ment200915( 5) 249 － 255．
［3］ Lp W HWang DCho V． Aircraft ground service
scheduling problems and their genetic algorithm with
hybrid assignment and sequence encoding scheme［J］．
IEEE Systems Journal20137( 4) 649 － 657．
［4］ Ｒavizza SAtkin J A DBurke E K． A more realistic
approach for airport ground movement optimisation
with stand holding ［J］． Journal of Scheduling201417
( 5) 507 － 520．
［5］ Cattaruzza DAbsi NFeillet Det al． An iterated local
search for the multi commodity multi trip vehicle rou
ting problem with time windows ［J］． Computers ＆
Operations Ｒesearch201451( 3) 257 － 267．
［6］ Michallet JPrins CAmodeo Let al． Multistart ite
ated local search for the periodic vehicle routing prob
lem with time windows and time spread constraints on
services ［J］． Computers ＆ Operations Ｒesearch2014
41 196 － 207．
［7］ Jin JCrainic T GLkketangen A． A cooperative
parallel metaheuristic for the capacitated vehicle routing
［J］． Computers ＆ Operations Ｒesearch201444 33 －
41．
［8］ 刘艳秋曹歌张颖等． 基分组策略补货配送问
题优化模型 ［J］． 沈阳工业学学报201739( 2)
165 － 169．
( LIU YanqiuCAO GeZHANG Yinget al． Optimi
zation model for replenishment and distribution prob
lems based on grouping strategy ［J］． Journal of Shen
yang University of Technology201739 ( 2) 165 －
169． )
［9］ 苟晶晶． 机场规划需勤保障车辆低数量预测
［J］． 中国民航飞行学院学报201527( 2) 50 － 53．
( GOU Jingjing． Prediction of the minimum require
ment of ground vehicles for airport planning ［J］．
Journal of Civil Aviation Flight University of China
201527( 2) 50 － 53． )
( 责编辑 钟 媛 英文审校 尹淑英)
966第 6 期 唐 非等 阶段启发式算法求解机场勤服务优化问题
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
2 0 1 7 年 1 1 月
沈 阳 工 业 学 学 报
Journal of Shenyang University of Technology
Vo l 39 No 6
Nov 2 0 1 7
收稿日期 2017 － 03 － 06．
基金项目 国家然科学基金面项目( 71571037) ．
作者简介 唐 非( 1975 － )女辽宁北镇讲师博士生事系统建模系统优化分析等方面研究．
* 文已 2017 － 10 － 25 21 ∶ 13 中国知网优先数字出版． 网络出版址 http ∥www． cnki． netkcmsdetail21． 1189． T．
20171025． 2113． 072． html
doi 10． 7688 j． issn． 1000 － 1646． 2017． 06． 12
阶段启发式算法求解机场勤服务优化问题*
唐 非12 刘树安1 董昕禹3
( 1 东北学 信息科学工程学院沈阳 110819 2 沈阳工业学 软件学院沈阳 110023 3 纽约州立学石溪分校 计算机系
美国 石溪 11790 － 2424)
摘 针保障航班离港延误勤服务调度优化问题建立特种车辆数化效服
务时间率化特种车辆服务时间方差化目标模型提出种新阶段启发式
算法． 根航班服务时间窗特种车辆航班间服务转移特点该算法够机场航班合理分
配特种车辆优化航班服务序列． 通仿真实例验证模型算法正确性结果表明提出
阶段启发式算法提高特种车辆服务效率减少车数量效服务时间达特种车
辆服务负荷均衡．
关 键 词 延误 特种车辆 效服务时间 时间方差 服务时间窗 阶段 松弛时间 负荷均衡
中图分类号 TP 18 文献标志码 A 文章编号 1000 － 1646( 2017) 06 － 0664 － 06
Multiphase heuristic algorithm for solving airport
ground service optimization problem
TANG Fei12 LIU Shuan1 DONG Xinyu3
( 1． School of Information Science ＆ EngineeringNortheastern UniversityShenyang 110819China 2． School of Software
Shenyang University of TechnologyShenyang 110023China 3． Computer Science DepartmentStony Brook University
Stony Brook 117902424USA)
Abstract Aiming at the ground service scheduling optimization problem without the departure delay in
airporta multiobjective model which could minimize the quantity of special vehiclesthe ratio of invalid
service time and the service time variance for special vehicles was establishedand a multiphase heuristic
algorithm was proposed． According to the features of airline service time window and the mobility of special
vehicles service between flightsthe allocation of special vehicles for the airpaort flights could be arranged
with the proposed algorithmand the flight service sequence could be optimized． Through the simulation
examplesthe correctness of both model and algorithm was proved． The results show that the proposed
multiphase heuristic algorithm improves the service efficiency of special vehiclesreduces the quantity of
used vehicles and the time of invalid serviceand achieves the workload balance of special vehicles．
Key words delay special vehicle invalid service time time variance service time window multiphase
slack time workload balance
根民航局统计 2015 年国境民
机场 210 中 26 机场客年吞吐量超
1 000 万 次16 机 场 年 起 降 架 次 超
20 万导致机场旅客数量航班港频次快速
增长面运行效率间矛盾越发明显． 航班
延误社会济效益存着显性隐性影响恢复延误需通勤保障作业停机位分
配滑行道路径选择等提高服务效率［1］． 中
勤服务作业作业项目环境影响较复杂重
研究课题包括单航班服务优化航班
单服务优化航班服务优化等问题． 问
题勤服务进行合理优化调度降低航
班延误带损失［2 － 4］． 勤服务组优化调度问
题作时间窗车辆路径问题( vehicle
routing problem with time windowsVＲPTW)
种延伸． VＲPTW 问题 NP 难问题采迭代
搜索算法邻域搜索算法元启发式搜索算法等
非精确算法［5 － 8］．
VＲPTW 相勤服务优化问题中特种
车辆航班间服务转移时间相 VＲPTW 路
径代价达航班停机位需根航班
需求继续进行服务保障服务程重点．
机场勤车辆调度研究中文献［9］勤服
务车辆低数量目标采禁忌搜索算法进行
求解通拖车服务调度结果出存定
调节时间余量． 类似勤服务优化问题文
献通求解方法分析结合
VＲPTW 问题求解方法知勤服务车辆调
度问题难求精确优解． 保障航班
延误离港文满足航班港服务时间窗约束
建立服务特种车辆数化效服务时
间率化特种车辆服务时间方差化
目标模型提出种新阶段启发式算
法问题进行求解．
1 目标模型
1 1 问题描述
时段 N 架航班进入指定停机位航班
港时间航班服务需求等信息均知． 机场
定数量资源保障航班港服务需求清
洁车行李车加油车食品车等通特种车辆
服务作业航班满足需求满足预计离港时间
约束．
1 2 变量假设
文做出假设
1) 航班需求量服务时间需
辆特种车辆完成
2) 特种车辆时刻航班提供
服务旦开始服务中断．
模型建立程中涉变量包括 航班序号
iN 港航班集合N { 12…i…n} 航
班港服务时间窗［T e
i T d
i ］T e
i 航班 i 允许服务
时间T d
i 航班 i 离港时间 航班服务时间 Pi
航班停机位置获取函数 g( i)特种车辆
航班 ij 间转移时间 s ij 表 示
s g( i)g( j) 特种车辆 序 号 kM 特种车辆集合
M { 12…k…m} 特种车辆 k 服务开始时
间 ts
k 特种车辆 k 服务结束时间 te
k 特种车辆 k
服务时间 tk 特种车辆总服务时间 t．
模型建立程中涉决策变量包括 特
种车辆 k 航班 i 提供服务开始时间 ts
ik 特种
车辆 k 航班 i 提供服务结束时间 te
ik 航班 i
服务请求否分配特种车辆 k 服务序列 l
位置 xkl
xkl i ( i∈N)
0 (
{ )
中k∈Ml∈Nk ． 特种车辆 k 航班服务集合
航班服务序列编号集合分表示 Nk { xk1
xk2 …xkl …xnk
} L k { 12…l…nk }
满足
∑
m
k 1
nk n ( 1)
1 3 数学模型
机场航班起降频次逐年升提供勤
保障特种车辆存设备老化维修等状况
保障会勤服务作业导致航班发生延误情
况确定勤服务少车数量尤重．
外提高服务效率减少特种车辆效服务作业时
间量特种车辆服务作业均衡勤
服务调度关键指标． 文中效服务时间指特
种车辆航班间服务转移等服务时间相
反航班提供服务作业时间效作业时间．
文勤服务特种车辆数化第目
标效服务时间率化第二目标特
种车辆服务时间方差化第三目标建立目
标函数模型表达式分
Z1 min m ( 2)
Z2 min
t－∑
n
i 1
Pi
t ( 3)
Z3 min ( tk － 珋tk )槡 2 ( 4)
s． t
∑
m
k 1
∑
nk
l 1
sign( xkl ) n ( 5)
xkl ≠xk＇l＇ ( kk＇∈Mll＇∈L k )( 6)
T d
xkl － Pxkl ≥ts
xklk ≥T e
xkl
( k∈Ml∈L k )( 7)
ts
xklk － s g( xkl － 1)g( xkl) ≥te
xkl － 1k ( k∈Ml∈L k )( 8)
566第 6 期 唐 非等 阶段启发式算法求解机场勤服务优化问题te
xklk ( ts
xklk + Pxkl
)·sign( xkl)( k∈Ml∈Lk)( 9)
te
k max
i
{ te
xkll·sign( xkl )}( k∈Ml∈L k )( 10)
ts
k min
i
{ ts
xkll·sign( xkl )}( k∈Ml∈L k )( 11)
tk te
k － ts
k ( k∈M)( 12)
t ∑
m
k 1
tk ( k∈M)( 13)
珋tk t
m ( k∈M)( 14)
xkl i ( i∈Nk∈Ml∈L k )( 15)
模型中式( 2) ～ ( 4) 表示目标函数 式( 5) ( 6)
表示航班均服务航班需
辆特种车辆服务 式( 7) ( 8) 表示特种车辆 k
航班提供服务时间约束 式( 9) ～ ( 12) 表示特
种车辆 k 航班提供服务结束时间航班
早服务时间晚结束服务时间服务总时
间 式( 13) ( 14) 表示车辆服务总时间
均服务时间 式( 15) 表示航班 i 特种车辆 k
序列 l 位置．
模型中涉 sign(·) 表示
sign( y) 1 ( y ＞ 0)
0 ( y≤0
{ ) ( 16)
2 阶段启发式算法设计
文模型目标非线性模型航班延
误情况难获特种车辆服务车辆数效服
务时间服务作业均衡优精确解． 根
特点基两阶段启发式算法思想设计新
阶段启发式算法．
2 1 算法基思想
文设计算法基思想特种服务车辆
应量满负荷进行服务作业减少服务车辆数．
基础减少效服务时间量车辆
服务作业均衡． 阶段启发式算法包括构造
特种车辆航班服务序列初始分配阶段优化服务
系列阶段均衡特种车辆间服务作业阶段．
算法第阶段采局部邻域搜索方法实现
航班初始分配． 航班集合满足航班离港需求
前提航班化数量分配特种车辆
航班提供服务作业． 航班集合中迟
离港航班初始化特种车辆服务序列初始
航班基础采局部邻域搜索方法松弛时
间优先规次满足时间约束航班进行
初始分配直航班集合中没满足条件航班．
松弛时间 Δti 指特种车辆服务序列相邻两
航班间等服务时间． 根式( 8) ( 15)Δti
计算表达式
Δtxklk ts
xklk － s g( xkl － 1)g( xkl) － te
xkl － 1k
( k∈Ml∈L k )( 17)
果存等服务分配航班特种车辆 k
局部邻域搜索范围符合式( 7) ( 8) 约束航班．
算法第二阶段初始分配基础采
循环调整服务时间窗方法减少效服
务时间采插入法 Δtxklk ＞ 0 中松弛
时间优先规符合时间约束航班插入特
种车辆服务序列相应位置．
通调整服务开始时间循环调节服务时间窗
区间调整服务开始时间计算表达式
ts
xklk min{ T e
xkl
ts
xklk － Δtxkl
}
( k∈Ml∈L k )( 18)
算法第三阶段前两阶段基础松弛
时间优先规特种车辆未进行服务剩余
服务时间重新调整航班分配量特种车辆
服务作业均衡．
2 2 阶段启发式算法实现
根算法设计思想针航班港服务时
间窗［T e
i T d
i］约束勤服务作业问题设计
阶段启发式算法． 算法流程图图 1 示
实现程
1) 输入港航班集合 N 航班相关信
息包括航班服务时间窗［T e
i T d
i ］停机位置 g
航班服务时间 Pi 初始化航班 te
i T d
i ．
2) 特种车辆服务序列进行初始分配．
① 果 N 非空 N 中迟离港意
航班初始分配特种车辆 k 服务序列末尾位置
N 中删该航班转步骤② 否转步骤 4) ．
② 根式( 7) ( 8) 采局部邻域搜索方法
松弛时间优先规 N 中次符合条
件意航班分配特种车辆 k N 中删该
航班计算航班 ts
xklk te
xklk Δtxklk 直没
符合条件航班转步骤 3) ．
3) 航班序列进行优化．
① 航班服务序列中序判断否存未标
记航班 Δtxklk ＞0 航班果根式( 18)
重新计算 ts
xklk te
xklk Δtxklk ts
xklk T e
xkl
航
班标记调整服务时间窗结束转步骤②否转
步骤③．
② 判断服务序列否结束果转步骤①．
③ 航班集合 N 中搜索满足时间约束插
入特种车辆 k 服务序列航班果松弛时
间原插入相应位置调整特种车辆服
务序列 N 中删该航班否转步骤 2) ．
666 沈 阳 工 业 学 学 报 第 39 卷图 1 算法流程图
Fig 1 Flow chart of algorithm
4) 均衡服务作业． 提前结束航班服务序
列作业特种车辆搜索车辆服务序列中
否满足时间约束未开始服务航班果
松弛时间原车辆间调整服务序列否
转步骤 5) ．
5) 输出需目标函数值 Z1 Z2 Z3 ．
3 仿真结果分析
算法运行环境 ThinkPad PC i74710MQ
CPU 2 50 GHz．
3 1 算例数
选取首国际机场某日 8∶00 10∶00 港
部分航班例算法进行验证． 航班序号 i航班类
型 h停机位 g 服务时间窗［T e
i T d
i］等 40 架航班
服务数表 1 示． 特种车辆 8 停机位转
移时间矩阵
S
0 0 2 0 1 5 2 0 3 8 5 0 5 3 6 0
2 0 0 0 1 6 2 8 3 3 3 5 4 2 5 5
1 5 1 6 0 0 3 3 4 3 4 8 4 6 5 9
2 0 2 8 3 3 0 0 1 2 5 4 5 7 6 0
3 8 3 3 4 3 1 2 0 0 5 8 6 2 6 1
5 0 3 5 4 8 5 4 5 8 0 0 2 0 1 9
5 3 4 2 4 6 5 7 6 2 2 0 0 0 2 2
6 0 5 5 5 9 6 0 6 1 1 9 2 2 0 0
机型 h 服务时间间关系矩阵
P 1 2 3[]20 15 10
3 2 仿真结果
根航班信息表 1转移时间矩阵 S 服务
时间矩阵 P 数运行系统勤服务调度
方案表 2 示中tk 特种车辆 k 服务时
间s g 航班停机位转移时间tw 等服务
时间． 目标函数值Z1 4Z2 13 92 Z3
766第 6 期 唐 非等 阶段启发式算法求解机场勤服务优化问题表 1 航班数
Tab 1 Data of flights
i h g T e
i T d
i
1 1 5 8∶ 00 9∶ 10
2 2 3 8∶ 00 9∶ 20
3 2 1 8∶ 05 9∶ 20
4 1 4 8∶ 05 9∶ 05
5 3 8 8∶ 10 9∶ 30
6 2 1 8∶ 20 9∶ 35
7 1 3 8∶ 25 9∶ 40
8 3 4 8∶ 30 9∶ 45
9 1 5 8∶ 30 9∶ 40
10 2 4 8∶ 40 9∶ 45
11 1 2 8∶ 40 9∶ 45
12 2 2 8∶ 45 10∶ 00
13 1 4 8∶ 50 10∶ 05
14 3 2 8∶ 50 10∶ 00
15 2 1 8∶ 55 10∶ 05
16 1 5 8∶ 55 10∶ 20
17 2 1 9∶ 00 12∶ 10
18 2 6 9∶ 05 10∶ 30
19 1 5 9∶ 05 10∶ 30
20 2 4 9∶ 10 10∶ 15
i h g T e
i T d
i
21 3 7 9∶ 15 10∶ 25
22 2 8 9∶ 15 10∶ 25
23 2 3 9∶ 20 10∶ 30
24 3 5 9∶ 20 10∶ 35
25 2 6 9∶ 25 10∶ 40
26 1 6 9∶ 25 10∶ 45
27 1 8 9∶ 25 10∶ 40
28 2 3 9∶ 30 12∶ 40
29 2 7 9∶ 30 10∶ 50
30 2 5 9∶ 35 10∶ 35
31 2 1 9∶ 35 11∶ 00
32 3 5 9∶ 40 10∶ 50
33 2 1 9∶ 40 10∶ 55
34 1 4 9∶ 45 11∶ 05
35 2 8 9∶ 45 11∶ 10
36 2 3 9∶ 50 11∶ 00
37 2 2 9∶ 50 13∶ 00
38 2 7 9∶ 55 10∶ 50
39 2 4 9∶ 55 11∶ 05
40 3 8 10∶ 00 11∶ 20
16 86． 根表 2 勤服务调度方案具体勤
服务作业时间计划图 2 示．
表 2 勤服务调度方案
Tab 2 Scheduling schemes for ground service
k 航班服务序列
tk
min
s g
min
tw
min
1 2581318263331393435 182 6 28 3 1 9
2 361115192532293836 172 5 21 0 1 9
3 171216213024272817 191 0 23 6 5 0
4 4910142022234037 170 0 20 8 2 2
图 2 勤服务作业时间计划
Fig 2 Working time plan for ground service
表 2 图 2 出保障航班延误
情况少需 4 辆特种车辆航班转移等
效服务时间率较航班工作效率较高
特种车辆间服务负荷相均衡．
3 3 结果较
机场勤服务调度问题作 VＲPTW 问题
种延伸难获精确解算法效性
文采 VＲPTW 常启发式算法遗传算法
进行较．
机场港航班进行勤服务调度采
启发式算法先先服务( first come first service
FCFS) 算法相数情况系统运行获
勤服务调度方案表 3 示目标函数值
Z1 5Z2 18 92 Z3 8． 03． 根表 3 勤服
务调度方案先先服务勤服务作业具体时间
安排图 3 示．
表 3 勤服务调度方案(FCFS)
Tab 3 Scheduling schemes for ground service(FCFS)
k 航班服务序列
tk
min
s g
min
tw
min
1 17132025283537 155 5 18 7 10 0
2 26111419243036 150 4 21 6 6 4
3 3812172126313340 144 6 17 0 9 0
4 49151822273239 151 0 20 3 3 7
5 5101623293438 148 7 22 1 13 0
图 3 勤服务作业时间计划(FCFS)
Fig 3 Working time plan for ground service (FCFS)
VＲPTW 研究中常采遗传算法
相数条件保障航班延误时特种
车辆数少采逐次增加车辆数方法
断调整参数次运行系统种群规模参数
500交叉概率 0 65变异概率 0 15终
止代数 2 000 时获勤服务调度方案表 4
示目标函数值 Z1 5Z2 18 25 Z3
33 14． 根表 4 勤服务调度方案采遗传算
法获勤服务作业时间计划图 4 示．
文提算法中特种车辆服务作业时间
安排紧密空闲时隙较． 三种算法勤服务
作业特种车辆数目分455目标Z1 优
866 沈 阳 工 业 学 学 报 第 39 卷表 4 勤服务调度方案(GA)
Tab 4 Scheduling schemes for ground service (GA)
k 航班服务序列
tk
min
s g
min
tw
min
1 36102132336831 151 4 16 4 0
2 1118165322437 126 3 24 8 1 5
3 415172528193335 170 2 22 2 18 0
4 1222729303438 141 3 25 3 20 0
5 71492621391220 157 1 30 9 44 0
图 4 勤服务作业时间计划(GA)
Fig 4 Working time plan for ground service (GA)
势明 显 效服务时间率分 13 92
18 92 18 25 目标 Z2 优势较明显外
三种算法效服务时间总分 104 7
141 8 203 1 min时间值优势较明
显说明服务作业效率较优势． 特种车辆
服务作业时间方差分 16 868 03 33 14
目标 Z3 服务作业均衡方面居中先先服务
算法服务均衡性稍差．
文提出阶段启发式算法计算机
运行时间基 1 ～2 s 间运行调度方
案较合理效减少勤服务车数减少
服务转移等时间降低效服务时间
率量特种服务车辆服务作业负荷均衡．
4 结
文机场港航班频次逐年升环境
考虑满足动态港服务时间窗约束航班服
务请求保障航班会勤服务发生离港延
误情况提高勤服务效率量优化勤服务
作业安排． 根服务时间窗约束条件建立
目标优化模型考虑勤服务作业少
特种车辆问题航班间服务转移等
服务时间问题特种车辆间服务负荷均衡问
题． 根模型特点两阶段启发式算法基础
提出种新阶段启发式算法． 研究结果
表明提出模型算法够快速反应较
机场提供勤服务调度方案提高特种车辆
服务效率减少服务车效服务时间
保障航班时离港． 外根调度结果机场
配置维护特种车辆理方面具定
参考意义．
参考文献(Ｒeferences)
［1］ 丁建立王新茹徐涛． 航班延误恢复调度混合粒
子群算法 ［J］． 交通运输工程学报20088( 2) 90 －
95．
( DING JianliWANG XinruXU Tao． Hybrid parti
cle swarm optimization arithmetic for recovery sche
duling of flight delays ［J］． Journal of Traffic and
Transportation Engineering20088( 2) 90 － 95． )
［2］ Berrittella MFranca L LZito P． An analytic hierarchy
process for ranking operating costs of low cost and full
service airlines ［J］． Journal of Air Transport Manage
ment200915( 5) 249 － 255．
［3］ Lp W HWang DCho V． Aircraft ground service
scheduling problems and their genetic algorithm with
hybrid assignment and sequence encoding scheme［J］．
IEEE Systems Journal20137( 4) 649 － 657．
［4］ Ｒavizza SAtkin J A DBurke E K． A more realistic
approach for airport ground movement optimisation
with stand holding ［J］． Journal of Scheduling201417
( 5) 507 － 520．
［5］ Cattaruzza DAbsi NFeillet Det al． An iterated local
search for the multi commodity multi trip vehicle rou
ting problem with time windows ［J］． Computers ＆
Operations Ｒesearch201451( 3) 257 － 267．
［6］ Michallet JPrins CAmodeo Let al． Multistart ite
ated local search for the periodic vehicle routing prob
lem with time windows and time spread constraints on
services ［J］． Computers ＆ Operations Ｒesearch2014
41 196 － 207．
［7］ Jin JCrainic T GLkketangen A． A cooperative
parallel metaheuristic for the capacitated vehicle routing
［J］． Computers ＆ Operations Ｒesearch201444 33 －
41．
［8］ 刘艳秋曹歌张颖等． 基分组策略补货配送问
题优化模型 ［J］． 沈阳工业学学报201739( 2)
165 － 169．
( LIU YanqiuCAO GeZHANG Yinget al． Optimi
zation model for replenishment and distribution prob
lems based on grouping strategy ［J］． Journal of Shen
yang University of Technology201739 ( 2) 165 －
169． )
［9］ 苟晶晶． 机场规划需勤保障车辆低数量预测
［J］． 中国民航飞行学院学报201527( 2) 50 － 53．
( GOU Jingjing． Prediction of the minimum require
ment of ground vehicles for airport planning ［J］．
Journal of Civil Aviation Flight University of China
201527( 2) 50 － 53． )
( 责编辑 钟 媛 英文审校 尹淑英)
966第 6 期 唐 非等 阶段启发式算法求解机场勤服务优化问题
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档