基于时间窗的机场地面保障车辆动态调度

姜伟华, 张文静, 袁琪, 姜雨

(1.南京航空航天大学金城学院, 南京 210000; 2.南京航空航天大学民航学院, 南京 210000)

随着民航运输的快速发展,大型枢纽机场普遍进入超负荷运行状态,机场航班地面保障任务调度作为机场场面运行的关键环节之一,已经逐渐成为制约大型枢纽机场发展的新瓶颈。由于航班地面保障任务涉及多主体利益,天气、流控等不确定性因素,更加大了动态调度难度,面对逐步恢复的航空运输消费量与有限机场资源,亟需对航班地面保障任务进行动态调度研究。

对航班地面保障任务的研究主要以对航班保障资源调度进行合理建模并寻找有效的解决方法为主,近年来主要从模型构建和求解算法两方面进行研究。地面保障资源调度模型构建方面,主要基于带时间窗的车辆路径问题(vehicle routing problem with time window, VRPTW),丁建立等[1]以车辆总使用费用最低为目标,引入混合时间窗的概念,建立动态特种车辆调度模型。Zeng等[2]以车辆行驶路径最短、车辆到达时间和最早服务时间之间的差异最小、车辆使用总数最少为目标建立了车辆调度模型。Gök等[3]以最小化总体延误为目标,然后根据各服务部门工作将车辆分散到航班上,并利用约束规划和混合整数规划求解器求解。李欣[4]分析机场加油车运行模式,以最小化车辆行驶距离,缩短加油车行驶时间与等待时间,任务分配相对均衡为目标建立模型。吴枕[5]根据机场保障车辆实际服务流程,针对不同需求构建了车辆协同与动态调度模型。Bi等[6]则考虑高峰时段摆渡车资源紧张问题,建立多目标车辆调度模型求解。陈程等[7]以总时间成本最小为目标,提出实时需求下的带时间窗移动充电车调度模型。

求解方式可分为精确算法和启发式算法,精确算法主要有:线性规划法[8]、动态规划法[9]和分支定界法[10]等,常见启发式算法有蚁群算法[11]、模拟退火算法[12]、遗传算法[13]、禁忌搜索算法[14]和粒子群算法[15]等。针对机场地面保障资源调度问题的特点,中外有许多学者还基于常见启发式算法进行了改进,或尝试其他算法进行求解。Padrón等[16]提出了一种改进的序列迭代方法减少计算量。朱新平等[17]考虑保障作业持续时间的不确定性,设计了递阶式单亲遗传算法。Guo等[18]提出一种新的基于合作博弈理论的车辆调度遗传算法解决机场行李运输车辆调度问题。Zhao等[19]对比分析发现面向多目标的粒子群算法更加适合对问题求解。郝群茹[20]等针对车辆路径优化问题,在禁忌搜索算法的基础上,设置 4 种邻域变化规则来改进局部搜索。Zampirolli等[21]利用模拟退火算法构建初始解,同时使用迭代局部搜索算法进行改进。Zhang等[22]利用图论对机坪建立拓扑模型并使用改进蚁群算法进行了求解。Zhao等[23]将车辆调度模型转化成网络最大流量问题进行求解。

上述研究主要是基于静态需求来优化机场地面保障车辆的调度,然而在实际运行中,需求可能会受天气和交通流量控制等实时因素的影响而改变。如何考虑到航班到达和离开的不确定性,实现机场地面保障车辆的动态调度,仍然是一个需要解决的关键问题。此外,当前车辆路径问题的研究主要集中在车辆路径优化、总配送成本最小等方向,现将软时间窗限制运用到车辆路径问题中,建立带软时间窗的机场地面保障车辆调度模型,更能反映实际问题。

因此现考虑机场航班延误、提前等情况,针对航班信息的动态变化特点,且需求带有时间窗要求的情形,研究带时间窗的机场地面保障车辆动态调度问题,提出一种双阶段机场地面保障车辆调度模型,并运用双阶段启发式算法进行求解,旨在实现机场地面保障车辆的协同作业与动态调度,为机场航班实际地面保障任务调度提供理论依据和决策支持。

1 问题描述

根据车辆路径问题的定义,结合机场航班地面保障服务工作的特点,要研究的双阶段机场地面保障车辆调度问题可抽象为带时间窗的车辆路径问题(vehicle routing problem with time windows, VRPTW)。针对某一种类型的机场地面保障车辆,将航班抽象为需要被服务的客户,每个i航班作业设置了允许进行作业的时间窗口[ai,bi];各保障车辆若在ai之前抵达该航班所在机位,须等到ai才能为航班进行服务,并且需在bi之前完成服务,同时车场和车辆也有相应的工作时间窗,根据不同作业任务时间窗以及位置分布,车辆调度人员需要在运行安全的前提下,对有限的保障设备或车辆进行调度,最终得到每个车辆进行服务的航班服务顺序及地点,即机场地面保障车辆初始调度。但在实际运行过程中,随着时间的推移,新的需求可能由于延误、机位调动、时间窗变动等情况随机产生,为保证航班正常性,在新的服务时间窗内,需要重新分配另一个车辆为其进行服务,寻找机场地面保障车辆的最佳线路,即机场地面保障车辆动态调度。机场地面保障车辆动态调度示例如图1所示,图1中矩形方框代表保障车辆停车场,实心圆圈代表已服务的航班,空心圆圈代表待服务的航班,三角形代表新增或变更需求的航班,线段则代表相互连接的保障车辆服务路线。

图1 机场地面保障车辆动态调度示例Fig.1 An example of dynamic scheduling of airport ground support vehicles

2 模型构建

考虑航班延误、提前等情况,针对航班信息的动态变化特点,构建双阶段机场地面保障车辆调度模型,双阶段车辆路径规划策略如图2所示。

图2 双阶段车辆路径规划策略Fig.2 Two-stage vehicle routing scheduling strategy

2.1 初始调度模型

2.1.1 模型假设

为简化模型,针对机场地面保障车辆初始调度问题做出以下假设。

(1)有限时段假设。选取一定时间段的地面保障车辆调度问题进行研究,方便研究与建模。

(2)信息完备假设。模型中所需的坐标位置、

资源需求量、行驶距离、行驶速度、车辆类型及容量等信息均可知且完备。

(3)运行规则假设。假设每种车型的车场唯一,车辆必须从原车场出发,并在规定时间内返回车场,计算时所用车辆数量=路径数量。

2.1.2 模型建立

第一阶段为机场地面保障车辆的初始调度。在当天地面保障服务开启后,对计划内的机场地面保障车辆进行路径设计,依据规定的计划进离港时间,得到初始的调度方案。机场地面保障车辆初始调度模型为

(1)

(2)

(3)

(4)

(5)

(6)

sik+ti+hij-M(1-xijk)≤sjk, ∀i,j∈F,k∈V

(7)

ai≤sik+ti≤bi, ∀i∈F,k∈V

(8)

(9)

(10)

(11)

式中:F为航班集合;V为车辆集合;N为等待安排保障作业的航班数量;K为车辆总数;dij为从航班i所到机位行驶到航班j所在机位的距离;qi为航班i所需要的资源量;Q为车辆对资源的最大容量;hij为车辆从航班i机位处行驶至航班j所需要的行驶时间;ti为对航班i机型保障服务所需时间;sik为车辆k对航班i的开始服务时间;M为极大值;ai为航班i的开始接受服务时间;bi为航班i的最迟结束服务时间;xijk为0-1变量,车辆k从航班i行驶到航班j处为1,否则为0;yik为0-1变量,航班i由第k辆车服务为1,否则为0;Zk为0-1变量,第k辆车被使用为1,否则为0。

式(1)、式(2)为目标函数,在保证航班作业正点率的情况下,使用车辆数量最小和车辆行驶总距离最小;式(3)约束表示从车场中心出发的车辆数量不超过机场所拥有的该种类型的车辆总数;式(4)表示每个航班作业任务只能由一辆车进行服务;式(5)表示每个客户都需要被服务;式(6)表示每个车辆运载的资源量不能超过车辆容量;式(7)表示车辆对航班的服务开始时间需在上一航班结束服务并行驶到达之后;式(8)为作业时间窗约束;式(9)和式(10)保证车辆流量守恒;式(11)表示被使用车辆均从原车场出发并返回原车场。

2.2 动态调度模型

2.2.1 模型假设

(1)每一时间段的开始调整时间为上一时间段内最后一个服务任务完成时间。

(2)在时间段开始时刻正在进行服务的车辆的位置,设置其为虚拟车场,但车辆最终均需要回到原车场。

(3)航班停机位信息在每一个时间段更新,在该时间段内不会再更改。

2.2.2 模型建立

第二阶段为动态优化阶段。在实际运行过程中,对于场面较为忙碌的大型机场,多种不确定因素将导致航班信息发生更改,据此所获得的车辆初始调度方案将因为进离港航班信息变化而受到扰动。对于时间窗发生变化的航班,首先检测其是否导致初始规划车辆调度方案违背时间窗、容量等约束,若是,则获取该时间航班服务时间窗和可用车辆信息,对该时间段进行车辆的重新调度,即机场地面保障车辆的动态调度优化过程。机场地面保障车辆动态调度模型为

(12)

(13)

(14)

(15)

(16)

(17)

sik+ti+hij-M(1-xijk)≤sjk, ∀i,j∈Fh,
k∈V

(18)

ai≤sik≤bi, ∀i∈Fh,k∈V

(19)

(20)

(21)

(22)

(23)

(24)

式中:Kt为t=ts时已经派出的保障车辆;Qk为车辆k的剩余载重量;n为已完成服务的航班数量;m为正在进行服务的航班数量;Nh为剩余待接受服务的航班数量;Fn为已完成服务的航班集合;Fh为需要服务的航班集合。

式(12)为目标函数,在保证时间窗约束等前提下,需尽可能减少对原指派计划的变动因此设置目标为最小化因计划调整而增加的行驶距离;式(13)约束表示从车场发出的车辆数不超过机场所拥有的该种类型的车辆总数;式(14)和式(15)表示每个航班作业任务只能被单车进行单次服务;式(16)表示每个客户都需要被服务;式(17)表示每个车辆运载的资源不能超过当前车辆剩余容量;式(18)车辆对航班的服务开始时间需在上一航班结束服务并行驶到达之后;式(19)为作业时间窗约束;式(20)和式(21)保证车辆流量守恒;式(22)表示车辆均从原车场出发并返回原车场;式(23)和式(24)表示虚拟车场只能发出车辆且最终车辆将回到原车场。

3 算法设计

机场地面保障车辆调度问题属于典型的NP-hard问题,本文考虑不同启发式算法的优劣,根据前文构建的双阶段机场地面保障车辆调度模型的特点,设计双阶段启发式算法进行求解。在初始调度阶段,采用局部搜索改进遗传算法,得到车辆初始调度方案;在动态调度阶段,采用基于破坏重建思想[24]的邻域搜索算法进行求解,得到动态再优化的调度方案。主要算法步骤如下。

3.1 改进遗传算法

步骤1染色体编码。采用整数编码方式。

步骤2生成初始群体。随机生成含有若干初始个体的种群。

步骤3适应度函数。采用线性加权法并引入惩罚函数,将时间窗约束与容量约束进行转化,只有违反的约束越少,个体的适应度才更高。

步骤4选择操作。采用应用最广泛的轮盘赌方式。

步骤5交叉与变异。交叉操作采用改进两点交叉的方式。变异操作采用对称变异方法随机选择任意两个对称的基因位置并交换位置。

步骤6局部搜索优化。为加快遗传算法的收敛速度,本文基于大规模邻域搜索算法(large neighborhood search,LNS)中的破坏和修复的思想,在传统遗传算法中加入局部搜索机制,以求获得更高质量的解。

步骤7若达到终止准则,算法终止,否则,回到步骤4。

遗传算法(genetic algorithm, GA)模仿生物淘汰、遗传和进化的规则,有适用问题范围广和较好的全局搜索能力,但通常需要较长时间才能收敛到近似全局最优解。因此本文采用局部搜索改进遗传算法,通过局部搜索可在可行空间的某个局部范围内快速的找到局部最优解,从而加快收敛速度。

3.2 破坏重建算法

步骤1破坏操作。首先搜索动态需求中由于使用原方案而导致违反时间窗或容量约束的任务点,然后从中随机选择其中一个点进行破坏,并计算剩余任务点与该任务点的相关度,选择相关度较大的任务点构成破坏任务点集合,为避免陷入局部最优,仍然加入随机算子进行选择;若不存在违反约束的任务点,则从所有任务点中随机选择任务点进行破坏。

步骤2重建操作。基于最佳插入原则,即对每个被移除的个体选择不违反容量和时间窗约束,并使得插入后新增距离最小的位置进行插入。

步骤3计算对新生成的解计算其目标函数,若新解优于原解,则进行最优解更新,反复迭代直到达到最大迭代次数。

在动态调度阶段,为达到快速响应的目的,要求信息处理的时间尽可能短,采用基于破坏重建思想的邻域搜索算法进行求解,可以避免局部搜索算法在面对大规模算例时的局限性,同时又可以快速求解以获得方案的实时性与可执行性。

4 仿真验证

为验证模型及算法的有效性,以中国广州白云机场为研究对象,以食品车和清水车为例进行实例验证与分析。该机场目前机位布局图如图3所示。

图3 机场基本布局图Fig.3 Basic layout of the airport

根据机场地面保障车辆运行相关规定[25],将25 km/h设置为仿真实例中车辆行驶的平均速度,将食品车容量设置为600 份/辆,最大使用车辆数为15 辆,清水车容量设置为5 000 L/辆,最大使用车辆数为10 辆。

通过多次仿真验证,改进遗传算法的参数设置如下:种群大小为100,最大迭代次数为120,交叉概率为0.9,变异概率为0.08;破坏重建算法的参数设置如下:最大迭代次数为50,初始解规模为50。

算法采用MATLAB (版本:R2018a)编写程序,使用计算机配置为Intel(R) Core(TM) i5-10200H CPU @2.40 GHz,8 GB RAM,操作系统为Windows 10(x64)系统。

4.1 基础算例求解

以该大型枢纽机场7月份某天的航班运行数据为算例,选取计划进港时间在08:20—14:00之间的航班数据共254 条、即127 个航班对。将08:00设置为计时开始时刻。

4.1.1 初始调度阶段

实验首先基于航班的计划进离港时间对作业任务进行初始调度。使用改进遗传算法求解得到清水车与食品车具体初始规划路线,结果如表1和表2所示。清水车初始规划在第8次迭代后即可找到可行解,最终得到清水车初始规划方案使用车辆数为5辆,行驶总距离为28 585 m。食品车初始规划在第19 次迭代后可找到可行解,最终得到食品车初始规划使用车辆数11辆,行驶总距离为71 330 m。

表1 清水车初始规划结果Table 1 Initial scheduling results of potable water service equipment

表2 食品车初始规划结果Table 2 Initial scheduling results of aviation catering vehicle

4.1.2 动态优化阶段

根据实际情况,当开启当天保障服务时,动态服务时间窗也随之开启,即进入第二阶段——动态优化阶段,产生新的需求变化,通过破坏重建算法对实时调度方案进行重新调整。

本文设置航班计划更新时间间隔为120 min。将08:00设置为计时开始时刻,则第一次更新时刻为10:00,假设在10:00前可获取接下来两小时内进港航班的预计进港时间,识别可能发生早到或延误的航班,基于此对未来两小时时间段内进港的航班各作业重新进行时间规划,该时间段内的航班保障作业新时间窗将进行更新,代表新的需求,将发生机位更改和服务时间的更改将一并输入到模型中,从而得到新的路线规划方案。

对清水车和食品车的动态调度问题分别进行连续5 次求解,找到求解结果如表3所示。由表3可知,5 次求解结果中,清水车在调整后的最优方案行驶距离为28 935 m,行驶总距离包括已经完成服务航班任务的距离,平均距离成本为29 867 m,且平均在进行3 次迭代后即可找到可行解。而食品车在调整后的最优方案行驶距离为73 665 m,平均行驶距离成本为75 907 m,由于食品车容量相对较小,航班需求量较多,在调整时容量约束对求解的限制较大,需要迭代更多次才能找到可行方案;为了保障时间窗变化较大的航班可以及时得到服务,动态调度在初始规划的基础上新增了车辆,但算法运行时间仍然在1 min之内,且能收敛到较优解。实验结果表明,所使用的动态求解算法对问题的稳定性较好,所得结果均在可接受范围内。

表3 最优解结果Table 3 The optimal solution

清水车在动态调整后的具体调度方案甘特图如图4所示,框内数字代表作业任务序号。面对航班任务新需求,清水车初始调度方案有3 个航班任务发生车辆占用冲突,为了保证每个航班及时进行服务,动态调整后清水车使用数量相较初始规划增加一辆,但调整后增加的车辆总行驶距离仅为350 m。由于食品车配送任务较多,原初始规划方案对新规划的时间窗发生车辆占用冲突的航班数较多,因此各路线在符合新规划的时间窗约束的条件下,进行了较多调整,但综合来看,行驶总距离仅新增3.2%,且运算时间降低了8 min,验证了本文采用的调度方法在面对需求较大和动态变化较多的算例时仍能保证实时性和运行效率。实验结果表明,所使用的动态求解算法对问题的稳定性较好,所得结果均在可接受范围内。

图4 清水车动态调度方案Fig.4 Dynamic scheduling scheme of clean water vehicle

4.2 算法性能

为了体现在初始调度阶段采用的改进遗传算法GA(LNS)的优越性,增加基于先到先服务(first come first service,FCFS)策略以及传统遗传算法的求解结果作为比较。采用不同算法得到的结果如表4所示。

表4 不同算法结果对比Table 4 Comparison of the different algorithms results

由表4可知,基于FCFS的方法虽然可以得到可行解,但无法考虑车辆在路线与距离上的全局最优,不利于环境和成本的节省;使用传统GA算法可使清水车路线方案总距离比FCFS减少44.61%,食品车路线方案总距离比FCFS减少31.72%,但由于航班数量多,随机组合方式多样,导致寻找可行解需要花费大量时间;对于本文采用的GA(LNS),可以快速找到可行解,其算法虽然加入了邻域搜索的过程,也仍然可以在计算时间相对较短的情况下获得较优解,同时其得到的最优解相比FCFS和GA有大幅下降,不仅可使用更少的车辆数,节约车辆使用与维护成本,其求解的清水车方案行驶总距离较FCFS和GA分别减少55.31%和19.31%,食品车方案行驶总距离较FCFS和GA分别减少47.38%和22.93%,验证了本文改进遗传算法的可行性与有效性。

分别选择5 次试验表现最好的清水车和食品车在经过动态调整后的调度方案,将其指标与初始车辆调度方案进行对比,如表5所示,以此来验证本文在动态调度阶段采用的破坏重建算法的性能。由表5可知,采用本文设计的基于破坏与修复算子的动态求解算法,可使得各车辆路线在符合新规划时间窗约束的条件下,求解的运行时间大大降低,虽然清水车在调整后新增总行驶距离1.2%,食品车总行驶距离新增3.2%,但均在可接受范围之内,验证了本文采用的求解算法满足地面保障车辆动态调度问题的实时性要求。

表5 初始调度与动态调度结果对比Table 5 Comparison of initial scheduling and dynamic scheduling results

5 结论

基于航班信息动态变化的特点,且需求带有时间窗要求的情形,针对带时间窗的机场地面保障车辆动态调度问题,考虑机场航班延误、提前等情况,构建了双阶段机场地面保障车辆调度模型,并设计双阶段启发式算法进行求解,最后以清水车和食品车调度为例分别进行仿真实验,得到如下结论。

(1)在初始调度阶段采用的改进遗传算法GA(LNS),虽然加入了邻域搜索的过程,也仍然可以在计算时间相对较短的情况下获得较优解,同时其得到的最优解相比FCFS和GA有大幅下降,不仅可使用更少的车辆数,节约车辆使用与维护成本,其求解的清水车和食品车行驶总距离较FCFS和GA都大幅减少,验证了本文改进遗传算法的可行性与有效性。

(2)采用本文设计的基于破坏与修复算子的动态求解算法,可使得各车辆路线在符合新规划时间窗约束的条件下,求解的运行时间大大降低,虽然行驶距离有所增加,但均在可接受范围之内,验证了本文采用的调度方法在面对需求较大和动态变化较多的算例时仍能保证实时性和运行效率。

目前本文仅考虑单车场调度,但在实际运行过程中,将可能存在多个车库,比如食品将由多个航食公司进行配送,因此未来可以研究考虑时间窗的多车场地面保障车辆调度问题,进一步细化模型。