2024年3月16日发(作者：位寒梦)
2021
年
1
月
计算机工程与设计
COMPUTER
ENGINEERING
AND
DESIGN
Jan.
2021
Vol.
42
No.
1
第
42
卷
第
1
期
基于
HTCPN
的
牵引车
动态优化调度
苏志刚
，赵松泽
，
郝敬堂
（
中国民航大学中
欧
航空工程
师
学院
，
天津
300300
）
摘
要
：
针对机场牵引车动态调度问题
，
基于层次赋时着色
Petri
网
（hierarchical
timed
colored
Petri
net
,
HTCPN
）
搭建
牵引车动态调度仿真系统
。
在充分考虑实际运行过程中各个步骤的随机性后
，
根据航空器实时发送的推出申请完成牵引车
的动态分配
。
在保障航班延误最少的基础上依次实现不同车辆间工作负荷均衡度最高和车辆行驶总距离最短的优化目标
，
通过蒙
特卡洛实验验证了优
化的有
效性
。
利用
该系统
完
成对
目标
机
场牵引
车
保障能力
的评估
，
预测在不同
航
班密度下必要
的牵引
车
配置数量
。
关键词
：
牵引车动态调度
；
层次赋时着色
Petn
网
；
多目标优化
；
保障能力评估
；
蒙特卡洛实验
中图法分类号
：
TP15
文献标识号
：
A
文章编号
：
1000-7024
（
2021
）
01-0294-08
doi
：
10.
16208/j.
issnl
000-7024.
2021.
01.
042
Dynamic
optimal
scheduling
of
tractors
based
on
HTCPN
SU
Zhi-gang
,
ZHAO
Song-ze
,
HAO
Jing-tang
(
Sino-European
Institute
of
Aviation
Engineering
&
Civil
Aviation
University
of
China,
Tianjin
300300,
China)
Abstract
：
Aiming
at
the
dynamic
scheduling
problem
of
airport
tractor,
a
dynamic
scheduling
simulation
system
of
tractors
was
designed
based
on
hierarchical
timed
colored
Petri
net
(
HTCPN)
.
After
fully
considering
the
randomness
of
each
step
in
the
actual
operation
process,
the
dynamic
allocation
of
the
tractors
was
completed
according
to
the
pushback
application
sent
by
the
aircraft
in
real
time.
On
the
basis
of
ensuring
the
minimum
of
the
flight
delay,
the
optimization
goal
of
the
highest
load
balance
amongdi
f
erenttractorsandtKesKortesttotaldistancetraveledbytractorswererealizedinsequence6TKee
f
ectivenessoftKe
optimization
was
verified
by
Monte
Carlo
experiment.
The
system
was
used
to
evaluate
the
support
capacity
of
tractors
at
the
tar
geNairporN
andNopredicNNhenecessarynumberofNracNorsaNdi
f
erenNflighNdensiies6
Key
words
：
dynamic
scheduling
of
tractors
；
hierarchical
timed
colored
Petri
net
；
multi-objective
optimization
；
support
capability
assessment
；
Monte
Carlo
experiment
/
引言
快速增长的航空运输量极大增加了机场场面的运行压
度问题进行优化
。
即假设在航班计划
、
航班需求时间窗以
及作业时间等信息已知并始终不变的前提下
，
根据航班的
需求规划车辆的行驶路径
（
实际情况下影响航班运行的随
机因素较多
。
当随机因素对原有航班计划产生影响时
，
车
力
[1]
o
目前我国大部分机
场
的工作人
员
是通过目
视
、
语音
对讲等方式对符合条件的车辆进行调度也，
落
后的信息获
辆资源需要重新分配
。
虽然启发式算法可以得到可行解
，
但其不能很好地对调度过程中的随机因素实时响应
。
取方式及决策过程导致航班高峰时段调度效率低下
，
进而
影响航班的准点率
。
地勤保障车辆调度问题持续受到国内
系统仿真方法利用离散仿真模型模拟调度流程
，
十分
适用于机场车辆调度这种存在诸多不确定因素的离散动态
外学者的广泛关注
，
研究方法主要集中在运筹学方法
37
*和
系统
仿真方法
82
两个方面
。
运筹学方法是将车辆调度问题简化为多目标优化模型
,
再利用启发式算法进行求解
（启发式算法主要是对静态调
收稿日期
：
2019-09-12
；
修订日期
：
2020-05-25
随机过程的分析
。
采用仿真方法可以很好地模拟调度过程
中的突发事件
，
设计出针对不同随机问题的解决方案
（
芝
加哥机场和日本民航局采用
TAAM
[11]
（
total
airspace
&
基金项目
：
中央高校基本科研业务费中国民
航
大学专项基金项目
（
3122017111
）
作者简介
：
苏志刚
（
972-
）
,
男
，
黑龙江尚
志
人
，
博士
，
教授
，研究方向为信号与信
息处理
、
监
视与导航；
赵松泽
（
1994
-
）
,
男
，
天津
人
，
硕士研究生
，
研究方向为机场保
障车辆调度和航空]
场面
滑行的仿真
；
郝敬堂
（
1989
-
）
,
男
，
河南
鹤壁人
，
硕士
，
实验师
，
研究方向
为空管监
视
数
据
处理
、
室内
导航等
（
:
************.com
第
42
卷第
1
期
苏志刚
，
赵松泽
，
郝敬堂
：
基于
HTCPN
的牵引车动态优化调度
•
295
•
airport
modeler
)
对空域和飞行区进行仿真研究
，
分析机场
分配该牵引车从当前位置驶向指定机位进行服务
。
若所有
的运行方式和空域构型
。
丹佛机场利用
SIMMOD
)
2
*
分析现
有飞行区的运行状况以及新的改造措施对延误的影响
。
上
牵引车当前时刻均处于工作状态
，调度人员会根据反馈信
息指派最先完成当前任务的牵引车执行该任务
。
现行调度
规则存在以下问题
。
(1)
述仿真软件虽然功能强大
，
但价格昂贵
，
且仿真的主要对
象是航空器
，
仅有少部分功能涉及到车辆调度过程
。
每辆牵引车航班任务分配不均衡
；
本文运用层次赋时着色
Petri
网
(
hierarchical
timed
colored Petn
net,
HTCPN)
对牵引车调度过程进行仿真
(
(2)
为航空器分配牵引车时没有考虑候选车辆与服务
需求点间的距离
。
为解决当前调度模式下存在的问题
，
需要依次从车辆
利用层次
Petri
网
(hierarchical
Petri
net,
HPN)
对系统进
行模块划分
，
增加模型的可视性
；
利用着色
Petn
网
到达时间
、
车辆工作负荷均衡度和车辆行驶距离
3
个方面
(colored
Petn
net
,
CPN)
对不同资源进行标记区分
；
利用
赋时
Petri
网
(timed
Petn
net
，
TPN
)
模拟牵引车资源占用
和释放的实时情况
。
搭建动态调度仿真系统
，
根据航空器
发送的推出申请完成航空器与牵引车的动态匹配
。
提出调
度优化方案
，
实现不同车辆间工作负荷均衡度最高和车辆
行驶总距离最短的优化目标，通过仿真实验验证了优化的
有效性
。
最后完成对目标机场牵引车保障能力的评估
，
预
测在不同航班密度下的牵引车配置数量
。
1
牵引
车
调度数学模型
1.1
调度流程分析
针对牵引车调度特点
，
将调度流程简化为如下步骤:
首先按照假设的规则随机生成离港航班信息
，
系统根据每
架航空器的预计离港时刻非降序排列所有航班信息形成航
空器等待队列
，
每架航空器在其预计离港时刻前
Tm
分
钟发出推出申请
；
系统按照设定的动态优化调度目标逐一
为待服务航空器分配满足条件的牵引车前往服务
；
牵引车
在开始推出任务前判断与邻近机位是否存在推出冲突
，
如
存在冲突则在原地等待
；
待冲突解脱后牵引车将航空器推
出到指定位置
，并完成信息的记录与更新。
1.2
基
本假设
机场场面运行过程中包含诸多随机因素
，
在不影响牵
引车和航空器正常运行的前提下对模型做如下假设
：
(1)
单位时间内离港航空器数目服从参数为
人
的泊松
分布
)
314
*
;
(2)
正常情况下
，
每架航空器在其预计离港时刻前
T
Re
q
ues
t
=
15min
发出推出申请
；
(3)
牵引车推出航空器时与邻近机位发生推出冲突的
概率为
P
mic
，
若存在推出冲突
，
牵引车和航空器在原地等
待的时间满足均值为
T
oni
的指数分布
；
(4
)
牵引车推出航空器的作业时间服从高斯分布
N
(
“
,
/)
。
作业时间的均值
$
由被服务航空器的机型决定
。
标准
差
。
的取值与航空器机型无关
，
与推出时地服人员和飞行
员配合的
熟
练度有关
。
1.3
优化目标
在
有运
模
，
到推
请后，
按
照车
辆
序号顺序分配可用车
辆
。
如果存在可用车辆
，
立刻
进行优化
。
车
辆
到达时间
：
在实际运行中时间因素最为重要
，
要
求车
辆
延
到达的时
C
#
=
min$[
'g!
；
)
X
；
()
式中
：
；
表示第
&
架航空器因牵引车晚点造成的延误时间,
式
(
2)
是表示延误与否的符号函数
sign
；
)
=
1
-
;
>
0
(2)
0
，
;
&
=
0
车辆工作负荷均衡度
：
为保证牵引车的安全使用和驾
驶人员的合理分配
，
调度车
辆
时应尽量提高不同车辆间工
作负
的
衡
，
用车
辆
工作负
的
作
为表
衡
的目
函数
G=mm"
N
,-
N
j
⑶
式中
：
V
表示牵引车的集合
，
N
：
和
N
j
表示编号为分和
j
的牵
引车服务过的航班数量
。
车
辆
驶
：
车在不同
位
的
不
忽略
，
减少行驶距离可进一步保证牵引车的准时到达
，
同
时降低机场或航空公司的燃油成本
C
3
=
⑷
式中
：
N
表示编号为
，
的牵引车行驶过的总距离
。
2
HTCPN
动态调度仿真系统
2.1
模型描述
建模采用自顶向下的分解原则
。
首先确定调度流程的
整体功能模型图
，
然后再对顶层模型进一步细化
，
在子页
中实现子流程功能
，
形成分层模型
。
牵引车动态调度仿真
系统的层次赋时着色
Petn
网模型可简化为以下多元组
HTCPN
=
(S,SN,SA,PN,PT
)
(5)
HTCPN
中各参数的含义分别为
：
()
S
代表子页的有限集合
，
每个子页对应于调度过
程中一个关键的子流程
，
依次为航空器推出申请
、
航空器
牵引车实时匹配
、
航空器推出冲突
、
航空器推出过程
。
s
中
的任意子页
s
均是一个非层次的赋时着色
Petn
网
s
=
LPN
,
R
,
)
)
(6)
式中
：
K
是时间值的集合
，
称为时间戳
；
)
是
R
中的元素,
对应于调度过程的起始时刻
。
・
296
・
计算机工程与设计
2021
年
（
2
）
SN
是替代变迁
，
SN
J
T
&
T
表示变迁集合
，
采用
变迁代表
Petri
网
中的某一模块&使得网络在
到
&之后在对应的
变迁间的对应关系
。
更深
的
建模
。
（
3
）
SA
是页分配函数
，
SA
：
SN
6
S
,
表示子页和替代
（
4
）
PN
代表端口节点的集合
&
PN
J
?
表示库
所集合
。
（5
）
PT
是端口类型函数
，
是从
PN
定义到
｛
In,Out
,
In/Out,General
｝
的函数
。
式
（
6
）
中的参数
CPN
表示一个非层次的着色
Petri
网
，
可用如下
9
元组表示
CPN
*
（
P,TA,
X
JC5O
J
）
（
7
）
图
1
牵引车调度顶层模型
表
2
顶层模型中替代变迁及其对应子过程
替代变迁
Request
式中
：
P
表示库所集合
，
以椭圆形表示
，
可以表示动态调度
仿真系统各
的实时状态
；
T
表示变迁集合
，
以矩形表
子过程
航空器推出申请
航
器
车实时
示
，
代表
中
具体事件的发生
，
实现不同库所间的
信息传递
;
A
为有向弧集合&是联系库所
之间的流关
的
表达式&
。
系
；
/为颜色集的非空有限集合
；
J
为变量集合；
C
为颜色
Match
Conflict
集函数
，
定
所的数据类型
；
5
为
航空器推出冲突
航
器推
E
为有向弧表达式
，
守卫表达式和弧表达式共同定义了变
Pushback
迁的使能条件
；
/
为
型的
函数
，
定
所的
生个数和位置的
&
托肯
（
token
）
表示分配给库所的资源
，
在
Petri
网模
库所
Plane
存储系统随机生成的航班信息
，
库所
Tug
存储机场内初始时刻所有牵引车的信息
，
库所
Airport
对应
中
。
车和航空
器是模型中两种不同类型的
色
其
不同的
颜
于机坪不同位置点距离的录入
，
以上
3
个库所是模型中初
。
后
其输
所移
肯
，同时
信息的输入窗口
。
所有航空器会依次通过
4
最终回到
Finish
PlaneList
库所中
，
该库所的作用是记录每
架航空器被推岀后的最终状态
。
，
库所
Capacity
对航
向输
所增
肯
，
从而
模型状态的改变
。
航空器
车的
颜
色集
表
1
。
器
队
列起到容量
的作用
。
在库所
的
HTCPN
模型形成
的
表
1
航空器与牵引车颜色集
肯
共同作用下
，
馈
。
23
航空器推出申请
环反
颜色
集
（
航班号
、
停机位
、
机型、
预计离港时刻
、
匹配的
车编号
、
牵引车到达时刻
、
开始推出时刻
、
完成推出
时刻
、
牵引车提前
/
晚点到达时间
）
航空器
顶层模型中表示航空器推岀申请的替代变迁
（
R-
quest
）
后
到如图
2
所示的
模型
。
牵引车
（
牵引车编号、
当前状态
（
工作
/
空
闲
）
、已服务航班序
列
、
已服务航班数量
、
当前时刻位置
、
可为
航班
开始服务时刻
、
行驶总
）
系统首先通过
Timetable
变迁在一定规则下随机生成航
班数据
。
该
器所在
表达式中的
density
用于模拟服
位编号
，
时
松
分布的航班流
。
库所
Apron
中存储系统自动生成的离港航
航班号
、
停机位、
牵引车编号等初始属性的作用是对
托肯的活动
，
同时确保同
&
车到达时刻
、
牵引车已服务航
条件
。
一机位在
2
小时内不会被再次分配
。
生成的航班信息在
List
中以列表的形式存储
。
List
中的航班列表再通过
Sort
序列
、
车
位
属性
系统的运行实时更
&更新后的
2
2
顶层模型
成为后续运行中新的
成按预计离港时刻的非降序排列
，
在
Queue
中形成
航班的等待队列
。
最后通过
Request
变迁逐一发岀推岀申
请
。
通过
Capacity
库所可以使系统逐一地接收航空器
队
列
的推
请
，
而实
动态调度仿真系统的顶层模型如图
1
所示
。
替代变迁
用双框矩形表示
，
各
的
表
2
。
航
器
队
列的容量
。
所右下方的标识代表颜色集
，
根据容纳的资源类型
端点为
的弧为
抑
，
作用是设
生的优先
，
而
自
分为
4
类
：
航空器状态库所
（
Plnfor
）
、
航空器
队
列状态库
权
。
当库所
Plane
中存在托肯时
，
变迁
Sort
无法发生
，通
抑
使
队
在航
信息生成后
所
（
LPInfor
）
、牵引车集合状态库所
（
LCInfor
）
和约束类
所
（
LDistance
，
Cap
）
。
主控制仿真实验中的航空器数目
。
Request
输岀弧上的
第
42
卷第
1
期
苏志刚
，
赵松泽
，
郝敬堂
：
基于
HTCPN
的牵引车动态优化调度
・
297
・
Plane
In/Out
plane
PInfor
input
(plane);
output
(density,initT);
action(Exponential(r),
#6
plane);
lpplace
Timetable
lpplace
(
Apron
Out
plane@+applytime
PInfor
[plistof]]
In/Out
Capacity
0
Request
LPPlace
[plane]^plist
Hl
List
[plistoQ]
Cap
input
(plist);
output
(plane,applytime);
action(
plist,
#6(
plist
)-T-mtTimeQ);
Sort
SortPbyT
(plist)
(
-----------------
►(
Queue
LPInfor
plist
LPInfor
图
2
航空器推出申请模型
applytime
是航空器发岀推岀申请的时刻
，
作为每架航空器
状态
基于
婪算法是
带的时间戳
。
算法设计了航空器牵引车实时匹配算法
。贪
开始
24
航空
器牵引
车实
时
匹配
依次读取待服务航班
发出的推出申请
为基础追求
的推
&
针对航
器
队
列
如图
3
所示
。
请逐
成
车的分配
，
对动态
车实时
算法
车辆到达时间匹配
有一定的解决能力
，
航空器
系统在读取待服务航空器发岀的推岀申请后
，
依次以
车
辆
到达时间
、
车
辆
工作负
衡
及车辆行驶
仅有一辆牵弓
、
宇满足需求/
否
车辆工作负荷
均衡度匹配
为
判据
空闲状态的
条件的
车集合
。
首先实现车辆到达时间的匹配
，
筛选岀当前时刻处于
车集合
，
如若没有
车
辆
，
定完成
衡
是
服
反有一辆牵引
连满足需求―
，
否
务时
的
车
。
车
辆
工作负
辆
车服务过的航班数
非降序排列
辆
务航班数
的
车集合
。最后
驶总
车行驶总
成非降序排列
，
的
车
，
车辆行驶距离匹配
是
从而实现车辆行驶距离的匹配
。
若此时满足条件的牵引车
仍多于一辆
，
则按照车辆序号顺序随机指派一辆牵引车前
服务
。
是
，
否
基于上述算法建立了如图
4
所示的航空器牵引车实时
匹配模型
。
模型中从上至下的
3
个替代变迁分别对应于流程图中
按照牵引车编号在集合中
选取第一辆牵引车
安排该牵引车
前往相应的停机位
是
的车辆
到达时
驶
(
、
车
辆
工作
负
后的节
后的
衡
车
辆
所
表示航空器
的
状态和经
车集合状态
。
车集合
Tug
同时
结束
推岀申请后的航空器
绑定于
Arrival
Time
替代变迁，
目的是筛选岀满足时间要
求的
图
3
航空器牵引车实时匹配算法
车集合
。
经过第一步
后的
车集
航空
辆最少的牵引车集合
(
Airport
以邻接矩阵的格式存储目标
器同时绑定于
Load
Balance
替代变迁
，
筛选岀服务航班数
・
298
・
计算机工程与设计
2021
年
Load
Balance
图
4
航空器牵引车实时匹配模型
机场内不同位置点间的距离
，
通过
Distance
替代变迁搜索
辆
车
位
服务航空器
计算岀行
驶到目的点的时间
。
经过
3
条件的
服务
。
2.5
航空器推出冲突
后产生
'满
车
，
系统安排该
车
相应的
位进
在机场运行高峰时段
，
邻近停机位航班常会因离港时
而
突
。
当航空器侧向推岀时与同
位
推
推岀的航空器由于安全
而产生冲突
）
5
*
,
，
只有当前
图
6
航空器推
出过
程模型
生推岀冲突后的解决方案是后机在
滑行通过推岀安全点后，
后机才能
推岀&推
距离等属性随之更新
。
下一步再通过替代变迁
UpdatePlane
完成航空器信息的更新
，
代表航空器的托肯
已被推岀
航空器队列库所
（
Finish
PlaneList
）
，
记录航空器被服务后
突会导致牵引车使用时间的增加以及实际推岀时间的
延迟
，
推岀冲突的模型如图
5
所示
。
待服务航空器
步
的牵引车同时绑定于变
的
状态
，
的牵引车编号
、
车到达时刻
、
为
架发岀
迁
Ran
,
通过
Ran
在库所
Conflict
中产生随机数
ran
,
再根
据
Norma
和
Wait
上的守卫函数判断航空器推岀冲突事件
推岀时刻
、
完成推岀时
推
属性
。
推
务完成后容
量库所中的托肯也完成更新
，
服务
是否发生
。当
ran
>
P
时
，
变迁
Normal
使能
，航空器正常
推岀
；
当
ran
<
P
时
，
冲突产生
，
变迁
Wait
使能
。
P
表示发
生推岀冲突的概率
。时间延迟
delay
表示产生推岀冲突后航
请的航空器
。
3
系统仿真分析
选定天津滨海国际机场作为研究对象
，
验证
HTCPN
空器
车
在
的时间
。
2.6
航空器推出
动态
仿真系统解决实际
位之间的连接线
，
的有效性
。
机场停机位布
航空器推岀后伴随着牵引车和航空器信息的更新
，
航
空器推岀过程模型如图
6
所示
。
如图
7
所示
，
特种车辆需严格按指定路线行驶
，
即图中
各
车的停车场位于
18
号和
201
首先通过替代变迁
UpdteTug
,
代表牵引车的托肯重
新回到牵引车
所
（
Tug
）
,
此时牵引车服务过航班序
号
位之间
。
根据地理位置可以得岀不同地面点间的邻接关系
，
并
列
、
时刻位置
、
可为
航
服务时刻
、
行驶总
计算
意
面点之间的
。
根据文献
）
6
*
第
42
卷第
1
期
苏志刚
，
赵松泽
，
郝敬堂
：
基于
HTCPN
的牵引车动态优化调度
・
299
・
、
fc
<
7
k
<
-
w>
<
M
g
I
T
ffi
^
图
9
牵引车平均行驶总距离
中的通用配置方法可估算岀
天津机场牵引车理论配置数量
为
12
辆
。
表
3
为
仿
实
验
中
设的
推
作
时
型
的
关
系
。
负荷差累计和随航班数量的增加近似周期性变化
，
在服务
航班数量为
60
时
达到最低点
，
由于
实
验
中
12
辆
牵引车被
表
3
作业时间均值
机型分类
C
的任务数
近于
0
。
相等
，所以
车
辆间
工作负
代表机型
B737
,
A320
作业时间均值
5
min
由图
9
可见
，
场面内所有牵引车平均行驶总距离与服
务航
班数量的关系
。随着
服务航
班数量的累加
，
行
驶
总距
D
B<6<
&
A310
B777
,
A330
6
min
7
min
的
更
为
。
处理的
E
为体现仿真系统对随机变化的动态反应
，在保证离港
基于
蒙
特卡洛方法
⑴
*
对高峰时段的牵引车
动态
调度进
航班信息相同的前提下
，
可以将系统中
行仿
析
，
仿真系统中
设定航
'A
*
25
架次
/
小
数
据
为固定
的常量
再次实验后进行对比分析
。
在对照
组实验中
，
将发生航空器推岀冲突的概率设置为
0
,
牵引车
时
，
牵引车行驶速度
^
=20km/h
,
作业时间的标准差
0.5min
,
推岀冲突发生概率
P
confii-
*
20%,
原地等待时间
推
岀航空器的
作
业时间不再
服
从高
斯
推岀时间均为
5
min
。
&
所
有航空器的
均值
T
cofict
*
5min
。
在
不
同的服务航班数量
车平
100
次独立实验
，
图
8
和图
9
显示了牵引车工作负荷均衡度和
驶总
后
的
比
。
表
4
中分别罗列了引入常量数据和随机数据每辆牵引
车依次服务过的航班序列
。
表
4
牵引车服务过航班序列
车
号
1
服务过
航
班序列
量数
据
[1,14,26,42
*
[2,17,29,40,50
*
[3,13,25,37
*
[4,21,33,44
*
[5,16,28,41
*
[6,22,34,47
*
吴
M
更
糊
陋
昌
叵
躍
卅
数
据
[1,14,26,42
*
2
3
[
21<294050
*
[
3132538
*
[
4213345
*
[
516283<
*
[6,22,34,47
*
[7,19,32,44
*
[
8152<3949
*
4
5
6
7
[7,19,31,43*
图
8
车辆间工作负荷差累积和
8
9
[
8152<38
*
图
8
的纵轴是表征不同车辆工作负荷均衡度的负荷差
累积和
10
N
—
N
j
B
，
优化前车辆负荷差累计和与服
11
12
务航
班数量呈现正相
关
的
。
后
的
大
？
低,
[
918303949
*
[
10233545
*
[
11243648
*
[12,20,32,46
*
[
9
18
30
41
*
[
10233546
*
[
11243648
*
[
12203143
*
・
300
・
航空器托
肯
刻
、
计算机工程与设计
状态
带的
车到达时
30
2
8
6
2
4
2
2
2021
年
推岀时
成推岀时
实验结
果对应的
甘
特图
，
如图
10
和图
11
所示
。
W
9
8
7
6
5
4
3
2
1
7:45
8:00
8:15
8:30
8:45
9:00
9:15
9:30
9:45
10:00
时刻
■
牵引车等待时间
□
牵引车服务时间
图
10
采用常量数据时
车调度结果
7:45
8:00
8:15
8:30
8:45
9:00
9:15
9:30
9:45
10:00
时刻
■
牵引车等待时间
□
牵引车服务时间
图
11
采用随机数据时牵引车调度结果
综合表
4
、
图
10
和图
11
可以发现
，
当考虑到航空器发
生推岀冲突的可能性以及推岀时间分布的随机性后
，
牵引
车的
时
服务时
相应地受到影响
，
此时系统会
为基础追求局部最优解
，
因此航空器与牵引车
的
方
用常量数据时产生
大的变化
。
航局相关文件规定
，
车应在待服务航空器
预
计
离港时刻前
5
min
到位
，
否贝
IJ
将被视作晚点到达。
由图
10
图
11
&
航
务的
车
时
大于
5
min
,
表明没有延误发生
，
且优化后每辆牵引车的任务量
得到了合理的分配
。
航
入
和牵引车数量
N
进一步评估天津机场
牵引车的保障能力
。
在
参数下进行
200
次蒙特卡
洛实
验
，
牵引车晚点率随
入
和
N
的变化关系如图
12
所示
。
率
10%
作为评估保障能
格
的临界
值
。
从图中可以发现
，
当
入
2
29
架次
/
小时
，
11
辆牵引车就
可以将晚点率控制在
10%
之下
，
表明机场当前配置的
12
辆
牵引车是冗余的
，
此时可适当减少场面
车的使用数
量
；
当
30
架次
/
小时
2
入
2
33
架次
/小时
，
当前机场配置刚
准
求
，
车数量应
状
；
当
34
架
次
/
小时
2
入
2
37
架次
/
小时
，
现有配置已无法满足需要
，
配
置
13
辆
车
使得晚点率
到
10%
以下
；
当
入
继续
2
%
2
0
、
<
1
8
淫
1
6
堡
1
4
1
2
丽
W-
«
1
0
8
6
2
O
航班密度/(
架次
/
小时)
t
-7V=12
-
»-N=13
图
12
车晚点率变化曲线
增大时
，
在现有配置下增
辆
车
有效改
引
车的延
。
4
结束语
基于层次赋时着色
Petn
网理论搭建了机场牵引车动态
调度仿真系统
。
根据航空器实时
的推
请完成牵引
车的动态分配
。
同时考虑了运行过程中各个环节的随机性
以及高峰时段可能发生的推岀冲突问题
。
在还原机场现有
调度模式的基础上
&
多目标优
实现航班延
基础目标
&
之后依次实现不同车
辆
工作负
衡
高和车
辆行驶总
的
目标
。
天津滨海国际机场为例
，
通过蒙特
卡洛
实验验证
：
化
的有效性
，
同时验证
方法
目
场的牵引车保
能
估
，
最后通
方法
预
在不同航
：
度
下必要的牵引车配置数量
。
参考文献
：
Civil
Aviation
Administration
of
China.
2017
statistical
bulletin
of
civil
aviation
industry
development
[R*.
Beijing
：
Develop
ment
Plan
Department
of
CAAC,
2018
：
1-17
(in
Chinese).
[中国民用航空局.
2017
年民航行业发展统计公报
[R*.
北
京
：
民航发展计划司
，
2018
：
1-17.]
[2*
LIU
Yi
,
ZHANG
Jun
,
DING
Cong
,
et
al.
Modeling
and
heu
ristic
algorithm
of
ground
ferry
vehicle
scheduling
in
large
air
ports
[M
*
.
Beijing
：
CICTP
,
2019
:
159170.
[3
*
ZHU
Xinping
&
HAN
Songchen.
Centralized
scheduling
of
ser-
vicevehiclesforaircraftturnaroundbasedonpartheno-genetic
algorithm
[J*.
Journal
of
Southwest
Jiaotong
University,
2018
,
53
(2
)
：
406-413
(in
Chinese
)
.
[朱新平
，韩松臣
.
过
站
保障车辆
集中式调度的单亲
遗传算[*
•
西
南
交通大学学
报
,
2018
,
53
2
)
：
406-413.
*
[
4
*
WANG
Zhurong
,
LIYou
,
HEIXinhong
,
chon
airportrefueling
vehiclescheduling
problem
based
on
greedy
algorithm
[C*
//Intenational
Conference
on
Intelligent
Com
puting.
Wuhan
：
Springer,
2018
：
717-728.
[
11
*
ZHANG
Xuehua6Analysis
of
KATL
operation
simulated
by
TAAM
[
J
*
6Applied
Mechanicsand
Materials
,
2015
,
713
：
1601-16046
[5*
Jia
Yan
Du,
Jens
O
Brunner,
Rainer
Kolisch.
Planning
towing
processes
at
airports
more
efficiently
[J*.
Transportation
ResearchPartE
：
LogisticsandTransportationReview
,
2014
,
70
(1
)
：
293-304.
[
12
*
LiXiong
,
WeiDongxuan
,
LiDongbin
,
etal6Utilizationpat-
ternofcloselyspacedpara
l
elrunwaysandsimulationofopera-
tionale
f
iciency
[
C
*//
IEEEInternationalConferenceonPro-
[
6
*
Andrea
t
aG
,
DeGiovanniL
,
MonaciM6Afastheuristicfor
airport
ground-service
equipment
and
sta
f
a
l
ocation
[
J
*
6
Procedia-SocialandBehavioralSciences
,
2014
,
108
：
26-366
gress
in
Informatics
&
Computing.
Shanghai
:
IEEE,
2016
：
158-1626
[13
*
LIU
Ruoyang
,
CUI
Jinchuan
,
SONG
Yuqing.
Forward
greedy
heuristic
algorithm
for
n-vehicle
exploration
problem
[7
*
HENG
Hongjun
,
WANG
Fang.
Research
on
rell-time
schedu-
lingofairportspecialvehiclesbasedon
MAS
[
J
*
6Application
ResearchofComputers
,
2017
,
34
(
9
)
：
2599-2604
(
in
Chi-
nese
)
.
[衡红军
，
王芳
.
基于
MAS
的机场特种车辆实时调度问
题的研究
[J
*
.
计算机应用研究
，
2017
,
34
(9
)
：
2599-2604.]
[8
*
XINGZhiwei
,
WEI
Zhiqiang
,
LUO
Qian
,
et
al.
Flight
sup-
portserviceprocessmodelingmethodbasedoncoloredtimePetri
net
[
J
*
6SystemsEngineeringandElectronics
&
2018
&
40
(
5
)
：
1064-1069
(in
Chinese
)
.
[邢志
伟
，
魏志强&罗谦
，
等
.
基于
着色时间
Petti
网的
航
班保障服务建模方法
[J*.
系统工程与
电子技术
，
2018
,
40
(5
)
：
1064-1069.]
[
9
*
GOU
Jingjing6Prediction
of
the
minimum
requirement
of
ground
vehicles
for
airport
planning
[J
*
.
Jounal
of
Civil
Aviation
Flight
University
of
China
,
2015
,
27
(2
)
：
50-53
(in
Chinese).
[苟晶晶.机场规划所需地勤保障车辆最低数量预
测
[J
*
.
中国民航飞行学院学报
，
2015
,
27
(2
)：
50-53.]
[
10
*
LIAO
Dan
,
HUANG
Baojun6Simulation
andevaluation
of
airportcomprehensivesupportcapabilitybased
AirTOp
[
J
*
6
AeronauticalComputing
Technique
,
2017
,
47
(
1
)
：
77-80
(in
Chinese).
[廖丹
&
黄宝军
.
基于
AirTOp
机场综合保障能
力仿真与评估
[J
*
.
航空计算技术
，
2017
,
47
()
：
77-80.]
(
NVEP
)
[
C
*
//
8th
International
Symposium
on
Computa
tional Intelligence
and
Design.
Hangzhou
：
IEEE
,
2016
：
243
246.
[
14
*
Lin
MingHsin
,
ZhangYimin6Hub-airportcongestionpricing
and
capacity
investment
[J*.
Transportation
Research
Part
B
：
Methodological
,
2017
,
101
"
89-1066
[
15
*
Pan
Weijun
,
Yang
Lei
,
Zhu
Xinping
,
etal6
Modeling
of
complex
apron
conflict
control
based
on
petri
net
model
[
C
*//
InternationalConferenceon
Modeling
,
Simulationand
OptimizationTechnologiesand
Applications6Xiamen
"
Atlan-
tisPress
,
2016
"
10-126
[
16
*
CivilAviationAdministrationofChina6Civiltransportairport
flightsupportspecialequipmentconfigurationguide
[
S
*
6Bei-
jing
"
TransportDepartmentofCAAC
,
2015
"
1-61
(
in
Chi-
nese).
[中国民用航空局.运输机场航班保障专用设备配置
指南(试行)
[S*
.
北京
：
民
航运输司
&
2015
：
1-61.]
[17*
Zhao
Xianqiong,
Olaf
Malasse,
Gregory
Buchheit.
Verifica
tion
of
safety
integrity
level
of
high
demand
system
based
on
stochasticpetrinetsandmontecarlosimulation
[
J
*
6Reliabili-
ty
Engineering
&
System
Safety
,
2019
,
184
:
258-265.
2024年3月16日发(作者：位寒梦)
2021
年
1
月
计算机工程与设计
COMPUTER
ENGINEERING
AND
DESIGN
Jan.
2021
Vol.
42
No.
1
第
42
卷
第
1
期
基于
HTCPN
的
牵引车
动态优化调度
苏志刚
，赵松泽
，
郝敬堂
（
中国民航大学中
欧
航空工程
师
学院
，
天津
300300
）
摘
要
：
针对机场牵引车动态调度问题
，
基于层次赋时着色
Petri
网
（hierarchical
timed
colored
Petri
net
,
HTCPN
）
搭建
牵引车动态调度仿真系统
。
在充分考虑实际运行过程中各个步骤的随机性后
，
根据航空器实时发送的推出申请完成牵引车
的动态分配
。
在保障航班延误最少的基础上依次实现不同车辆间工作负荷均衡度最高和车辆行驶总距离最短的优化目标
，
通过蒙
特卡洛实验验证了优
化的有
效性
。
利用
该系统
完
成对
目标
机
场牵引
车
保障能力
的评估
，
预测在不同
航
班密度下必要
的牵引
车
配置数量
。
关键词
：
牵引车动态调度
；
层次赋时着色
Petn
网
；
多目标优化
；
保障能力评估
；
蒙特卡洛实验
中图法分类号
：
TP15
文献标识号
：
A
文章编号
：
1000-7024
（
2021
）
01-0294-08
doi
：
10.
16208/j.
issnl
000-7024.
2021.
01.
042
Dynamic
optimal
scheduling
of
tractors
based
on
HTCPN
SU
Zhi-gang
,
ZHAO
Song-ze
,
HAO
Jing-tang
(
Sino-European
Institute
of
Aviation
Engineering
&
Civil
Aviation
University
of
China,
Tianjin
300300,
China)
Abstract
：
Aiming
at
the
dynamic
scheduling
problem
of
airport
tractor,
a
dynamic
scheduling
simulation
system
of
tractors
was
designed
based
on
hierarchical
timed
colored
Petri
net
(
HTCPN)
.
After
fully
considering
the
randomness
of
each
step
in
the
actual
operation
process,
the
dynamic
allocation
of
the
tractors
was
completed
according
to
the
pushback
application
sent
by
the
aircraft
in
real
time.
On
the
basis
of
ensuring
the
minimum
of
the
flight
delay,
the
optimization
goal
of
the
highest
load
balance
amongdi
f
erenttractorsandtKesKortesttotaldistancetraveledbytractorswererealizedinsequence6TKee
f
ectivenessoftKe
optimization
was
verified
by
Monte
Carlo
experiment.
The
system
was
used
to
evaluate
the
support
capacity
of
tractors
at
the
tar
geNairporN
andNopredicNNhenecessarynumberofNracNorsaNdi
f
erenNflighNdensiies6
Key
words
：
dynamic
scheduling
of
tractors
；
hierarchical
timed
colored
Petri
net
；
multi-objective
optimization
；
support
capability
assessment
；
Monte
Carlo
experiment
/
引言
快速增长的航空运输量极大增加了机场场面的运行压
度问题进行优化
。
即假设在航班计划
、
航班需求时间窗以
及作业时间等信息已知并始终不变的前提下
，
根据航班的
需求规划车辆的行驶路径
（
实际情况下影响航班运行的随
机因素较多
。
当随机因素对原有航班计划产生影响时
，
车
力
[1]
o
目前我国大部分机
场
的工作人
员
是通过目
视
、
语音
对讲等方式对符合条件的车辆进行调度也，
落
后的信息获
辆资源需要重新分配
。
虽然启发式算法可以得到可行解
，
但其不能很好地对调度过程中的随机因素实时响应
。
取方式及决策过程导致航班高峰时段调度效率低下
，
进而
影响航班的准点率
。
地勤保障车辆调度问题持续受到国内
系统仿真方法利用离散仿真模型模拟调度流程
，
十分
适用于机场车辆调度这种存在诸多不确定因素的离散动态
外学者的广泛关注
，
研究方法主要集中在运筹学方法
37
*和
系统
仿真方法
82
两个方面
。
运筹学方法是将车辆调度问题简化为多目标优化模型
,
再利用启发式算法进行求解
（启发式算法主要是对静态调
收稿日期
：
2019-09-12
；
修订日期
：
2020-05-25
随机过程的分析
。
采用仿真方法可以很好地模拟调度过程
中的突发事件
，
设计出针对不同随机问题的解决方案
（
芝
加哥机场和日本民航局采用
TAAM
[11]
（
total
airspace
&
基金项目
：
中央高校基本科研业务费中国民
航
大学专项基金项目
（
3122017111
）
作者简介
：
苏志刚
（
972-
）
,
男
，
黑龙江尚
志
人
，
博士
，
教授
，研究方向为信号与信
息处理
、
监
视与导航；
赵松泽
（
1994
-
）
,
男
，
天津
人
，
硕士研究生
，
研究方向为机场保
障车辆调度和航空]
场面
滑行的仿真
；
郝敬堂
（
1989
-
）
,
男
，
河南
鹤壁人
，
硕士
，
实验师
，
研究方向
为空管监
视
数
据
处理
、
室内
导航等
（
:
************.com
第
42
卷第
1
期
苏志刚
，
赵松泽
，
郝敬堂
：
基于
HTCPN
的牵引车动态优化调度
•
295
•
airport
modeler
)
对空域和飞行区进行仿真研究
，
分析机场
分配该牵引车从当前位置驶向指定机位进行服务
。
若所有
的运行方式和空域构型
。
丹佛机场利用
SIMMOD
)
2
*
分析现
有飞行区的运行状况以及新的改造措施对延误的影响
。
上
牵引车当前时刻均处于工作状态
，调度人员会根据反馈信
息指派最先完成当前任务的牵引车执行该任务
。
现行调度
规则存在以下问题
。
(1)
述仿真软件虽然功能强大
，
但价格昂贵
，
且仿真的主要对
象是航空器
，
仅有少部分功能涉及到车辆调度过程
。
每辆牵引车航班任务分配不均衡
；
本文运用层次赋时着色
Petri
网
(
hierarchical
timed
colored Petn
net,
HTCPN)
对牵引车调度过程进行仿真
(
(2)
为航空器分配牵引车时没有考虑候选车辆与服务
需求点间的距离
。
为解决当前调度模式下存在的问题
，
需要依次从车辆
利用层次
Petri
网
(hierarchical
Petri
net,
HPN)
对系统进
行模块划分
，
增加模型的可视性
；
利用着色
Petn
网
到达时间
、
车辆工作负荷均衡度和车辆行驶距离
3
个方面
(colored
Petn
net
,
CPN)
对不同资源进行标记区分
；
利用
赋时
Petri
网
(timed
Petn
net
，
TPN
)
模拟牵引车资源占用
和释放的实时情况
。
搭建动态调度仿真系统
，
根据航空器
发送的推出申请完成航空器与牵引车的动态匹配
。
提出调
度优化方案
，
实现不同车辆间工作负荷均衡度最高和车辆
行驶总距离最短的优化目标，通过仿真实验验证了优化的
有效性
。
最后完成对目标机场牵引车保障能力的评估
，
预
测在不同航班密度下的牵引车配置数量
。
1
牵引
车
调度数学模型
1.1
调度流程分析
针对牵引车调度特点
，
将调度流程简化为如下步骤:
首先按照假设的规则随机生成离港航班信息
，
系统根据每
架航空器的预计离港时刻非降序排列所有航班信息形成航
空器等待队列
，
每架航空器在其预计离港时刻前
Tm
分
钟发出推出申请
；
系统按照设定的动态优化调度目标逐一
为待服务航空器分配满足条件的牵引车前往服务
；
牵引车
在开始推出任务前判断与邻近机位是否存在推出冲突
，
如
存在冲突则在原地等待
；
待冲突解脱后牵引车将航空器推
出到指定位置
，并完成信息的记录与更新。
1.2
基
本假设
机场场面运行过程中包含诸多随机因素
，
在不影响牵
引车和航空器正常运行的前提下对模型做如下假设
：
(1)
单位时间内离港航空器数目服从参数为
人
的泊松
分布
)
314
*
;
(2)
正常情况下
，
每架航空器在其预计离港时刻前
T
Re
q
ues
t
=
15min
发出推出申请
；
(3)
牵引车推出航空器时与邻近机位发生推出冲突的
概率为
P
mic
，
若存在推出冲突
，
牵引车和航空器在原地等
待的时间满足均值为
T
oni
的指数分布
；
(4
)
牵引车推出航空器的作业时间服从高斯分布
N
(
“
,
/)
。
作业时间的均值
$
由被服务航空器的机型决定
。
标准
差
。
的取值与航空器机型无关
，
与推出时地服人员和飞行
员配合的
熟
练度有关
。
1.3
优化目标
在
有运
模
，
到推
请后，
按
照车
辆
序号顺序分配可用车
辆
。
如果存在可用车辆
，
立刻
进行优化
。
车
辆
到达时间
：
在实际运行中时间因素最为重要
，
要
求车
辆
延
到达的时
C
#
=
min$[
'g!
；
)
X
；
()
式中
：
；
表示第
&
架航空器因牵引车晚点造成的延误时间,
式
(
2)
是表示延误与否的符号函数
sign
；
)
=
1
-
;
>
0
(2)
0
，
;
&
=
0
车辆工作负荷均衡度
：
为保证牵引车的安全使用和驾
驶人员的合理分配
，
调度车
辆
时应尽量提高不同车辆间工
作负
的
衡
，
用车
辆
工作负
的
作
为表
衡
的目
函数
G=mm"
N
,-
N
j
⑶
式中
：
V
表示牵引车的集合
，
N
：
和
N
j
表示编号为分和
j
的牵
引车服务过的航班数量
。
车
辆
驶
：
车在不同
位
的
不
忽略
，
减少行驶距离可进一步保证牵引车的准时到达
，
同
时降低机场或航空公司的燃油成本
C
3
=
⑷
式中
：
N
表示编号为
，
的牵引车行驶过的总距离
。
2
HTCPN
动态调度仿真系统
2.1
模型描述
建模采用自顶向下的分解原则
。
首先确定调度流程的
整体功能模型图
，
然后再对顶层模型进一步细化
，
在子页
中实现子流程功能
，
形成分层模型
。
牵引车动态调度仿真
系统的层次赋时着色
Petn
网模型可简化为以下多元组
HTCPN
=
(S,SN,SA,PN,PT
)
(5)
HTCPN
中各参数的含义分别为
：
()
S
代表子页的有限集合
，
每个子页对应于调度过
程中一个关键的子流程
，
依次为航空器推出申请
、
航空器
牵引车实时匹配
、
航空器推出冲突
、
航空器推出过程
。
s
中
的任意子页
s
均是一个非层次的赋时着色
Petn
网
s
=
LPN
,
R
,
)
)
(6)
式中
：
K
是时间值的集合
，
称为时间戳
；
)
是
R
中的元素,
对应于调度过程的起始时刻
。
・
296
・
计算机工程与设计
2021
年
（
2
）
SN
是替代变迁
，
SN
J
T
&
T
表示变迁集合
，
采用
变迁代表
Petri
网
中的某一模块&使得网络在
到
&之后在对应的
变迁间的对应关系
。
更深
的
建模
。
（
3
）
SA
是页分配函数
，
SA
：
SN
6
S
,
表示子页和替代
（
4
）
PN
代表端口节点的集合
&
PN
J
?
表示库
所集合
。
（5
）
PT
是端口类型函数
，
是从
PN
定义到
｛
In,Out
,
In/Out,General
｝
的函数
。
式
（
6
）
中的参数
CPN
表示一个非层次的着色
Petri
网
，
可用如下
9
元组表示
CPN
*
（
P,TA,
X
JC5O
J
）
（
7
）
图
1
牵引车调度顶层模型
表
2
顶层模型中替代变迁及其对应子过程
替代变迁
Request
式中
：
P
表示库所集合
，
以椭圆形表示
，
可以表示动态调度
仿真系统各
的实时状态
；
T
表示变迁集合
，
以矩形表
子过程
航空器推出申请
航
器
车实时
示
，
代表
中
具体事件的发生
，
实现不同库所间的
信息传递
;
A
为有向弧集合&是联系库所
之间的流关
的
表达式&
。
系
；
/为颜色集的非空有限集合
；
J
为变量集合；
C
为颜色
Match
Conflict
集函数
，
定
所的数据类型
；
5
为
航空器推出冲突
航
器推
E
为有向弧表达式
，
守卫表达式和弧表达式共同定义了变
Pushback
迁的使能条件
；
/
为
型的
函数
，
定
所的
生个数和位置的
&
托肯
（
token
）
表示分配给库所的资源
，
在
Petri
网模
库所
Plane
存储系统随机生成的航班信息
，
库所
Tug
存储机场内初始时刻所有牵引车的信息
，
库所
Airport
对应
中
。
车和航空
器是模型中两种不同类型的
色
其
不同的
颜
于机坪不同位置点距离的录入
，
以上
3
个库所是模型中初
。
后
其输
所移
肯
，同时
信息的输入窗口
。
所有航空器会依次通过
4
最终回到
Finish
PlaneList
库所中
，
该库所的作用是记录每
架航空器被推岀后的最终状态
。
，
库所
Capacity
对航
向输
所增
肯
，
从而
模型状态的改变
。
航空器
车的
颜
色集
表
1
。
器
队
列起到容量
的作用
。
在库所
的
HTCPN
模型形成
的
表
1
航空器与牵引车颜色集
肯
共同作用下
，
馈
。
23
航空器推出申请
环反
颜色
集
（
航班号
、
停机位
、
机型、
预计离港时刻
、
匹配的
车编号
、
牵引车到达时刻
、
开始推出时刻
、
完成推出
时刻
、
牵引车提前
/
晚点到达时间
）
航空器
顶层模型中表示航空器推岀申请的替代变迁
（
R-
quest
）
后
到如图
2
所示的
模型
。
牵引车
（
牵引车编号、
当前状态
（
工作
/
空
闲
）
、已服务航班序
列
、
已服务航班数量
、
当前时刻位置
、
可为
航班
开始服务时刻
、
行驶总
）
系统首先通过
Timetable
变迁在一定规则下随机生成航
班数据
。
该
器所在
表达式中的
density
用于模拟服
位编号
，
时
松
分布的航班流
。
库所
Apron
中存储系统自动生成的离港航
航班号
、
停机位、
牵引车编号等初始属性的作用是对
托肯的活动
，
同时确保同
&
车到达时刻
、
牵引车已服务航
条件
。
一机位在
2
小时内不会被再次分配
。
生成的航班信息在
List
中以列表的形式存储
。
List
中的航班列表再通过
Sort
序列
、
车
位
属性
系统的运行实时更
&更新后的
2
2
顶层模型
成为后续运行中新的
成按预计离港时刻的非降序排列
，
在
Queue
中形成
航班的等待队列
。
最后通过
Request
变迁逐一发岀推岀申
请
。
通过
Capacity
库所可以使系统逐一地接收航空器
队
列
的推
请
，
而实
动态调度仿真系统的顶层模型如图
1
所示
。
替代变迁
用双框矩形表示
，
各
的
表
2
。
航
器
队
列的容量
。
所右下方的标识代表颜色集
，
根据容纳的资源类型
端点为
的弧为
抑
，
作用是设
生的优先
，
而
自
分为
4
类
：
航空器状态库所
（
Plnfor
）
、
航空器
队
列状态库
权
。
当库所
Plane
中存在托肯时
，
变迁
Sort
无法发生
，通
抑
使
队
在航
信息生成后
所
（
LPInfor
）
、牵引车集合状态库所
（
LCInfor
）
和约束类
所
（
LDistance
，
Cap
）
。
主控制仿真实验中的航空器数目
。
Request
输岀弧上的
第
42
卷第
1
期
苏志刚
，
赵松泽
，
郝敬堂
：
基于
HTCPN
的牵引车动态优化调度
・
297
・
Plane
In/Out
plane
PInfor
input
(plane);
output
(density,initT);
action(Exponential(r),
#6
plane);
lpplace
Timetable
lpplace
(
Apron
Out
plane@+applytime
PInfor
[plistof]]
In/Out
Capacity
0
Request
LPPlace
[plane]^plist
Hl
List
[plistoQ]
Cap
input
(plist);
output
(plane,applytime);
action(
plist,
#6(
plist
)-T-mtTimeQ);
Sort
SortPbyT
(plist)
(
-----------------
►(
Queue
LPInfor
plist
LPInfor
图
2
航空器推出申请模型
applytime
是航空器发岀推岀申请的时刻
，
作为每架航空器
状态
基于
婪算法是
带的时间戳
。
算法设计了航空器牵引车实时匹配算法
。贪
开始
24
航空
器牵引
车实
时
匹配
依次读取待服务航班
发出的推出申请
为基础追求
的推
&
针对航
器
队
列
如图
3
所示
。
请逐
成
车的分配
，
对动态
车实时
算法
车辆到达时间匹配
有一定的解决能力
，
航空器
系统在读取待服务航空器发岀的推岀申请后
，
依次以
车
辆
到达时间
、
车
辆
工作负
衡
及车辆行驶
仅有一辆牵弓
、
宇满足需求/
否
车辆工作负荷
均衡度匹配
为
判据
空闲状态的
条件的
车集合
。
首先实现车辆到达时间的匹配
，
筛选岀当前时刻处于
车集合
，
如若没有
车
辆
，
定完成
衡
是
服
反有一辆牵引
连满足需求―
，
否
务时
的
车
。
车
辆
工作负
辆
车服务过的航班数
非降序排列
辆
务航班数
的
车集合
。最后
驶总
车行驶总
成非降序排列
，
的
车
，
车辆行驶距离匹配
是
从而实现车辆行驶距离的匹配
。
若此时满足条件的牵引车
仍多于一辆
，
则按照车辆序号顺序随机指派一辆牵引车前
服务
。
是
，
否
基于上述算法建立了如图
4
所示的航空器牵引车实时
匹配模型
。
模型中从上至下的
3
个替代变迁分别对应于流程图中
按照牵引车编号在集合中
选取第一辆牵引车
安排该牵引车
前往相应的停机位
是
的车辆
到达时
驶
(
、
车
辆
工作
负
后的节
后的
衡
车
辆
所
表示航空器
的
状态和经
车集合状态
。
车集合
Tug
同时
结束
推岀申请后的航空器
绑定于
Arrival
Time
替代变迁，
目的是筛选岀满足时间要
求的
图
3
航空器牵引车实时匹配算法
车集合
。
经过第一步
后的
车集
航空
辆最少的牵引车集合
(
Airport
以邻接矩阵的格式存储目标
器同时绑定于
Load
Balance
替代变迁
，
筛选岀服务航班数
・
298
・
计算机工程与设计
2021
年
Load
Balance
图
4
航空器牵引车实时匹配模型
机场内不同位置点间的距离
，
通过
Distance
替代变迁搜索
辆
车
位
服务航空器
计算岀行
驶到目的点的时间
。
经过
3
条件的
服务
。
2.5
航空器推出冲突
后产生
'满
车
，
系统安排该
车
相应的
位进
在机场运行高峰时段
，
邻近停机位航班常会因离港时
而
突
。
当航空器侧向推岀时与同
位
推
推岀的航空器由于安全
而产生冲突
）
5
*
,
，
只有当前
图
6
航空器推
出过
程模型
生推岀冲突后的解决方案是后机在
滑行通过推岀安全点后，
后机才能
推岀&推
距离等属性随之更新
。
下一步再通过替代变迁
UpdatePlane
完成航空器信息的更新
，
代表航空器的托肯
已被推岀
航空器队列库所
（
Finish
PlaneList
）
，
记录航空器被服务后
突会导致牵引车使用时间的增加以及实际推岀时间的
延迟
，
推岀冲突的模型如图
5
所示
。
待服务航空器
步
的牵引车同时绑定于变
的
状态
，
的牵引车编号
、
车到达时刻
、
为
架发岀
迁
Ran
,
通过
Ran
在库所
Conflict
中产生随机数
ran
,
再根
据
Norma
和
Wait
上的守卫函数判断航空器推岀冲突事件
推岀时刻
、
完成推岀时
推
属性
。
推
务完成后容
量库所中的托肯也完成更新
，
服务
是否发生
。当
ran
>
P
时
，
变迁
Normal
使能
，航空器正常
推岀
；
当
ran
<
P
时
，
冲突产生
，
变迁
Wait
使能
。
P
表示发
生推岀冲突的概率
。时间延迟
delay
表示产生推岀冲突后航
请的航空器
。
3
系统仿真分析
选定天津滨海国际机场作为研究对象
，
验证
HTCPN
空器
车
在
的时间
。
2.6
航空器推出
动态
仿真系统解决实际
位之间的连接线
，
的有效性
。
机场停机位布
航空器推岀后伴随着牵引车和航空器信息的更新
，
航
空器推岀过程模型如图
6
所示
。
如图
7
所示
，
特种车辆需严格按指定路线行驶
，
即图中
各
车的停车场位于
18
号和
201
首先通过替代变迁
UpdteTug
,
代表牵引车的托肯重
新回到牵引车
所
（
Tug
）
,
此时牵引车服务过航班序
号
位之间
。
根据地理位置可以得岀不同地面点间的邻接关系
，
并
列
、
时刻位置
、
可为
航
服务时刻
、
行驶总
计算
意
面点之间的
。
根据文献
）
6
*
第
42
卷第
1
期
苏志刚
，
赵松泽
，
郝敬堂
：
基于
HTCPN
的牵引车动态优化调度
・
299
・
、
fc
<
7
k
<
-
w>
<
M
g
I
T
ffi
^
图
9
牵引车平均行驶总距离
中的通用配置方法可估算岀
天津机场牵引车理论配置数量
为
12
辆
。
表
3
为
仿
实
验
中
设的
推
作
时
型
的
关
系
。
负荷差累计和随航班数量的增加近似周期性变化
，
在服务
航班数量为
60
时
达到最低点
，
由于
实
验
中
12
辆
牵引车被
表
3
作业时间均值
机型分类
C
的任务数
近于
0
。
相等
，所以
车
辆间
工作负
代表机型
B737
,
A320
作业时间均值
5
min
由图
9
可见
，
场面内所有牵引车平均行驶总距离与服
务航
班数量的关系
。随着
服务航
班数量的累加
，
行
驶
总距
D
B<6<
&
A310
B777
,
A330
6
min
7
min
的
更
为
。
处理的
E
为体现仿真系统对随机变化的动态反应
，在保证离港
基于
蒙
特卡洛方法
⑴
*
对高峰时段的牵引车
动态
调度进
航班信息相同的前提下
，
可以将系统中
行仿
析
，
仿真系统中
设定航
'A
*
25
架次
/
小
数
据
为固定
的常量
再次实验后进行对比分析
。
在对照
组实验中
，
将发生航空器推岀冲突的概率设置为
0
,
牵引车
时
，
牵引车行驶速度
^
=20km/h
,
作业时间的标准差
0.5min
,
推岀冲突发生概率
P
confii-
*
20%,
原地等待时间
推
岀航空器的
作
业时间不再
服
从高
斯
推岀时间均为
5
min
。
&
所
有航空器的
均值
T
cofict
*
5min
。
在
不
同的服务航班数量
车平
100
次独立实验
，
图
8
和图
9
显示了牵引车工作负荷均衡度和
驶总
后
的
比
。
表
4
中分别罗列了引入常量数据和随机数据每辆牵引
车依次服务过的航班序列
。
表
4
牵引车服务过航班序列
车
号
1
服务过
航
班序列
量数
据
[1,14,26,42
*
[2,17,29,40,50
*
[3,13,25,37
*
[4,21,33,44
*
[5,16,28,41
*
[6,22,34,47
*
吴
M
更
糊
陋
昌
叵
躍
卅
数
据
[1,14,26,42
*
2
3
[
21<294050
*
[
3132538
*
[
4213345
*
[
516283<
*
[6,22,34,47
*
[7,19,32,44
*
[
8152<3949
*
4
5
6
7
[7,19,31,43*
图
8
车辆间工作负荷差累积和
8
9
[
8152<38
*
图
8
的纵轴是表征不同车辆工作负荷均衡度的负荷差
累积和
10
N
—
N
j
B
，
优化前车辆负荷差累计和与服
11
12
务航
班数量呈现正相
关
的
。
后
的
大
？
低,
[
918303949
*
[
10233545
*
[
11243648
*
[12,20,32,46
*
[
9
18
30
41
*
[
10233546
*
[
11243648
*
[
12203143
*
・
300
・
航空器托
肯
刻
、
计算机工程与设计
状态
带的
车到达时
30
2
8
6
2
4
2
2
2021
年
推岀时
成推岀时
实验结
果对应的
甘
特图
，
如图
10
和图
11
所示
。
W
9
8
7
6
5
4
3
2
1
7:45
8:00
8:15
8:30
8:45
9:00
9:15
9:30
9:45
10:00
时刻
■
牵引车等待时间
□
牵引车服务时间
图
10
采用常量数据时
车调度结果
7:45
8:00
8:15
8:30
8:45
9:00
9:15
9:30
9:45
10:00
时刻
■
牵引车等待时间
□
牵引车服务时间
图
11
采用随机数据时牵引车调度结果
综合表
4
、
图
10
和图
11
可以发现
，
当考虑到航空器发
生推岀冲突的可能性以及推岀时间分布的随机性后
，
牵引
车的
时
服务时
相应地受到影响
，
此时系统会
为基础追求局部最优解
，
因此航空器与牵引车
的
方
用常量数据时产生
大的变化
。
航局相关文件规定
，
车应在待服务航空器
预
计
离港时刻前
5
min
到位
，
否贝
IJ
将被视作晚点到达。
由图
10
图
11
&
航
务的
车
时
大于
5
min
,
表明没有延误发生
，
且优化后每辆牵引车的任务量
得到了合理的分配
。
航
入
和牵引车数量
N
进一步评估天津机场
牵引车的保障能力
。
在
参数下进行
200
次蒙特卡
洛实
验
，
牵引车晚点率随
入
和
N
的变化关系如图
12
所示
。
率
10%
作为评估保障能
格
的临界
值
。
从图中可以发现
，
当
入
2
29
架次
/
小时
，
11
辆牵引车就
可以将晚点率控制在
10%
之下
，
表明机场当前配置的
12
辆
牵引车是冗余的
，
此时可适当减少场面
车的使用数
量
；
当
30
架次
/
小时
2
入
2
33
架次
/小时
，
当前机场配置刚
准
求
，
车数量应
状
；
当
34
架
次
/
小时
2
入
2
37
架次
/
小时
，
现有配置已无法满足需要
，
配
置
13
辆
车
使得晚点率
到
10%
以下
；
当
入
继续
2
%
2
0
、
<
1
8
淫
1
6
堡
1
4
1
2
丽
W-
«
1
0
8
6
2
O
航班密度/(
架次
/
小时)
t
-7V=12
-
»-N=13
图
12
车晚点率变化曲线
增大时
，
在现有配置下增
辆
车
有效改
引
车的延
。
4
结束语
基于层次赋时着色
Petn
网理论搭建了机场牵引车动态
调度仿真系统
。
根据航空器实时
的推
请完成牵引
车的动态分配
。
同时考虑了运行过程中各个环节的随机性
以及高峰时段可能发生的推岀冲突问题
。
在还原机场现有
调度模式的基础上
&
多目标优
实现航班延
基础目标
&
之后依次实现不同车
辆
工作负
衡
高和车
辆行驶总
的
目标
。
天津滨海国际机场为例
，
通过蒙特
卡洛
实验验证
：
化
的有效性
，
同时验证
方法
目
场的牵引车保
能
估
，
最后通
方法
预
在不同航
：
度
下必要的牵引车配置数量
。
参考文献
：
Civil
Aviation
Administration
of
China.
2017
statistical
bulletin
of
civil
aviation
industry
development
[R*.
Beijing
：
Develop
ment
Plan
Department
of
CAAC,
2018
：
1-17
(in
Chinese).
[中国民用航空局.
2017
年民航行业发展统计公报
[R*.
北
京
：
民航发展计划司
，
2018
：
1-17.]
[2*
LIU
Yi
,
ZHANG
Jun
,
DING
Cong
,
et
al.
Modeling
and
heu
ristic
algorithm
of
ground
ferry
vehicle
scheduling
in
large
air
ports
[M
*
.
Beijing
：
CICTP
,
2019
:
159170.
[3
*
ZHU
Xinping
&
HAN
Songchen.
Centralized
scheduling
of
ser-
vicevehiclesforaircraftturnaroundbasedonpartheno-genetic
algorithm
[J*.
Journal
of
Southwest
Jiaotong
University,
2018
,
53
(2
)
：
406-413
(in
Chinese
)
.
[朱新平
，韩松臣
.
过
站
保障车辆
集中式调度的单亲
遗传算[*
•
西
南
交通大学学
报
,
2018
,
53
2
)
：
406-413.
*
[
4
*
WANG
Zhurong
,
LIYou
,
HEIXinhong
,
chon
airportrefueling
vehiclescheduling
problem
based
on
greedy
algorithm
[C*
//Intenational
Conference
on
Intelligent
Com
puting.
Wuhan
：
Springer,
2018
：
717-728.
[
11
*
ZHANG
Xuehua6Analysis
of
KATL
operation
simulated
by
TAAM
[
J
*
6Applied
Mechanicsand
Materials
,
2015
,
713
：
1601-16046
[5*
Jia
Yan
Du,
Jens
O
Brunner,
Rainer
Kolisch.
Planning
towing
processes
at
airports
more
efficiently
[J*.
Transportation
ResearchPartE
：
LogisticsandTransportationReview
,
2014
,
70
(1
)
：
293-304.
[
12
*
LiXiong
,
WeiDongxuan
,
LiDongbin
,
etal6Utilizationpat-
ternofcloselyspacedpara
l
elrunwaysandsimulationofopera-
tionale
f
iciency
[
C
*//
IEEEInternationalConferenceonPro-
[
6
*
Andrea
t
aG
,
DeGiovanniL
,
MonaciM6Afastheuristicfor
airport
ground-service
equipment
and
sta
f
a
l
ocation
[
J
*
6
Procedia-SocialandBehavioralSciences
,
2014
,
108
：
26-366
gress
in
Informatics
&
Computing.
Shanghai
:
IEEE,
2016
：
158-1626
[13
*
LIU
Ruoyang
,
CUI
Jinchuan
,
SONG
Yuqing.
Forward
greedy
heuristic
algorithm
for
n-vehicle
exploration
problem
[7
*
HENG
Hongjun
,
WANG
Fang.
Research
on
rell-time
schedu-
lingofairportspecialvehiclesbasedon
MAS
[
J
*
6Application
ResearchofComputers
,
2017
,
34
(
9
)
：
2599-2604
(
in
Chi-
nese
)
.
[衡红军
，
王芳
.
基于
MAS
的机场特种车辆实时调度问
题的研究
[J
*
.
计算机应用研究
，
2017
,
34
(9
)
：
2599-2604.]
[8
*
XINGZhiwei
,
WEI
Zhiqiang
,
LUO
Qian
,
et
al.
Flight
sup-
portserviceprocessmodelingmethodbasedoncoloredtimePetri
net
[
J
*
6SystemsEngineeringandElectronics
&
2018
&
40
(
5
)
：
1064-1069
(in
Chinese
)
.
[邢志
伟
，
魏志强&罗谦
，
等
.
基于
着色时间
Petti
网的
航
班保障服务建模方法
[J*.
系统工程与
电子技术
，
2018
,
40
(5
)
：
1064-1069.]
[
9
*
GOU
Jingjing6Prediction
of
the
minimum
requirement
of
ground
vehicles
for
airport
planning
[J
*
.
Jounal
of
Civil
Aviation
Flight
University
of
China
,
2015
,
27
(2
)
：
50-53
(in
Chinese).
[苟晶晶.机场规划所需地勤保障车辆最低数量预
测
[J
*
.
中国民航飞行学院学报
，
2015
,
27
(2
)：
50-53.]
[
10
*
LIAO
Dan
,
HUANG
Baojun6Simulation
andevaluation
of
airportcomprehensivesupportcapabilitybased
AirTOp
[
J
*
6
AeronauticalComputing
Technique
,
2017
,
47
(
1
)
：
77-80
(in
Chinese).
[廖丹
&
黄宝军
.
基于
AirTOp
机场综合保障能
力仿真与评估
[J
*
.
航空计算技术
，
2017
,
47
()
：
77-80.]
(
NVEP
)
[
C
*
//
8th
International
Symposium
on
Computa
tional Intelligence
and
Design.
Hangzhou
：
IEEE
,
2016
：
243
246.
[
14
*
Lin
MingHsin
,
ZhangYimin6Hub-airportcongestionpricing
and
capacity
investment
[J*.
Transportation
Research
Part
B
：
Methodological
,
2017
,
101
"
89-1066
[
15
*
Pan
Weijun
,
Yang
Lei
,
Zhu
Xinping
,
etal6
Modeling
of
complex
apron
conflict
control
based
on
petri
net
model
[
C
*//
InternationalConferenceon
Modeling
,
Simulationand
OptimizationTechnologiesand
Applications6Xiamen
"
Atlan-
tisPress
,
2016
"
10-126
[
16
*
CivilAviationAdministrationofChina6Civiltransportairport
flightsupportspecialequipmentconfigurationguide
[
S
*
6Bei-
jing
"
TransportDepartmentofCAAC
,
2015
"
1-61
(
in
Chi-
nese).
[中国民用航空局.运输机场航班保障专用设备配置
指南(试行)
[S*
.
北京
：
民
航运输司
&
2015
：
1-61.]
[17*
Zhao
Xianqiong,
Olaf
Malasse,
Gregory
Buchheit.
Verifica
tion
of
safety
integrity
level
of
high
demand
system
based
on
stochasticpetrinetsandmontecarlosimulation
[
J
*
6Reliabili-
ty
Engineering
&
System
Safety
,
2019
,
184
:
258-265.