机场调度的队列模型及延误研究

曹风云

张建伟

四川大学，计算机学院，成都610065

摘要：论文讨论了机场航班延误的严重性．基于机场航班排序理论的研究，采用马尔可夫(M矾∞v)链的c-K方程理论建立机场服务队列模型．用模型对飞机进场和离场的时间延误进行预测，仿真实验再现了时间延误概率分布图．由此证明，该模型能直现反映航班延误情况．进一步根据延误情况去制定航班排序策略，是一

个有效的办法．

关键词：航班延误；机场调度；队列模型；M矾【ov链

中图分类号：TP399；V35

文献标识码：A

文章编号：1672—4747(2010)04一0077一04

Resea，rch

on

meQodelueueM

andDelaysofAirportScheduling

CAOFeng

Department

yun

ZHANGJian-wei

Science，

SichuanUniversity，

ofComputer

Chengdu610065，China

^bstract：Based

on

Thethe

great

impactionof

the

delaysof

airport

f1ight

scheduling

wasdiscussedinthis

paper．

researchof

Markov

theory

an

8bout

sequencing，

queue

usingChapman—Kolmogorov

was

equationtheoryofmodel

chain，airport’sf1ights

time

serving

model

established．andthe

This

predictedthe

edelaytim

of

1anding

and

takingoff，

It

simulation

this

experimentmodel

shawedthedistributionof

the

delays

of

delayingprobability．intuitively．

wasprovedthat

couldreflect

will

be

flight

to

Furthermore。

thefli．ght

ordering

strategy

fo瑚ulated

according

thedelayingcondition．

ords：KeywDelayof

flights，airportscheduling，queue

models，Markovchain

收稿日期：2009-ll一06．

基金项目；国家863计划，新型管制自动化系统核心技术。基金号：2006从12A104．

作者简介：曹风云(1984一)，女，湖北襄樊人，四川大学计算机学院硕士研究生，主要研究领域为

图形。

77

字图像处理与计算机

交通运输工程与信息学报20lO年第4期

O

引

言

个跑道的情况下进行建模。此时模型中刀一l，记为

麒f)／口(f)／l。每架飞机接受机场服务是一个独立随机

航班延误是困扰航空运输业的世界性难题。航班延误不仅给旅客带来诸多不便，使航空公司蒙受经济损失，而且严重威胁到机场及空域的安全。目前，中国在进行航班延误恢复时的航班调度上基本采用先到先服务算法(FCFS)。虽然，这对于管制员比较容易实施和操作，但是，调度的效率低，容易造成过度的延误。针对这种情况，日前，学者对机场航班排序问题研究较多。例如，文献【l】提出了基于模糊佩特里(Petri)网的航班进离港调度。通过模拟管制员的调度决策过程，得到优化合理的进场顺序和着陆时刻。文献【2】提出了基于蚁群算法的航班着陆顺序。用蚁群算法寻找符合实际操作的优化排列。文献【3】提出了基于遗传算法的航班动态排序模型。合理安排航班的着陆次序，并在不违反飞机间距要求的情况下给出各飞机经过优化的着陆时间，提高机场跑道的利用率。但是，这些研究均没有直接提出如何估算航班延误的概率。因此，在保证安全及服从整个机场容量限制的前提下，借鉴马尔可夫(Markov)链的C—K方程理论建立3—4机场服务队列模型。该模型是将航班队列作为动态Poisson过程，服务时间满足Erl锄g分布的近似数值模型，能直观反映机场航班延误情况。

现为机场对飞机的调度过程建立Poisson过程的数学模型。设Ⅳ(f)为【O，f】时间内到达的航班数。其中过程，即M钌kov过程。某一时间段内的飞机构成一个独立离散随机序列，该序列构成M甜kov链。通过解出Markov链的C—K方程，即可求出从当前状态到下一状态的概率，即延误概率。1．1航班调度的数学模型

户玑。i。，，mi。为相邻航班的最小时间间隔，r为从O

开始的时间段，因此，o，1，…，f为r段时间内的一系列时间点。则Ⅳ(f)的状态空间为{O，l，2，…>，且具有以下性质：

(1)(零初值性)Ⅳ(o)=0。

(2)(独立增量性)在任意两个不相重叠的时间间隔内到达的航班相互独立。

(3)(时齐性)在【J，f)这段时间间隔到达的航班

数只与时间间隔长度r—s和厶i。有关而与起点时间s无关。

(4)(普通性)在充分小的时间间隔内，最多只

到达一个航班。该性质可用数学公式表达：以p。(岔)

表示在时间间隔△，内第七次航班的延误概率，则存在一个正常数A，使得对充分小的出，有

1

预测模型

进场或离场的飞机队列模型是航班队列为动态

见(址)=l一础+“△，)(在充分小的时间间隔内无航班

到达的概率为卜尬)；pl(△f)=尬+“△f)(在充分

小的时间间隔内有一次航班到达的概率为他)；

Poisson过程，服务时间满足Erl孤g分布的近似数值

模型，该队列模型可记为旭f)／矿(f)伪【4】。模型的运行

原理如图l所示：

黑见(卅=。(出)(在充分小的时间间隔内到达两次或

两次以上的航班几乎是不可能的)。

当{Ⅳ(，)，f≥O}满足上述四个条件的计数过程，

丽一

、／

到苎一

琶

of

the

接受机场调度

(起飞、降落)服务时间

飞机起飞或落入停机坪

则{Ⅳ(，)，r≥O’是强度为加的Poisson过程t41，即

觥)=等c-m㈣’l’2，…

sequencing

1．2

Er

图1机场随机队列模型示意

Fig．1

ModeI

randomfIlght

Jang分布

在该过程中，假设没有天气(大雾、风等)的影响，终端区空域容量可以动态增长，针对当前只有一

当{Ⅳ(f)，f≥o}满足泊松过程，Ⅳ(f)表示【o，f)内随机到达的航班

。设厶表示第疗次航班到达机场的时

机场调度的队列模型及延误研究曹风云等

刻，一=l，2，…，由概率论定义，可知其分布函数为处于调度中的航班架次，假设每次的服务时间是第七阶Erl锄g分布a

初始化时：f=o，po(o)=l，只(o)=O，f>0，通过迭

钟，：l-一薹譬功

【o

Ⅲ

f≤o

这种分布称为埃尔朗(Erlang)分布。因为

代，计算刃(△f)(O≤f≤舭)求解C—K方程，同时可求

出航班的平均等待时间。

基于Markov链的队列模型是无穷队列空间的近似估计，当概率值足够小时，系统再增加七个状态到已存在的状态中，只要△f足够小，产生的概率依然能评估航班入场、出场的时间延误【71。

巴(，)=Ph≤r)=尸(Ⅳ(f)≥由=黑譬“(f≥o)

-t一蓉绎伽

为。的分布函数。其中等e～，七=。，l，2，…为

Poisson过程。由Erl锄g分布来确定到达机场的航班的时间间隔，反映了机场的容量限度。由于L的分布

2仿真实验

在该预测模型中，假设在某一跑道上，共有15架飞机等待降落或起飞(Ⅳ_15)，每架飞机在接受机场调度的过程中，有三种状态：等待调度，接受调度，完成调度(七=3)。Erl锄g分布产生的随机数作为时间点，接受调度的航班架次占机场飞机总量的比例A(f)为0．05，该跑道的容量指数∥(f)为0．9。在Matlab中仿真，通过迭代解C—K方程，得到在状态3和状态

函数为‘o，=l一薹号}～，其中p。，因此，第疗次

航班的平均排队时间为E(L)=n，名，其中刀为航班数，A为泊松强度【5】。

1．3建立预测精度模型

从宏观上来看，航班进场和离场的过程是随机序

列，满足Markov链，航班到达时间间隔满足Erl和g分布，航班队列是动态Poisson过程‘61。因此，在

胪七的延误概率如图2、图3所示：

由上图可知，航班在状态2和Ⅳ事后时的延误概率均星增长趋势；比较图2、3可知，航班在状态2的延误概率要远远大于在状态Ⅳ七的延误概率。因此，得出以下结论：在航班入场、出场随机队列模型中，

拟f)，矿(f)／l模型中，假设有Ⅳ次航班，则给出M甜kov

链在时刻f状态f的情况下，预测下一状态挣l的C—K方程(一阶微分方程)为；

弓(f)=一五(f)昂(f)+七∥(f)墨(f)fp)=一(2(f)+^弘(，))+^-(，)卑+。(，)

姗

，

鞋

譬留

～

妒，．一

，

只，(f)=兄(‘)只一。(f)一(A(f)+七∥(f))只(f)+七∥(f)曰¨(f)

七≤j≤(Ⅳ一1)七

，

一一

P，(f)=A(f)e一。(f)+七∥(f)(P+．(f)一只(f))(^，一1)

七％(f)=一．j}∥(f)％(f)+名(，)墨。-1)。O)

式中，名(f)指某跑道上待降落或起飞的飞机占机场飞机总量的比例；∥O)指某跑道的当前机场容量指

厘

茁加他：¨￡：m

●一

l

桶箕柑嚣

8642

o

／’

．，’

8．1

8．2

￥

《

妹

／!

8．7

8．8

8．9

8

一斗t8．一8．348．5

8．69

数(拥挤或延误时跑道容量／正常情况下跑道容量)【6】；

只(f)是在时刻f状态f的情况下的概率。

该模型共有(Ⅳ七+1)种状态，每种状态表示当前

选取的时间段(8：OO一9：00)

图2∥=15，Ⅳ=3航班在状态3的延误概率

Fjg．2

FIight

hen∥=15，deIayprobaIityw

ca8e

Ⅳ=3

at

3

交通运输工程与信息学报20lO年第4期

20

，

瓣

肇宅留～厦苔‘-怕篓柑蕊接

●

i

璧-s

譬留

!

j

童10

譬伯5

J

一手一●

甚

葵

惮

．，

一Z

球

S

一≯’

3．1

8．2

8．3

8．4

8．5

8．6

8．7

8．8

8．9

9

曩。

碟

一58

8．1

8．2

8．3

8．4

8．5

8．6

8．7

．一一

8．88．99

选取的时间段(8：oo-9：00)

选取的时间段(8：Oo-9：00)

图3∥=15。Ⅳ=3航班在状态脾膏的延误概率

Fjg．3

FIight

deIayprobal

itywhenⅣ=15，Ⅳ=3

at

图4∥=25，Ⅳ=3航班在脾七的延误概率

Fig．4

FI

ightdelayprobal

henⅣ=25，Ⅳ=3ityw

at

ca8e／捧膏case／¨c七

由初始状态概率风(o)=l，只(o)=o'f>0，预测未来某一状态的延误概率，随着时间的增加，在Ⅳ

七步状态

3结束语

本文针对当前机场调度的实际情况及机场航班

转移后，概率变小，即航班延误的概率大大减小。在此基础上，将该跑道上的航空器数量增加至25(Ⅳ=25)，接受调度的航班架次占机场飞机总量的比例五为O．08，该跑道的容量指数∥为0．85。在matlab中仿真，通过迭代解C—K方程，得到在状态Ⅳ延误概率如图4所示。

比较图3、图4可知，在两种情况下，延误概率的趋势相似，但Ⅳ=25时，延误概率要小。由此得出以下结论；在航班入场出场队列模型中，在延误概率许可范围内，适量增加航班数量，可提高跑道容量利用率。参考文献

【l】

排序理论基础，采用M盯kov链的C—K方程理论建

立机场服务队列模型，对航班延误情况进行预测。在状态相等的情况下，随着状态转移步数的增加，

七的延误概率大大减小。在延误概率允许的范围内，增

加状态数，即航班数增加，可提高机场跑道利用率。该模型是随机队列模型，预测过程较为简单，但足以评估当前空管情况中航班入场出场的时间延误。下一步，通过延误概率去制定航班调度策略，是一个较好的办法。

王海东，孙淑光．基于模糊佩特里网的航班进离港调度p】．天津：中国民航大学，2007．

下的指路通行能力研究们．东南大学学报，1998，

28(3)：99-101．

【6】

【2】李志荣。张兆宁．基于蚁群算法的航班着陆排序【J1．交通运输工程与信息学报，2006，6(2)：66—69．

姚宴斌，高金华．机场轨道交通陆侧交通分流情况的预测研究【J】．华东交通大学学报，

23(1)：49-51．

2006，

【3】

陶

冶，白存儒．基于遗传算法的航班动态排序

【7】

模型的研究阴．中国民航飞行学院学报，2005，

8(16)：5-7．

H锄senM盯k．Nikoleris1乱的s

Uscof

qucueing

andLovellDavid．

mOdels

to

estimatedelaysaving

Eigh廿lRese盯ch

【4】田

铮，秦超英．随机过程及应用嗍．北京：科

f-rom

Europe

4D仃旬ecto巧

Air

precision【C】．

US刖

觚d

学出版社，2007：72一161．

【5】

T仡伍c

Manag哪em

常玉林，王炜，曹洪．主车流服从ErI觚g分布

D钾clopm锄tSemin弛USA，2009．

(中文编辑：吴继屏)