基于最邻近算法的机场特种车辆调度应用研究

殷 龙，衡红军

(中国民航大学 计算机科学与技术学院，天津 300300)

基于最邻近算法的机场特种车辆调度应用研究

殷 龙，衡红军

(中国民航大学 计算机科学与技术学院，天津 300300)

航班在机场过站期间需要接受清洁、配餐、加水、燃油加注、装卸行李货物等一系列地面保障服务。这些服务主要通过一些不同类型的特种车辆(如清洁车、配餐车、加油车、行李车等)来完成。车辆的优化调度对提高航班正点率和资源利用率至关重要。目前我国民航机场对特种车辆的调度大都是依靠人工调度，单车单航班服务。这种低效率调度方式的车辆利用率不高，并且也是造成航班延误的重要因素。为保证航班正点运行，机场特种车辆必须高效完成地面保障服务任务。文中以燃油加注服务为研究对象，首先根据机场燃油加注服务的业务构建了带时间窗约束的特种车辆调度的数学模型；然后研究利用最邻近算法实现对模型的求解，并以国内某机场某天的实际数据为例，验证了模型求解算法在该问题上的有效性；最后得出了最优的燃油加注任务分配结果。实验结果表明，利用该算法调度特种车辆可大幅降低服务成本。

车辆路径问题；最邻近算法；时间窗；车辆调度；机场特种车辆

Key works:Vehicle Routing Problem (VRP);nearest neighbors algorithm;time window;vehicle scheduling;airport special vehicle

0 引 言

航班正点率、航空安全、航班延误处理机制、航班的载运率等是衡量民航运输质量的重要指标[1]。其中人为可控的对民航服务质量影响最大的一项为航班的正点率。随着日益增长的航空运输需求，航班延误现象变得越来越普遍，导致航班正点率降低。而机场调度是机场管理的核心组成部分，因此，优化地面服务车辆调度对于提高航空运输服务质量和保障航班正点率极为重要。

机场特种车辆调度问题[2]实质上是一种帯时间窗约束的车辆路径优化问题[3-5](Vehicle Routing Problems with Time Windows，VRPTW)。每个航班都有接受机场提供的地面保障服务的需求。机场地面保障部门需要组织合理的行车路线，使得每个航班的需求得到满足，并能在一定的约束(车辆续驶路程、车辆载运量、航班时间窗等等)下，达到路程最短、所需车辆最少、耗费时间最少等目的[6]。

文中以燃油加注服务为研究对象，首先，根据机场燃油加注服务的业务构建了特种车辆调度的数学模型；然后，利用最邻近算法实现对模型的求解，并以国内某机场某天的实际数据为例，验证了模型求解算法在该问题上的有效性。该方法同样适用于配餐、加注清水等其他地面保障服务的特种车辆调度。

1 问题描述和数学模型

1.1 问题描述及条件假设

随着航空交通运输业的日益发展，增大了机场对航班地勤服务的需求。从地勤服务车辆调度问题中的车辆角度来考虑，由于车辆需要对航班进行服务资源的配送，有关车辆的一些约束需要被考虑，如部分服务车辆的容量限制、航班对服务资源的需求量以及对服务时间的要求等。鉴于此,尝试用VRPTW[7-9]的建模方法来描述该实际情况：某机场车辆调度中心向n个航班提供特种服务(配餐、加油、加水等)，第i个航班货物需求量为gi，车辆到达航班i的停机位时刻为si，最早允许特种车辆服务的时间为ai，最迟服务时间为bi，车辆在航班i的服务时间为ti，车辆在航班j的服务时间为tj，车辆由航班i的停机位行驶到航班j的停机位时间为tij，到达航班j的停机位时刻为sj，提前到达航班j的时间为Δaj，延迟到达航班j的时间为Δbj，车场与停机位、停机坪之间的运输费用为cij，车辆车载容量为Q(Q>gi)，即车辆不允许超过自身最大载重量且必须在时间窗内服务航班。评价值为M,即选择下一节点时务必使得M尽可能小。要求合理指派特种车辆，并确定每台车的服务路线，使得总服务费用Z及航班延误率最低[10]。

问题条件假设：

(1)调度问题是静态的，即所有任务事先给定；

(2)所有运输车辆在任何时刻一辆车上至多只能服务一个航班，该任务从车场(原点)作为起点直至相应到达停机坪；

(3)任务的时间窗应该被严格执行,即为硬时间窗；

(4)车辆服务路线必须是封闭的,即每辆车在执行完一条调度路线后必须再回到原来所在的位置(车场)。

变量定义：

1.2 模型构建

带有时间窗约束的特种车辆机场调度模型如下：

目标函数为：

(1)

评价函数为：

M=w1*tij+w2*Δaj+w3*Δbj

w1+w2+w3=1

(2)

约束条件为：

(3)

(4)

(5)

(6)

(7)

Xijk=1→Si+ti+tij=Sj

(8)

Xijk=0(或i,j=0,1,…,m)

(9)

模型中，式(1)为目标函数，它的含义随着目标的变化而变化，可以为费用、距离等，一般根据该模型的实际应用来确定，Z表示总服务费用；式(2)表示选择下一节点时的评价系数，即使得评价系数M最小；式(3)表示车辆k服务的任务之和应小于车辆的载重量，即绝对不允许超载；式(4)表示航班i只能由特定的某辆车来提供相应服务；式(5)表示对所有的点进行服务需从配送中心(车场)派出m辆车；式(6)表示该任务点必定只有某辆车来提供相应服务，且也必有该辆车从另一点来提供服务；式(7)表示任务点必定由某1车辆来提供服务且必须去向另一点；式(8)表示从停机坪i到停机坪j所需的时间；式(9)表示变量的取值约束。

2 最邻近算法原理及算法设计

2.1 算法的基本原理

最邻近法最早由Rosenkrantz和Stearns等于1977年提出，与Dijkstra算法和Floyd算法一并用于求解物资配送最短路径问题[11-12]。该算法基本原理描述如下：从配送中心(或车场、原点)出发寻找与其评价值最小的且为未访问的节点作为第一个节点，同时将其设置为已访问。然后以该节点为起点进行搜索，找出与之相邻的、评价值最小的、未访问的节点，检查是否满足约束条件，即加上该节点该环路上的货物量之和不会超出车辆的最大载重量。该点符合时间窗约束(详细判断条件如下)，则将点加入到线路中并将该节点设为已访问，否则结束该条线路。以刚加入的点作为搜索的起点继续遍历，直到找不到未访问的、相邻的节点为止，此时结束该条路线，回到配送中心(车场)。重复以上步骤，直到所有节点全被访问，则算法结束。

时间窗约束判断条件为：

Sj=Si+Ti+Tij

显然：

当车辆延迟到达服务点j时，说明航班会延误，此时将点j从当前路径中删除，剩余节点构成一条服务路径，并再次从初始点出发寻找下一条路径。

2.2 算法的实现步骤

具体步骤如下：

第一步：拟定配送中心(车场或原点)，计算任意节点到该中心的距离，生成距离矩阵。

第二步：从该距离矩阵中取出离配送中心最近的未访问节点vk，将该节点设为已访问，形成一个往返式的子回路。

第三步：以该节点为中心进行搜索，找出与之相邻的、未访问的节点，检查是否满足以下条件：

(1)该节点未访问。

(2)计算子回路和vk的总货运量Q，若Q≤qi，则继续第四步，否则转到第一步，寻找新的一条回路。

(3)sk∈[ak,bk]，即到达新任务点的时间在时间窗内，则继续第四步，否则转到第一步，寻找新的一条回路。

第四步：将节点vk插入到子回路中，即将两条新弧(i,k),(k,j)代替原来的(i,j)，同时将该节点设为已访问，并重新计算车辆到达各项任务的时间。

第五步：跳转到第二步，检查所有节点直到所有节点都加入到某一子回路中。

3 算例分析

文中采用国内某机场的航班数据做算例，实现对机场加油车的调度，验证该算法的有效性。

3.1 数据采集

该机场拥有客机停机位63个，每天进离港航班大约300架次。规定飞机加油车行驶速度为20 km/h，加油车最大行驶路程为50 km[13]。由于加油车一定会对离港航班进行加油服务，文中只选取该机场2014年8月31日00:00:00到2014年9月1日00:00:00之间的实际数据，该天共有航班147个，实验要解决机场加油车辆调度问题。

3.1.1 机型大小

由于不同类型飞机所需加油量和加油服务时间不同，所以必须对飞机进行分类，大概分为三类：小型飞机、中型飞机、大型飞机。不同类型飞机的加油需求量和服务时间见表1。

表1 不同类型飞机的加油需求量和服务时间

3.1.2 停机位距离

与普通物流车辆调度相比，机场加油车调度具有特殊性，主要表现在车辆行驶路径上。在机场，地勤车辆必须按照规定路径行驶，不得进入飞机行驶区域。

该机场现有63个客机停机位，根据其邻接关系，编号依次为：409、410、411、412、413、414、415、416、417、418、419、101、102、103、104、105、106、107、108、109、501、502、503、504、110、111、112、113、114、115、116、117、118、201、202、203、204、205、206、207、208、209、210、211、212、213、214、215、216、217、218、219、220、221、222、223、224、225、226、227、228、229、230，其中加油车车场位于停机位109和停机位501之间，其邻接关系由其位置决定，相邻停机位之间距离大约40 m。表2列出了车场(编号：D)和其中8个停机位任意两点之间的距离(单位：m)。

表2 车场和其中8个停机位任意两点之间的距离

3.1.3 离港航班时间窗

时间窗即由服务车辆开始为该航班服务的最早开始服务时间(或称时间窗下限，单位：时刻)和最晚开始服务时间(或称时间窗上限，单位：时刻)限制的时间范围。服务车辆必须在这个时间范围内开始为该航班服务，否则可能导致航班延误。

民航局规定：加油车应在旅客开始登机前5 min完成加油服务，载客加油或特殊情况下加油应在预计离港时间前5 min完成。即加油车必须至少在预计离港时间前5 min完成加油服务[10]。

下面根据该机场的计划离港时间数据，确定其时间窗下限和时间窗上限。

参数定义：ai为时间窗下限；bi为时间窗上限；td为计划离港时间；Ti为加油车服务时间。

离港航班时间窗：

ai=bi-15

bi=td-Ti-35

部分离港航班时间窗见表3。实际处理时间参数时，均将24进制转化为10进制，单位为min。

表3 离港航班时间窗(部分)

3.2 结果分析

通过Java编程实现文中算法，并将其应用于该机场加油车调度问题，得出了147个离港航班接受加油车服务的开始时间、结束时间及每辆加油车的路径安排方案。

3.2.1 航班接受加油服务的时间段

文中算法采用硬时间窗约束，对提前或延迟到达服务机位的加油车采用比重系数加入到对最短路径选择中，最后得出调度结果中开始服务时间均在时间窗内，加油车不会造成航班延误。以航班为对象，表4列出部分航班接受加油服务的时间段(单位：时刻)。

表4 离港航班接受加油服务时间段(部分)

3.2.2 加油车任务分配结果

以加油车为对象，为每一辆车分配加油任务。先不考虑任务均衡性，即分配任务时不对每辆加油车加任务量λ约束。由于路径调度分配受评价系数的影响，经过测试不同系数的比重，得出了最优的系数分配方案。表5列出了不考虑任务均衡性时加油车的路径调度方案。

表5 不考虑任务均衡性时加油车的路径调度方案

从表中可以看出，最优的排班结果中，车辆行驶总距离为60 960m，加油车等待航班的总时间为1 000min左右，没有延误时间，而传统单车单航班服务方式，则需要147个车次，总的行驶距离达到8万多米。

通过以上加油任务分配并结合各自路径的服务时间可得出，完成所有航班加油任务仅需7辆加油车，极大节省了加油车资源。

4 结束语

文中将机场加油车调度问题建立数学模型，利用最邻近算法结合时间窗约束算出使总路程最短的路径集合，将所有航班任务合理分配给加油车。采用硬时间窗约束，只允许等待，不允许延误，使每个航班尽可能在规定时间内得到加油服务。最终，文中方案能成功应用在机场加油车调度问题上。

对于实际问题，该方案也有其局限性。例如，如果航班受天气、其他地勤服务等因素影响做出动态调整，加油车调度方案也应及时做出调整。而文中给出的只是一个静态调度方案，后期需对动态调度做进一步研究[14]。

[1] 黄建伟.民航地勤服务[M].北京:旅游教育出版社，2007.

[2] 樊琳琳.大型机场地勤服务中的车辆调度问题的初步研究[D].沈阳:东北大学，2009.

[3]DantzigG,RamserJ.Thetruckdispatchingproblem[J].ManagementScience,1959,6:80-91.

[4] 郎茂祥．物流配送车辆调度问题的模型和算法研究[D].北京:北京交通大学,2002.

[5] 方金城,张岐山.物流配送车辆路径问题(VRP)算法综述[J].沈阳工程学院学报：自然科学版,2006,2(4):357-360.

[6] 龚 涛,刘 山,何永明.民航过站飞机的地面作业调度算法研究[J].中国民航学院学报,2002,20:15-16.

[7] 杨燕霞,伍岳庆,姚 宇,等.带时间窗车辆调度问题的启发式算法研究与应用[J].计算机应用,2013,33(A01):59-61.

[8]DesrochersM,DesrosiersJ,SolomonM.Anewoptimizationalgorithmforthevehicleroutingproblemwithtimewindows[J].OperationsResearch,1992,40(2):342-354.

[9]KallehaugeB,LarsenJ,MadsenOBG,etal.Vehicleroutingproblemwithtimewindows[M].US:Springer,2005.

[10] 李 军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社，2003．

[11] 李坤颖,杨 扬,侯凌霞.应急物流配送优化的改进最邻近算法研究[J].交通信息与安全,2011,29(3):40-42.

[12] 李 军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程,1996,14(5):45-50.

[13] 中国民用航空局.民航发[2013]83号,航空公司航班正常运行标准(试行)[S].北京:民航局综合司,2013.

[14]GhannadpourSF,NooriS,Tavakkoli-MoghaddamR,etal.Amulti-objectivedynamicvehicleroutingproblemwithfuzzytimewindowsmodel,solutionandapplication[J].AppliedSoftComputing,2014,14(1):504-527.

Research on Application of Airport Special Vehicles Scheduling Based on Nearest Neighbors Algorithm

YIN Long，HENG Hong-jun

(College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

During the flight over the airport station,it will be in need of a series of ground support service such as cleaning,catering,water adding,refueling,cargo loading and unloading,which is finished with up some kind of different types of vehicles such as cleaning cars,catering trucks,fuel trucks,luaggage cars,etc.Optimal scheduling is of great importance in improving the punctuality rate and resources utilization for flight.At present,most of scheduling of the airport in China to the special vehicle is manual,single vehicle with single flight service.This inefficient approach makes the low usage of the vehicle,thus it becomes one of the important factor of the delaying for a flight.In order to ensure the punctuality of the flight,airport special vehicles must finish the ground support service efficiently.Putting refueling service as the object,first of all,a mathematical model with time window constraints according to the business of the airport refueling service is built in this paper.After that,the research of using the nearest neighbor algorithm on the solution of the model is given,and taking the actual flight data of a domestic airport as an example,the model is verified the effectiveness on the issue.At last,the optimum fuel filler task allocation result is obtained.Experimental results show that the algorithm can greatly reduce the service cost for special scheduling vehicles.

2015-11-03

2016-03-03

时间：2016-06-22

国家自然科学基金资助项目(U1333109);国家级大学生创新创业训练项目(201510059014)

殷 龙(1991-)，男，研究方向为计算机软件开发、构造启发式算法;衡红军，博士，副教授，研究方向为智能信息处理、机器学习、民航信息系统。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.044.html

TP249

A

1673-629X(2016)07-0151-05

10.3969/j.issn.1673-629X.2016.07.032