考虑任务均衡的加油车动态调度问题*

衡红军，戚馨桐

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

1 引言

车辆调度问题是多项式复杂程度的非确定性问题NP(Non-deterministic Polynomial)，求解该问题通常采用3大类算法，即启发式算法、仿生算法和精确算法。启发式算法构造简单，对于求解较小规模数据较为有效，但对于较大规模数据往往表现欠佳[1 - 3]；仿生算法会因为陷入局部最优的陷阱而无法得到最优解，需要结合其他算法来提高前期搜索能力[4,5]；而精确算法可以获得问题最优解，却是以庞大的计算量作为代价的，随着计算机性能的提升，精确算法运用在大规模调度问题上成为新趋势[6 - 8]。目前，针对机场特种车辆调度问题的研究较少且以启发式算法为主，衡红军等[9]利用节约值算法归并回路搜索最短路径；Wang等[10]提出一种基于贪婪策略的机场加油车调度算法AVSAGS(Airport Vehicle Scheduling Algorithm based on Greedy Strategy)求解该问题。

本文研究机场地面服务中的燃油加注服务。目前，机场地面服务仍停留在人工调度阶段，采用单车单服务的方式(即：车辆从车场出发完成1个航班的燃油加注服务后便返回到车场)会使得机场的地面资源利用率降低，同时难以确保加油员工作量均衡。考虑在资源充足时，即当值加油员与加油车为一一匹配关系，加油员驾驶加油车在过站航班和始发航班的进港、出港时段提供燃油加注服务。由于过站航班的到达时刻易受到自然环境、航线流量等因素的影响，导致航班的实际时刻与计划时刻相差较大，所以采取过站航班在临近机场时发送的预计到达(进港)时刻以及始发航班的预计出港时刻作为是否为航班安排服务的依据。

基于上述航班时刻特性，本文构建了一种基于动态规划时间窗的实时车辆调度模型DVRPTW(Dynamic Vehicle Routing Problem with Time Window)[11]，通过航班预计时刻计算航班燃油加注服务时间窗，对服务开始时刻进入到规划时间窗的航班构建DVRPTW模型，模型根据实际情况加入约束条件与目标函数。之后将动态调度问题转化为连续时间片下的静态调度问题[12]。在每个时间片下通过自适应分支定价算法配置车辆、人员为航班服务，车辆根据不同航班的燃油加注服务的开始时刻与结束时刻进行衔接，车辆完成1次任务(服务序列)返回车场。再通过贪婪策略将任务进行衔接，最终实现车辆行驶时间最少，加油员的工作量均衡(差异最小)的目的。

2 问题描述与数学模型

2.1 问题描述

给定N+M个航班集合H={1,2,…,N,N+1,N+2,…,N+M}，其中N表示始发航班的数量，M表示过站航班的数量。集合V={1,2,…,T}表示车辆集合。规划车辆为航班服务满足以下约束：(1)每个航班仅被燃油加注服务1次；(2)所有航班仅可在其规定的燃油加注服务时间窗口内被服务；(3)加油员驾驶加油车从车场出发，完成1次任务即返回车场。实现如下目标：(1)车辆行驶时间最短；(2)加油员的工作量均衡。

2.2 数学模型

2.2.1 符号说明

(1)H0=H∪{0},Hn+1=H∪{n+1}，其中0和n+1分别表示将车场视为起点和终点。(2)L为执行燃油加注任务派出的车辆次数。(3)ti,j为航班i所在停机位到航班j所在停机位的车辆行驶时间，其中t0,i和tj,n+1分别表示车辆从车场出发到达i和从j返回车场的时间。(4)xi,j,k表示弧的决策变量，若xi,j,k=1，则表示车辆k服务航班i后，立即对航班j进行服务。(5)ci为航班i的服务时间。(6)si,k表示车辆k为航班i开始服务的时刻。(7)[ai,bi]为航班i的燃油加注服务时间窗，其中ai和bi分别表示服务的最早和最晚开始时间。(8)θ表示不满足燃油加注服务时间窗的惩罚系数。

2.2.2 DVRPTW的混合整数规划模型

(1)

(2)

(3)

(4)

(5)

(6)

si,k+ci+ti,j-θ(1-xi,j,k)≤sj,k,

∀i,j∈H,∀k∈V

(7)

ai≤si,k≤bi,∀i∈H,∀k∈V

(8)

xi,j,k∈{0,1},∀i∈H0,∀j∈Hn+1,∀k∈V

(9)

其中，式(1)和式(2)为目标函数表达式，分别表示车辆行驶时间最短和车辆之间的任务量差异最小。式(3)～式(9)为约束表式，分别表示：式(3)确保同一航班不被重复执行燃油加注服务；式(4)～式(6)确保加油车从车场出发开始为航班服务，执行完任务后，返回车场；式(7)确保车辆k为航班i服务后，从其所在停机位出发到达航班j所在停机位开始服务并确保开始服务时间在航班j的燃油加注服务时间窗口内，xi,j,k=0时表达式依然成立；式(8)确保所有航班必须在其规定时间窗内得到燃油加注服务；式(9)确保决策变量xi,j,k的取值为0或1。

3 算法设计

3.1 算法设计思想

求解动态规划问题应该首先将其转化为多个连续时间片下的静态调度问题。在每个时间片下，通过自适应分支定价算法规划车辆的行驶路径，将航班的燃油加注服务进行衔接形成服务序列，实现车辆行驶时间最短，车辆单次任务的工作量均衡的目的，在此过程中服务的衔接要满足式(3)～式(9)的约束条件。由于在实际情况中，任务数量往往大于实际车辆数，在保证加油员有休息时间的条件下，通过贪婪策略有效地衔接任务，进一步实现加油员工作量均衡的目的。

3.2 相关定义

定义1动态规划时间窗(t0+t)，t0表示当前时刻，t表示时间窗的长度。

定义2设k个连续时间片t1,t2,…,tk,每个时间片的长度恒定为Δ，可以得到ti的时间区间为[(i-1)·Δ,i·Δ]。在ti的开始时刻读取数据，经过τ(τ<<Δ)计算时间生成调度方案，在区间[(i-1)·Δ+τ,i·Δ+τ]执行调度方案。

定义3行驶时间=[行驶距离/行驶速度]。

定义4服务时间=燃油加注时间=[燃油加注量/燃油加注速度]，本文以服务时间作为衡量工作量的尺度。

3.3 工作流程

步骤1初始化预计航班集合、待排航班集合，将当日所有航班标记为“未访问”。

步骤2在当前时间片ti开始时刻读取预计航班数据到预计航班集合，若集合不为空，则执行步骤3。

步骤3计算预计航班集合中航班的燃油加注服务窗口，将服务窗口最早开始时刻进入到动态规划时间窗口且标记为“未访问”的航班加入到待排航班集合，并将这些航班标记为“已访问”。

步骤4若当天所有航班都安排完毕，则结束；否则，转步骤5。

步骤5若待排航班为空，则转步骤7；否则，转步骤6。

步骤6通过自适应分支定价算法配置车辆、人员进行燃油加注服务。

步骤7时间片ti开始时刻读取预计航班数据到预计航班集合，若集合不为空，则执行步骤3。

4 自适应分支定价算法

本文采用动态列生成算法[13]以及分支策略[14]构建一种新颖的自适应分支定价算法。列生成算法通过DW(Dantzig-Wolfe)分解原理[15]将原问题分解为表达式简单但列变量数目庞大的主问题MP(Master Problem)以及含有资源约束的多目标优化路径的子问题。由于无法枚举出主问题的所有列变量，只需得到限制主问题RMP(Restricted Master Problem)，限制主问题的解属于主问题解的凸子集，即同样包含最优解。每次迭代将松弛限制主问题模型转化为其对偶模型，可减少变量基数，加快计算速度。求解对偶模型得到对偶值，重新定价子问题，从而指导列的生成，而对偶模型的检验数判断是否将列加入到限制主问题规模，直到子问题无法产生检验数小于0的列，求解RMP即可得到浮点数最优解。最后采取基于弧的分支策略得到整数最优解。自适应分支定价算法流程图如图1所示。

Figure 1 Flow chart of branch and pricing algorithm图1 分支定价算法流程图

4.1 DW模型分解

4.1.1 符号及表达式

(1)λ1，λ2表示给2个目标分配的不同权重。(2)ϖ={b1,b2,…,bn}表示限制主问题规模中所有列的集合。(3)tr表示当前列r所途经路径的行驶时间，tr=∑i∈H0∑j∈Hn+1ti,jxi,j。(4)Cr表示当前列r的服务时间，Cr=∑i∈H0∑j∈Hcjxi,j。(5)dck表示列对应车辆k已经完成或正在进行燃油加注服务的航班的总服务时间。(6)若列r包含航班i时ei,r=1，否则ei,r=0，∑i∈H0∑j∈Hxi,j=∑j∈H∑r∈ϖej,r。(7)θr表示列的决策变量，解中包含服务序列r时为1，否则为0。(8)C表示每个航班服务序列的目标燃油加注时间，C=∑i∈Hci/L。

4.1.2 限制主问题

将整数线性规划模型式(1)～式(9)转化为集合覆盖模型作为限制主问题模型，再依据4.1.1节的公式推导，可以得到限制主问题模型，定义如下：

(10)

(11)

θr∈{0,1},r∈ϖ

(12)

式(10)与式(1)和式(2)含义一致。式(11)和式(12)分别对应式(3)和式(9)。

4.1.3 资源约束下的多目标优化路径子问题

松弛后的限制主问题模型的对偶模型定义为：

(13)

(14)

0≤πi≤1,i∈H

(15)

对偶模型的检验数为：

(16)

根据等价关系将式(16)细化为基于弧的表达式：

(17)

子问题模型定义为：

(18)

s.t.约束式(3)～式(9)

(19)

4.2 自适应分支定价算法具体实现

4.2.1 符号说明

(1)W表示等待服务的航班集合，∪s∈ϖo(s)=W,其中o(s)表示服务序列s所包含的航班。(2)P表示新产生的检验数小于0的列的集合。(3)Q=∪k∈Vqk表示车辆覆盖集合，其中qk表示被车辆k所覆盖的列集合。

4.2.2 动态列生成算法

算法1动态列生成算法

输入：待排航班。

输出：服务序列。

步骤1将待排航班加入到Ni集合。当前时间片ti，若i≥2，转步骤2；否则,转步骤7。

步骤2车辆覆盖集合Q中，若存在集合对应车辆k为空闲状态，则车辆k返回车场，销毁属于qk的所有列。

步骤3删除所有列中已经完成与正在进行燃油加注的航班，更新W，ϖ，Q。

(1)删除后，若列不为空，则保持剩余航班相对顺序；

(2)删除后，若列为空且列不属于Q，则销毁列。

步骤4单纯型算法求解RMP模型，并得到对偶变量πi,i∈W。

步骤5列衍生新列：

(1)插入操作。

①选择1个列s∈ϖ；

②选择航班l∈Wo(s)尝试插入到列s的任何位置，计算o(s)∪l后，o(s)航班服务的花费zs=zsl-πl；

③在列s上重复操作②，直到所有属于Wo(s)的航班完成操作②；

⑤转操作①，直到所有列都完成上述操作。

(2)删除操作。

①选择1个列w∈ϖ;

②选择航班l∈o(w),在列w中删除航班l，计算o(w)l后，o(w)航班服务的花费zwl=zwl+πl;

③在列w上重复操作②，直到所有l∈o(w)的航班服务完成;

⑤转操作①，直到所有列完成上述操作。

步骤6将P中列加入到ϖ，清空P。

步骤7为Ni中每个航班生成1个新列,将新列加入ϖ。

步骤8重复步骤4与步骤5，直到新生成的列达到基数上限或P为空。

步骤9单纯型算法求解RMP模型。

步骤10利用分支策略优化解，若最优整数解中存在不属于集合Q的列，则根据贪婪策略从车场指定加油车前往服务。

4.3 分支策略

由于将列的决策变量松弛为连续型变量，导致解中多个列包含同一航班。而整数规划无法解决这一问题，因此采用基于弧的分支策略优化解。假设2个服务序列，r1途径弧(m,j)访问j，r2途径弧(h,j)访问j。将弧值四舍五入取整，优先选择弧值变幅最大的弧，假设为弧(h,j)，则会产生2种分支。分支1：保留r2的弧(h,j)，其次将其他途径j点的传入、传出弧的花费设为非常大的值；分支2：将弧(h,j)花费设为非常大。然后重新计算直到求解出最优整数解。下面详述分支策略的具体过程。

算法2分支策略

输入：分支节点。

输出：服务序列。

步骤1初始搜索树S，加入根节点。

步骤2在搜索树中选取1个节点s(分支策略)初始化RMP模型。

步骤3求解RMP模型，解为Y。

步骤4若Y为整数解，转步骤5;否则,转步骤6。

步骤5将解Y对应的目标值与上界作比较。如果小于上界，则更新上界，并进行剪枝操作；否则，根据上界剪掉当前分支。转步骤7。

步骤6Y为浮点数解，判断浮点数解对应的目标值是否小于上界，若小于，则选择新的分支节点加入搜索树，删除当前分支节点；否则，剪掉当前分支。

步骤7如果搜索树S≠∅，转步骤2；否则,当前整数解即为RMP的最优解。

4.4 贪婪策略

考虑到加油员每次任务间有一定的休息时间，安排给同一加油员的多个任务的窗口不能重叠，而且加油员执行多个任务之间的休息时间不能低于40 min。在满足上述条件的前提下，每次将新任务指派给累计工作量最少的加油员。

5 实验及结果分析

为了验证算法解决实际问题的有效性，本文选取华北某机场的实际数据作为算例，分析并验证其可行性。

5.1 数据预处理

华北某机场有63个停机位为飞机提供地面服务，机场每天的进、出港航班数量达到300架次左右。根据民航局相关文件规定：机场地面特种车辆的行驶速度不能超过20 km/h，由于机场地下铺设的油管通道覆盖所有停机位，因此加油车无需负载燃油即可为航班服务。实验选取2018年5月23日全天真实航班数据作为实验算例，共108个离港航班，其中过站航班81个，航班编号101～181；始发航班27个，航班编号201～227。

5.1.1 时序模型预测燃油加注量

在调度规划时无法得知实际燃油加注量。考虑到航线与燃油加注量的紧密关系，以及相同航线在不同自然环境下对燃油加注量的影响，所以不能单纯采用平均值法进行预测，因此本文利用长短时记忆LSTM(Long Short-Term Memory)模型，根据2018年5月23日航班对应航线的历史数据，预测该日航班的燃油加注量。部分航班的航线的预测燃油加注量如表1所示。

Table 1 Forecasting fuel refueling volume on some routes

5.1.2 停机位的距离邻接矩阵

航班在指定的停机位等待燃油加注服务。根据测算，2个相邻停机位的距离大约40 m，车辆在行驶的过程中必须按照指定的路线行驶且线路不存在交叉情况(如图2所示)。则不同停机位之间的距离邻接矩阵如表2所示，其中D表示车场。

Figure 2 Ground road map of an airport in north China图2 华北某机场地面道路图

Table 2 Distance adjacency matrix of the stand

5.1.3 航班预计消息

航班消息由民航空中交通管制部门掌控。空管部门会将航班进、出港时刻以报文的形式发给机场。

5.1.4 燃油加注服务的时间窗

燃油加注服务时间窗，表示航班服务可以在航班服务的最早开始时间与航班服务的最晚开始时间的区间内开始，航班服务过早或过晚会导致服务等待或航班延误，因此航班服务的开始时间必须在其服务时间窗内。计算时将时间类型转化为十进制类型。

始发航班燃油加注服务时间窗:

bi=td-ci-35

(20)

ai=bi-15

(21)

过站航班燃油加注服务时间窗:

ai=tad

(22)

bi=ai+10

(23)

上式中，td为始发航班预计离港时刻，tad为过站航班预计到达时刻。部分始发、过站航班的服务时间及服务窗口如表3所示。

5.2 结果分析

5.2.1 环境与参数设置

根据本文算法，利用SQL2016对数据进行预处理，CPLEX Optimization Studio (64 bit) 12.6.3学术版对模型进行规范化处理，通过Java编程计算。

Table 3 Service window for some flights

实验结合实际情况给出以下参数：车辆数为10；车速300 m/min；燃油加注速率300 kg/min；违反燃油加注服务窗口的惩罚系数设为1 000；t设为30 min，Δ设为10 min；系数λ1设置为15，系数λ2设置为10。关于序列目标工作量C的设置：首先由于航班之间的服务时间差极大，设置过小则工作量难以均衡，过大则增加服务衔接进而加大等待时间导致资源浪费；其次已知所有航班总服务时间，为达到均衡目的希望任务次数是加油员数量的整数倍，基于以上2点并通过反复实验得出C为85。

5.2.2 实验结果分析

2018年5月23日部分实时航班规划的结果如表4所示，其中R表示服务序列编号。

Table 4 Partial flight planning results

全天规划结果以及每个加油员分配的服务序列结果分别如表5和表6所示。

Table 5 Full day flight planning results

2018年5月23日全天航班服务时间2 533 min，平均服务时长为253.3 min，通过式(24)观测每个加油员服务时间与平均服务时间的差异程度。其中，L表示加油员个数，gi表示第i个加油员的工作量，G表示平均工作量，由计算可知标准差为14.13。

Table 6 Full day flight and fueller planning results

(24)

根据最终的调度结果，可以得到车辆总行驶时间为215 min,所有加油员工作量的标准差为14.13，明显优于人工调度方式；在相同数学模型下与节约算法对比，自适应分支定价算法在行驶时间、加油员工作量的均衡度与算法的运行时间上同样具有优势。如表7所示，其中t,σ,time分别表示车辆行驶时间(min)、加油员工作量标准差、程序运行时间(s)。

Table 7 Comparison results

6 结束语

本文研究了机场航班的燃油加注服务，提出了一种基于动态规划时间窗的实时车辆调度算法，并通过实例验证了算法有效性，实现了行驶时间最短，加油员工作量均衡的目的。由于其他机场地面服务同样依赖于航班的消息，所以对于其他服务(例如客舱清洁、行李运输等)该算法同样适用。但是，针对不同数据需要调整动态规划窗口以及时间片的大小，二者将直接影响调度结果的优劣，同样影响结果的还有算法计算时间，时间短则可以加快服务部署进程，所以之后工作重点将放在算法的进一步优化上。