大型机场地面服务车辆调度问题的研究

摘要：本文主要研究了我国影响飞机准点率的因素，通过研究发现提高机场地面服务车辆调度效率可提高飞机准点率，保证民航运输效率。通过分析时间窗因素、地面服务车辆类型、地面服务流程等对地面服务车辆调度的影响，建立了适用于解决机场地面服务车辆调度问题的模型。通过研究解决此问题的两种经典启发式算法，寻找提高算法运行效率的方法。

关键词：地面服务车辆；时间窗；车辆路径问题；CW节约算法；邻域搜索算法

1概述

随着我国经济的发展，飞机成为人们重要的交通工具之一。每年我国大型枢纽机场吞吐量都在不断增加。2019—2023年我国民航运输旅客吞吐量、货邮吞吐量、飞机起降次数如表1所示。从表1中可以看出，2023年起，我国民航运输市场正在逐步恢复，其中旅客吞吐量、货邮吞吐量、飞机起降次数较上一年分别增长142.2%、15.8%、63.7%，旅客吞吐量和货邮吞吐量基本恢复到2019年的标准。但与此同时航班延误也频繁出现，据统计造成航班延误的原因之一是机场调度问题。

据研究发现，航空旅客投诉的重要原因是航班不正常服务，而航班延误的主要原因一般分为内在和外在两个因素。外在因素主要有恶劣天气影响、空中交通管制、恶劣的航空安全状况等。内在因素涉及航班机械维护、地面特种车辆调度效率等。从表2可以看出，2019—2023年影响航班不正常的原因除了天气原因、空管原因这些外在因素以外，最重要的一项因素来自航空公司和机场方面，其中一项为低效率的地面服务车辆。

航班在降落之前和起飞以后，需要接受各种地面服务，如燃油加注、乘客摆渡、货物运输等，这些服务需要清洁车、摆渡车、加油车等地面服务车辆协调完成，若其中任一环节设计不合理都可能导致航班延误、资源浪费、降低服务质量。因此为了提升民航业的服务质量，研究机场地面特种车辆的调度，找到影响特种车辆低效的原因，对保证航班的正常执行，提高航班运行效率，提升国民幸福度，改善航班延误现状具有非常重要的意义。

2影响因素分析

在航空运输中，飞机每进行一次航空飞行任务，都需要在机场进行一系列的生产和地面准备工作，这称为航班过站行为。而飞机在航班过站期间，进行的各种地面服务保障工作就是航班过站的地面服务。根据我国居民出行的主要特点并结合数据发现，我国各地大型枢纽机场的航班在一定时间内的起降存在高峰期，这种情况会导致航班到达波和离港波的出现，而航班的延误具有网络传播效应，从而导致航班延误的加剧。为了研究机场地面服务车辆调度问题，首先分析影响其调度效率的因素。

2.1考虑时间窗的影响

由于航班的抵港和起飞都需要按照航班时刻表进行，因此对地面服务车辆的服务时间有时间窗限制。首先，在航班不延误的前提下，地面服务车辆的服务时间需要严格控制航班时刻表里航班抵港至起飞时间段内，这属于硬时间窗问题。其次，航班有可能提前到达或者延迟离开，地面服务也允许在航班时刻表规定的时间外进行，属于软时间窗问题。此时在建立模型时，需要增加一个惩罚成本。

2.2考虑地面服务类型的影响

航班过站时，接受的地面服务大致可分为三类，分别是对飞机客舱、飞机外舱以及飞机外部进行后勤工作。而飞机接受的地面服务并不是全部都需要地面服务车辆设备来完成，其中飞机的加油、加水、电源车靠机作业、拖车作业等，这些服务需要地面服务车辆才能完成工作。而有的服务只需要地勤人员自己即可完成，如引导乘客下机、上机回收餐车、值机人员送舱单等服务。因此，本文在后续过程中，在不影响各环节顺序的基础上，将各流程进行简化，仅考虑需要地面服务车辆调度的环节进行研究。

从地面服务车辆种类分析，主要可将其分为两类，第一类是运输资源的车辆，如垃圾车、污水车、食品车等，此类地面服务车辆具有一定的容量限制，车辆必须将资源运输到停机坪才能保证工作的完成，并且车辆能够提供的资源不能超过其运载的上界。另一类是不涉及资源运输的车辆，如牵引拖车、升降车、管线加油车等，此类车辆的作业不受车辆运载容量上界所限制。

2.3考虑地面服务流程的影响

根据我国常用民用机型对地面服务项目的需求情况，航班过站时需要有地面服务车辆参与的地面服务项目有：（A）飞机到位，机务放轮挡；（B）清洁队清洁客舱；（C）食品公司上机回收餐车并装食品；（D）平台车或传送带靠舱门，卸行李；（E）卸货；（F）装货；（G）装行李；（H）油料公司油车到位加油；（I）电源车靠机作业；（J）污水车、垃圾车、加水车靠机作业；（K）关舱门，拖车拖出飞机。

根据各地面服务项目之间的关系，流程（B）（C）为围绕飞机客舱展开的工作，并且清洁客舱和回收餐车的工作可以同时进行。流程（D）（E）（F）（G）为围绕飞机外舱展开的作业，由于各项工作存在先后顺序，因此不能同时进行。流程（H）（I）（J）是围绕飞机外部进行各种地面作业，各项服务相互独立，因此不能同时进行。三大种类的服务相互独立，因此可以并行作业。

3问题描述和模型建立

结合地面服务车辆调度问题的影响因素，将机场地面服务车辆调度问题进行简化，最终可将其归结为带有时间窗的车辆路径问题（VRPTW）。在不考虑不同类型地面服务车辆对问题的影响下，设有同样车辆的车队V、一组客户C和一个有向图G，图由|C|+2个顶点组成，其中客户记为1，2，…，n，仓库由顶点0（“驶出仓库”）和n+1（“返回仓库”）表示。顶点的集合记为N=0，1，2，…，n+1。集合弧A表示仓库和顾客之间以及顾客之间的连接。没有弧止于顶点0，也没有弧起源于顶点n+1。对于每条弧线（i，j），其中i≠j，关联一个成本cij和一个时间tij，其中可能包括在顾客i处的服务时间。每辆车有一个容量q，每个顾客i有一个需求di.每个顾客i都有一个时间窗口ai，bi。车辆必须在bi之前到达客户，它可以在ai之前到达，但客户不会在此之前得到服务。仓库也有一个时间窗口a0，b0（假设仓库的时间窗口是相同的），a0，b0称为调度视界，车辆不得在a0之前离开仓库，必须在bn+1或者之前返回。

假设q，ai，bi，di，cij为非负整数，而tij为正整数，cij和tij都满足三角不等式。

定义两组决策变量x和s对每条弧（i，j），其中i≠j，i≠n+1，j≠0，对每辆汽车k定义：

xijk=0，如果车辆k不从点i驶向点j；

1，如果车辆k从点i驶向点j。

sik为某个顶点i和每个车辆k的决策变量，表示车辆k开始为客户i服务的时间，如果给定车辆k不为客户i服务，sik没有任何意义。并且假设a0=0，因此对于所有k，s0k=0。

为了使模型符合实际情况还应有如下假设：（1）对每辆服务车辆来说，每个顾客只得到一次服务；（2）每条服务路线都从顶点0出发，在顶点n+1结束；（3）时间窗和容量约束可以被观察。现在以车辆运行路线成本最小作为目标函数建立模型：

min∑k∈V∑i∈N∑j∈Ncijxijk（1）

∑k∈V∑j∈Nxijk=1i∈C（2）

∑i∈Cdi∑j∈Nxijk≤qk∈V（3）

∑j∈Nx0jk=1k∈V（4）

s.t.∑i∈Nxihk-∑j∈Nxhjk=0h∈C，k∈V（5）

∑i∈Nxi，n+1，k=1k∈V（6）

sik+tij-K（1-xijk）≤sjki，j∈N，k∈V（7）

ai≤sik≤bii∈N，k∈V（8）

xijk∈0，1i，j∈N，k∈V（9）

其中，约束式（2）表示每个顾客仅被访问一次。式（3）表示没有车辆装载超过其容量允许的货物。式（4）、式（5）、式（6）确保每辆车离开0号仓库，在顾客到达后再次离开，最终到达n+1号仓库。式（7）表明如果车辆k从i行驶到j，则不可能在sik+tij之前到达j，这里K是一个大标量。式（8）表示汽车为顾客i服务的时间必须在时间窗内。式（9）是完整性约束。该模型通过设置参数可转化为其他模型，当ai=0，bi取值很大时，问题退化为车辆路径问题（VRP）；当V中只含一个元素时，问题退化为旅行商问题（TSP）。

4求解算法分析

有时间窗的车辆路径问题已经被证明是NP难的，因此更多的是在研究解决此问题的启发式算法，常用的有经典的启发式算法和智能启发式算法，常用的智能启发式算法有遗传算法、蚁群算法、模拟退火算法等。下面介绍求解此问题的两类经典启发式算法。

4.1CW节约算法

该算法最开始是为解决有条件的车辆路径问题（CVRP）提出，而该算法在可行性的基础上具有运行速度快、简单、易于调整的特点，使得此方法在最初研究启发式算法解决此类问题时，被广泛使用。此方法采用将可行子路线进行合并的方法建立节约标准，即通过合并两条路线使用一辆车，而不是两辆车的方式来节约成本。现以一个仓库、两个顾客为例，节约算法的基本思想如下：设O为仓库，y和z是两个需要服务的顾客，将任意两点间的距离定义为dij（i=O，y，z；j=O，y，z），车辆从仓库O出发，服务两个顾客存在两种方案。第一种方案由一辆车完成整个服务过程，车辆从仓库O出发，依次服务顾客y、z，最后返回仓库，车辆行驶的总路程为D1=dOy+dyz+dzO；第二种方案是由两辆车分别从仓库出发，单独服务顾客y和z，最后返回仓库，此方案车辆行驶的总路程为D2=2dOy+2dzO。如果方案一车辆行驶的总路程小于方案二行驶的总路程，节省的距离为：

Sij=dOy+dzO-dyz。

将其定义为y、z两顾客间的节省函数。

考虑外部因素的影响，可将节省函数进行优化，引入节省函数：

Sij=dOy+dzO-λdyz+μdOy-dzO+vcy+czc-。

其中λ是为了避免顾客分布导致原始CW算法构建从最外面顾客开始，向内部顾客前进的圆形路线的缺点，通过引入正参数λ来帮助重塑路线。公式的第二项是为了收集更多关于顾客的分布的信息，利用顾客y、z之间关于他们到仓库距离不对称信息，引入的一个正常数μ。而第三项是为了考虑顾客的需求以及总体平均需求，将需求较大顾客提供优先级。其中cy（cz）表示顾客y（z）的需求，c-表示平均需求，v是非负参数。由于CW节约算法并没有考虑时间窗对问题的影响，因此在实际的使用过程中需要加入时间窗等约束条件。

4.2邻域搜索算法

邻域搜索算法最初是为了解决VRP问题提出，在给出初始解后，主要通过破坏算子破坏当前解的一部分，即从可行解变成不可行解，再由修复算子对被破坏的解进行重建，重新变成可行解的过程。而邻域是一种与破坏算子和修复算子有关的隐式定义。由于邻域的定义影响了算法的复杂度，一般情况下，邻域选择越大，得到局部最优解越好，从而得到全局最优解就越好。但邻域选择越大，每次迭代搜索所需要的时间也越长，因此邻域的选择非常重要。邻域搜索算法的基本步骤为：

（1）设初始解为路径σc=c1，c2，…，cn，其中ci∈C，cn为当前路径最后服务的客户。

（2）定义两个客户的相关性函数：R（i，j）=1cij+Vij，其中cij是从i到达j的成本，并且将所有的cij都在0，1范围内归一化；如果顾客i和j由不同车辆服务，并且减少车辆数量在成本函数中很重要，则Vij的计算结果为1，否则，计算结果为0。

（3）移除过程。将相关性大的顾客依次从σc移除放入集合S中，直至满足假设条件，并定义从σc中移走集合S后，剩余的部分解为σ*。

（4）插入过程。将移走的数据集S依次重新插入部分解σ*中，直至数据集S里的元素全都插入部分解σ*，此过程生成许多待定解。

（5）将新生成的解与初始解进行比较，比较其运行路线成本，决定是否接受新生成的解。

（6）更新当前解及相关参数，重复迭代过程，设置终止条件，结束搜索时即可返回问题的最优解或近似最优解。

结语

CW节约算法和邻域搜索算法都是解决VRPTW问题的重要经典启发式算法。其中CW节约算法影响算法效率的主要因素有：节省函数Sij函数的选择及参数设置；如何将时间窗因素加入CW节约算法模型中进行求解。而邻域搜索算法首先需要考虑初值的选取方式，用此方法求解问题初始解可随机给出，也可通过节约算法给出初始解。在于移除过程，相关函数的定义会影响移除的解的顺序，插入过程采取的算法也会影响算法的复杂度。因此，优化移除过程和插入过程的算法，对提高算法效率有重要意义。

参考文献：

［1］DantzigGB，RamserJH.TheTruckDispatchingProblem［J］.ManagementScience，1959，6（1）：8091.

［2］ShawP.UsingConstraintProgrammingandLocalSearchMethodstoSolveVehicleRoutingProblems［J］.PrinciplesandPracticeofConstraintProgrammingCP98，1999：417431.

［3］刘小兰，郝志峰，汪国强，等.有时间窗的车辆路径问题的近似算法研究［J］.计算机集成制造系统，2004，010（007）：825831.

［4］LarsenJ.ParallelizationoftheVehicleRoutingProblemwithTimeWindows［J］.Ph.d.thesisImmTechnicalUniversityofDenmark，2004：1145.

［5］RopkeS，PisingerD.AnAdaptiveLargeNeighborhoodSearchHeuristicforthePickupandDeliveryProblemwithTimeWindows［J］.TransportationScience，2006，40（4）：393546.

［6］衡红军，晏晓东.实现多目标优化的机场特种车辆调度算法［J］.计算机应用与软件，2016，33（010）：238242.

［7］DoyuranT，CatayB.ArobustenhancementtotheClarkeWrightsavingsalgorithm［J］.JournaloftheOperationalResearchSociety，2011，62（1）：223231.

基金项目：校级青年基金项目（QJ2022106）资助

作者简介：江婧（1995—），女，汉族，四川眉山人，硕士研究生，讲师，主要研究最优化理论及算法。