2023年7月29日发(作者：)

第42卷第3期

太原科技大学学报

Vol.

42

No.

3Jun.

42272227

年

6

%

JOURNAL

OF

TAIYUAN

UNIVERSITY

OF

SCIENCE

AND

TECHNOLOGY

文章编号：1773

-2257（2221）23

-2246

-27机场登机口分配问题的顶点着色模型与算法梁超超，陈培军（太原科技大学应用科学学院，太原230224）摘要：对航班-保机口分配问题进行研究，将其看成顶点着色问题进行求解，设计了简单有效的可

以应用于具有卫星厅的登机口分配的贪婪算法策略。将按照“先到先服务”的原则，依次运用启发式规

则为当前航班选择登机口，即优先使用可供航班类型种类数量少的登机口，并选择已空闲时间最长的登

机口。这样有助于减少使用可供多种类型航班使用的登机口的数量，有助于将这些登机口分配给数量

较多的航班类型使用。同时，极大的增加了分配的鲁棒性，有益于处理飞机不可避免的短时间的延误。

最后将&算法应用于上海浦东国际机场67个登机口优化安排343个航班的问题中，对算法的有效性进

行验证和分析。关键词:航班-保机口分配;顶点着色；贪婪算法中图分类号：O221

文献标志码：A

doi：10.3969/.

873

-

2057.2021.03.015随着旅行业快速发展，机场航班日起降架次的

赛题。航班分配问题的任务可理解为在尽可能节

约资源的

增多和乘

人数的

增长,现有的

的考验。

口，给出能够

最多的航班到，可将问题转化资源正面临着越来越

运输管适合的

口的问题。由于

口与机型的约束,理中，机场管理处于重要地位。

管理中，航及

为带约束的

之

位（（

口）分配处于重要地位。针对问题。

的

的主要工作是设口

问题4

口

问题的排序

运用

等提出了一种

，，并采用 口标号

：建J］计了简

应用于具有卫星厅的

口的 算法

。航站楼立标号算法对其进行求解。田晨和熊桂喜通过

算法来求解-登机口分配问题。文军、4］等人提出了一种登机口

问题的图着色

，并通

T

卫星厅S

J當片算法确定

算法。用

口的时I

"［TramLme

------------，根据“先到先服务”的原则建立登机口

的 序列

图1卫星厅S相对于航站楼T示意图Fig.

2

A

sUetch

of sctellite

halt

S

relative

to

terminai

building

T很多现

楼的旅客流量已达饱和状态，为了应

这类问题的

增的运营

，正增设卫星厅。2218年“华为杯”第

研究生数学竞赛F题对提出了研究要求。

楼T1航班分配问题数学模型的建立1.1登机口分配的分析口

星厅S的

设计如图7所示。

楼T有见28个登机口，卫星厅S有47个登机口，具体

收稿日期：208登9登4根据登机口的规格,可将登机口分为国内-国内作者简介:梁超超（1794-（，女，硕士研究生,研究方向为最优化理论及应用；通信作者：陈培军副教授,E-mvi:

pjchen@

tymoehu.

co.第42卷第3期梁超超，等:机场登机口分配问题的顶点着色模型与算法247宽体机、国内-国际宽体机、国际-国内宽体机、国际-

国际宽体机、国内-国内窄体机、国内-国际窄体机、

国际-国内窄体机、国际-国际窄体

8种类型。

S3登机口

指根据航班的

格以及

I时一个具体的登机刻、离开

，为每一

口。

一

的

格、纟

，

于

的也

约

：，或处于

，具体

10O目、飞行类型(国际或者国内)不同，确定口的类

口5000600O使用

用时,必须满

机口只能分配给一

(2)

对于每一

图2

19-22日不同时刻航班的数量Fig.

2

Number

of

tights

aS

different

time

from

19

to

22(7)对于每一个登机口而言，同一时间同一登

状态。口。言，登机口是唯一的，3卩必须给

一个且仅

一

。(3)

航班一旦开始使用

口，则

用过10O5O006000程不能中断，直到使用

(4)

登机口应

匹配，即宽型航班只能使用

口，窄

能使用窄

口。进理论建进

口

，根据已知的航班时刻表，并且按照“先到先服务”的原则

口

立

，这样

图3考虑空档间隔后,19X2日不同时刻航班的数量

Fig.

2

Number

of

flights

aS

different

time

from19

to

22

after

cansineriny

yap

interveis应用有序的

的数学

口

。统一对17日到达22日出发的航班采用虚拟的到达，即比出发时刻提前50

min,另外1.2数据处理以下为数据处理的具体步骤：(7)

不能超过起始时2点，如果位于2点之前，统一将2

点作为虚拟的

号判断并保存所有航班的宽、类

发类。窄类

。(5)

同样，对于22日到达，而较长时间才离开(2)

所

的

，将其

后50

min时间视为其虚拟一

，并

(J中的宽窄将航班分为国内-国

内宽体机、国内-国际宽体机、国际-国内宽体机、国

的出发

，若超过了

24点4卩已超过22日考虑范围，则可视为24点。际-国际宽体机、国内-国内窄体机、国内-国际窄体

机、国际-国内窄体机、国际-国际窄体机共8种

通

骤(4),(5)对24点和2点的特殊处理,

可筛选并保存满足22日到达和22日出发的航班以

及对应原顺序的

类。(3)

将2218年7月19日2点作为起点，计算

。的

(6)

计算并绘制22日不同时刻的航班数以及并绘制5日登2日不同时刻(单位:min

)航班的数，见图2；同时考虑间隔45

mm后,计算并

19考虑空档间隔45

min的

4、图

5.，见图日登2日不同时刻航班的数量，见图39(7)

按照步骤(2)中的8种航班类型统计并绘由图3可得：2：

供使用的登机口

排下所有的

最多为80个，而该机场可69个，因此现

制出22

类型的

，以及考虑口无法空档间隔45

min后22日不同时刻不同类型的航班。图6、图7,

了国内-国内窄体机的

，这

要尽可能多的安排

.，其适的

口

4

口最大化被利用。类型的航班数不在此一一

。(4)

将22日作为起点，由于航班到达时间和出

1.3航班登机口分配的顶点着色模型发时间之差的最小值为5。min

,为处理简单，我们问题在生产调

广泛的应243太原科技大学学报2223

年40图4

20日不同时刻航班的数量Fig.

4

Number

of

gights

ah

different

time

on

the

22th

day706o

5o*

緊4o

官3O崔O612824i/h图5考虑空档间隔后,22日不同时刻航班的数量Fig.

4

Number

of

gights

ah

different

time

on

the

22th

day

after

consinering

the

gap

intervats25*1巒11116

12

18

22t/h图6

20日窄体机国内-国内航班分布Fig.

4

Domestic-Pomestic

00皿

distriVution

ofnarrow

body

aircrog

on

the

22th

day300

5

0

56

12

18

24i/h图7考虑空档间隔45

min,

22日窄体机国内-国内航班分布Fig.

4

ConsiVering

the

distriVution

of

domestic-Pomestic

gights

on

narrow-Pody

11X000

with45-minute

gap

on

tee

22th

day用背景，已被应用于资源分配、货物存储和课表编

排、频率

[00]等问题当中。

-登机口问题看成

问题。首先口分配二元图G(卩,R)，对各航班按照到达时间的

先后顺序依次编号，记为3,2,…,,记卩(G)=

{3,2,-2}，人为

的

矩阵，用

各航班之间的关联情况,即R

=(()”“

,其中：(={3航班i与航班/关联，且i

j・(°,航班

i-

门

，或

i=j(3W

i,j

W

n).当(=6

E —

(的即可分配到同一登机口；当(=(时表示航班i和

的

，即不能

一

口。n表示航班数,题目中n

=

363.用

矩阵，我们可构建航班-登机口分配优化

为：mmae

I

kU

=

1K

满足：(3

)

[

K

12,…，K+1

]是顶点卩的一个划分。(2)航班的类型应

口的类型相匹配，并且

口的

满足一定的

。目标中的“2”

的个数。m表示登机口数,题目中m

=

06.

[

K,K,-,K+1]是图G

m

+ 1航班集KG)的一个划分，是指UK=

=

KG)且K3A

K

=

0(3

W

k,3

w

m

+

3

,且k老Z).划分到集合

K(3

W

k

W

m)中的

矩

及

口

Zc允许的类型决定的，对Vie

e

k(3

w

ie

W

n)，有

(=o

K+1为简易临

位，供

定.口的

靠，且临

位

无限制。2顶点着色模型的贪婪算法设计2.1与一般的顶点着色的不同(3

)按照“先到先服务”的原则，不同的航班根

成一个自然的序

。(2)经典的

算法中对于任意给定的所有顶点的一排列，一般用当前可用的最小色对当前

的

。

问题中，选择启发

则是根据之前

的

的先后顺序来选择

口，选择已

最长的

口，这样大大地增加了分的鲁棒性，并且也有益于处理

的短第42卷第3期梁超超，等:机场登机口分配问题的顶点着色模型与算法249的延误。(3)经典的顶点着色问题，颜色的数目是没有

限制的，而现在由于

的

，不同的

的数一定的

。(M

口的国内/国际、到达/出发、宽体机/窄体机等功能属性将其分为8类。2.2贪婪算法的设计根据上述独有的特点设计贪婪算法求解,具体

步骤为：(7)寻找不同类型的登机口编号及个数，且根

据其功能属性将其分成8种类型4

为8类4

楼的

，每种类型的

口由其数，这样便获得

所允许的个数。(2)

计算

矩阵。(3)

利用贪婪算法求解。按落地时间“先到先服务”原则,依次为

矩阵找到能使用的

口，并选择已

最长的

口。若可供使用的

口已经用完，则安排临

靠

方式。2.3实验结果与分析所需安排航班总数为303个，所能提供的登机

口总数为69个，通

算法可得

-登机口:宽体

排比例为102%,窄体机安排比

例为78.74%,共安排了

249个班次的

，航站楼

T和卫星厅S被使用登机口的平均使用率(登机口

占用时间比率)分别见图8和图9.0.8&0.6、»圧理08S06H-060nmO5

10

15

20

25

30航站楼T的登机口

图8航站楼T的每个登机口的平均使用率Fig.

2

Average

utilization

aS

esch

gate

of terminai

T3改进的顶点着色模型的贪婪算法设计31基于顶点着色方法的改进根据有些登机口可以为多种类型(国际、国内)

的航班服务的特点4

、窄机411农01、>圧O.1腿O.翌O.1協O.O.

0.105

10

15

20

25

30

35

40

45卫星厅S的登机口图9卫星厅S的每个登机口平均使用率Fig.

9

Averaae

utilization

aS

eych

boarbing

gate

of sctellite

halt

S

为国内或国际4

口可供使用的类型数分成三类，即仅供一类使用的,仅供两类使用的，供四类使

用的。从

这些 口(颜色)进一

成8

x

3

=24类，先考虑仅供一种类

用的登机口，然后考虑可供两种类

用的

口，最后考虑

供四种类 用的

口。3.2改进的贪婪算法的设计进的

方法设计

算法求解,具体步骤为：(7)寻找

类型的登机口编号及个数，分成

8种类型，每种类型又分为3类，即只供该类

:

用，可供两种类

用，可供四种类

用。(2

计算

矩

。(3)利用贪婪算法求解。按落地时间“先到先

服务”原则,依次为

矩阵找到能使用的

口。在这些

口中，优先使用只供类型使用的

口(颜色)，然后使用可供两种类

用的登机口，最后使用可供四种类

用的

口，并选择已

最长的

口。若供使用的

口已经用完，则安排临

靠方。3.3实验结果与分析通过上述算法可得到航班-登机口分配结果:宽

体机安排比例为82%,窄体

排比例为80.

H

%,排了

254

-

的

，航站楼T和卫星厅S被

用

口

的平均

用率(

口

用

比率))

图17和图17.改进的算法安排的航班比2.

2的算法安排的航班数多5个，说明改进的

的

算法大大地提高了登机口的用

率。2500.80&>、圧腿®太原科技大学学报2023

年7654321000000H-

0

06

05

04

03

02

01

5o3045航站楼T的登机口卫星厅S的登机口图1

航站楼T的每个登机口的平均使用率图11卫星厅s的每个登机口平均使用率Fig.

10

Aveoje

utilizhtion

ah

etch

gate

of

terminat

TFig.

11

Avaroge

utilizhtion

ah

etch

boarkinggate

of

satehite

halt

S4总结本文提出了可以应用于具有卫星厅的登机口

分配的

算法

。首先按照“先到先服务”的

249个航班。然后我们进一步提出简单有效的启发

式规则，即先使用仅供一种类

口，然后考虑可供两种类

用的登机用的

口，最后使用可供四种类

254

-

用的

口，结果共安排了原则，运用简单的（选择已

最长的 口），大大提高了登机口的使用效率。所提启发

则为当前

选择

口，结果共安排了出的算法简

，可操作性强。参考文献:[1

]文军，孙宏，徐杰，等.基于排序算法的机场停机位分配问题研究[J]

•系统工程,2004(7

)

347

N46i[2

]田晨,熊桂喜.基于遗传算法的机场机位分配策略[J].计算机工程,2045

(3)：186088

+272[3]

[4]

文军，李冰，王清蓉，等.机场停机位分配问题的图着色模型及其算法[J].系统工程理论方法应用,2045(2):136044.肖位枢.图论及其算法[M].北京:航空工业出版社,1993:172076.[5

]

BRELAZ

Di

New

metho/s

to

color

the

vertices

of

a

graph]

J].

Communications

of

the

ACM,

April,

1277,27(0)

：251056.[6]刘志镜，秦荣，朱国伟.实用化计算机辅助课表编排系统的研究与实现[J].西安电子科技大学学报,1994,21(4)

：445051.

[7

]刘根泉，王树禾，肖国龙.频率分配与图的着色[J].电子学报,1994,22(1)

：

Coloring

Model

and

Algorithm

for

Airvort

Flight-Gate

Assignment

ProblemLIANG

Chao-chao,

CHEN

Peigun(School

of

Appliea

Scieaco,Taiynyd

University

of

Scieaco

and

Techdoloap,Taiynyd

030020,

China)Abstrach:

The

flight0bc

assignmeat

pro/lem

is

studipS,which

is

reparheP

as

vehep

00X0111

pro/lem,2nd

a

sim­ple

and

effective

gely

algorithm

steWpy

-

which

can

lp

applieP

to

the

gate

assignmeat

with

satelliip

halt:

is

hp-

sidnea.

In

this

paper,

according

to

the

principlp

of

"fimt

comp,

first

serveS

”，thea

the

heaUs/c

rules

is

applieP

to

use

gates

that

are

aeim/m

for

one,two

and

four

flight

types

W

tum,and

the

gate

with

the

least

11/1111x(

of

^匚—/—

flight

typos

is

prefeced

-

and

select

gates

that

have

baa

idle

for

the

longest

time

further.

This

helps

to

reduce

the

n/mbor

of

gates

that

can

bo

used

for

multiple

typos

of

fliggis

and

helps

to

assign

tho

gate

with

tho

most

n/mbor

of

v-

vaila/lo

flignt

typos

to

tho

more

iliggt

types.

At

tho

same

time,it

yeat-e

increases

tho

ro/ustness

of

allocation,

which

is

beaeficial

to

deal

with

tho

inevita/lo

short

hXvy

of

aircraX.

Finallp,

tho

algorithm

is

applied

to

tho

optimization

of

303

flXhis

at

69

gates

of

SPb/hvi

PuUony

International

AiryoU,

which

proves

that

such

algorithm

is

efficwai.

Key

words

：flight0bv

assignmeat,

vertex

comUn/,gmedy

algorithm