基于遗传算法的机场特种车辆调度应用研究

杨 珏

(中国民航大学 基础实验中心，天津 300300)

0 引 言

航班在机场过站期间，机场需要利用特种车辆(如清洁车、配餐车、加油车、行李车等)，为航班提供加注燃油、配餐、装卸行李货物等地面保障服务。车辆的优化调度对提高航班正点率和资源利用率至关重要。现阶段国内民航机场对特种车辆的调度还是基于人工编排的单车服务单航班的调度方式。这种调度方式效率低下，车辆资源的利用率不高，在航班密集的时候，极易造成航班延误。因此为了保障机场内所有过站航班都能按时接受高质量的地面保障服务，需要对机场的特种车辆调度进行研究。

机场特种车辆调度是带时间窗约束的车辆路径问题(vehicle routing problem with time window，VRPTW)[1-3]。机场地面服务保障部门需要安排合理的车辆行驶路线为航班提供及时的地面保障服务，实现在车辆续驶路程、车辆载运量和航班时间窗等的约束条件下，所需车辆数最少、车辆总行驶距离最短和车辆调度总成本最少的目标。Thangiah[4]和Joe[5]都曾应用遗传算法求解VRPTW问题,前者的目标是使总的服务成本最小,而后者的目标有两个,首先是使用最少的车辆,其次是在使用最少车辆的前提下使总成本最小。

文中以机场地面燃油加注业务为研究对象。首先，依据燃油加注业务构建加油车辆调度的数学模型；然后，利用遗传算法对模型进行求解，与文献[4-5]相比，文中目标是在保证航班无延误的前提下，使车辆调度总成本最小。该方法同样适用于与燃油加注调度规则相似的配餐和加注清水服务的车辆调度，只需根据实际情况调整最大车载容量限制和最大车辆行驶距离等参数。

1 问题描述和数学模型

以为航班提供燃油加注服务业务为研究对象，带时间窗的机场加油车辆调度问题可以简述为：机场有N个航班F={1,2,…,n}等待燃油加注服务，l辆加油车V={1,2,…,l}，加油车的最大行驶路程为Q，规划加油车为航班服务的路径方案，保证航班加油服务的及时性，实现加油车总行驶距离最短以及调度成本最低的目标。

参数定义：

Ti—航班i所需的加油服务时长；

dij—停机位i到停机位j间的距离；

sik—表示第k辆车为航班i加油的开始时刻，令s0k=0；如果第k辆车不为航班i加油，则sik没有意义，k∈V。

ai—航班燃油加注服务的时间窗下限(最早开始加油时刻)；

bi—航班燃油加注服务的时间窗上限(最晚开始加油时刻)；

第k辆加油车服务完第i个航班后为第j个航班服务；

其他

数学模型表示为：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

xijk∈{0,1},∀i,j∈N,∀k∈V

(7)

在上述表达式中，式1是目标函数，表示加油车辆的行驶路径、航班的延误时间以及车辆加油服务等待时间的加权平均值最小；式2保证每个航班仅能接受一次服务；式3表示加油车须满足的行驶路程限制；式4～6表示车辆从车场出发，完成航班的燃油加注服务后，回到车场；式7表示航班以及车辆的整数化约束。

2 遗传算法设计

2.1 算法原理

遗传算法[6]是一种解决最优化问题的有效方法。该算法模拟了达尔文的遗传选择和生物进化的过程，最早由美国Michigan大学的J.Holland教授提出。

遗传算法从一个初始种群的随机状态开始搜索。种群由若干被称为“染色体”的个体构成，每个个体都是问题的一个解。个体在种群衍化过程中不断更新，这种更新称为遗传。通过“适应值”指标衡量种群中个体的优劣，通过遗传算子(交叉、变异)生成被称为后代种群的个体，通过“适应值”对后代个体进行筛选，以保持种群的规模固定。经过不断迭代，算法最终会收敛在某个“适应值”最好的个体，从而得出问题的最优解或近优解。

2.2 算法步骤

遗传算法流程如图1所示。

图1 遗传算法流程

2.3 带时间窗的机场特种车辆调度问题的遗传算法的设计

2.3.1 编码方式与初始化种群

为了使染色体能够简单地表示VRPTW问题的解，采用自然数编码[7]方式。用0表示车场，用1,2,…,L表示待服务的航班任务。假设机场有一个车场，有K台车，则最多存在K条航班服务路径，每条服务路径都始于车场，也终于车场。为了在一个染色体中反映出多条服务路径，采用增加K-1个虚拟车场的方法，这K-1个虚拟车场分别用自然数L+1,L+2,…,L+K-1表示。这L+K-1个互不重复的自然数的排列就构成一个染色体，并对应一种航班服务路径方案。

例如，现有8个航班(1,2,…,8)需要服务，则染色体A={0,1,4,6,2,9,3,5,7,8,10}中9,10为添加的虚拟车场，并且加油车辆数为2，服务的路径分别为k1,k2。子路径k1为：0-1-4-6-2-0；子路径k2为：0-3-5-7-8-0。

2.3.2 适应值评估

为了满足生物“优胜略汰”的进化目的，必须对每个染色体进行适应值评价。染色体的适应值决定了其在群体中的生存能力。对于航班加油服务，主要有两个约束：(1)时间窗约束，即车辆到达航班i位置的时间既不能早于ai，也不能迟于bi；(2)车辆的续航能力约束，即某个车辆行驶的总距离不能超过车辆最大行驶路程限制。因此，在满足上面约束的前提下，对染色体k构造出下面的评价函数:

k2*max{sik-bi,0}+k3*dij]

(8)

其中，k1,k2,k3为权重系数，满足0≤k1,k2,k3≤1且k1+k2+k3=1。式中的前两项分别为加油服务车辆的等待与加油服务的延误时间，第三项考虑的是距离因素，从航班i的位置到下一个航班j位置之间的距离。

2.3.3 选择操作

选择操作是指在种群中选择优化的个体或者选择通过配对交叉产生的新个体的操作。每个个体被选择的概率与其适应值成正比，适应值大的个体被选择的可能性大，适应值小的个体被淘汰的可能性大。选择的方法常见的有轮盘赌选择[8]以及最佳个体保存选择策略[9]，文中采用后者。

2.3.4 交叉操作

基于航班任务与虚拟车场共同排列编码方法产生的染色体中的元素是互不重复的自然数，若采用简单的一点交叉或多点交叉算子，必然以极大概率产生不能服务所有航班的调度方案。文中采用部分匹配交叉[10]方法。定义随机产生的两个交叉点之间的区域为匹配区域，使用位置交换操作交换两个位串的匹配区域。

例如，对染色体A={0,1,4,6,2,9,3,5,7,8,10}与染色体B={0,5,7,6,9,1,3,2,4,8,10}进行交叉操作。

(1)随机选取交叉点2,6。

A=0 14 6 2 9 35 7 8 10

B=0 57 5 9 1 32 4 8 10

(2)进行交叉操作。

A=0 17 5 9 1 35 7 8 10

B=0 54 6 2 9 3 24 8 10

(3)对染色体A去除重复。

A=0 14 6 9 2 35 7 8 10

(4)对染色体B去除重复。

B=0 51 6 7 9 32 4 8 10

2.3.5 变异操作

遗传算法利用变异算子[10-11]实现变异操作。当遗传算法通过交叉操作接近最优解邻域时，利用变异操作可以使算法加速向最优解收敛，从而提高算法的局部随机搜索能力，另外，引入变异操作也是为了维持群体的多样性，以防止算法过早收敛。

例如，对染色体A={0,1,4,6,2,9,3,5,7,8,10}进行变异操作。

(1)随机选取交叉点2,6。

A=0 146 2 935 7 8 10

(2)交换。

A=0 136 2 945 7 8 10

3 算例分析

为了验证算法的有效性，利用机场的实际航班数据，实现机场燃油加注车辆的调度。

3.1 数据采集

该机场每天约有300个进出港航班。加油车的平均速度设定为20 km/h，最大行驶路程设定为50 km。由于只需为离港航班提供燃油加注服务，因此选取了该机场某天的147个离港航班数据进行实验。

3.1.1 停机位距离

停机位是指航空器在机场停机坪停泊的位置。为了避免剐蹭航空器，加油车辆在停机坪上必须按照规定的路线行驶。停机位的位置关系决定了加油车辆的行驶距离。该机场的停机坪有63个停机位，表1列出了部分停机位间的距离(m)，其中D表示车场。

3.1.2 离港航班加油服务时间窗

离港航班加油服务时间窗是指为航班提供加油服务的最早开始时刻(或称加油服务时间窗下限，单位：时刻)和最晚开始时刻(或称加油服务时间窗上限，单位：时刻)限制的时间范围，加油车辆必须在这个时间范围内开始为航班提供燃油加注服务，否则将可能导致航班延误。

表1 停机位间的距离

按照民航局地面服务规范：燃油加注保障服务应在航班开始登机前5分钟完成，航班一般在计划离港时间前30分钟开始登机。依据该服务规范，确定航班加油服务的时间窗下限和时间窗上限。

参数定义：

ai—加油服务时间窗下限(最早开始加油时刻)；

bi—加油服务时间窗上限(最晚开始加油时刻)；

td—离港航班计划时刻；

Ti—加油服务时长。

离港航班加油服务时间窗：

ai=td-Ti

(9)

bi=td-Ti-35

(10)

按照式9和式10可以计算每个离港航班的加油服务时间窗。为了便于计算，将时间统一转化为分钟。部分离港航班的加油服务时间窗如表2所示。

表2 离港航班加油服务时间窗(部分)

3.2 结果分析

利用Matlab工具软件实现文中算法。采用软时间窗约束，允许加油车辆等待被服务航班，允许加油服务延误。若将航班延误的惩罚系数设以最大值，则可表示此解不可行，即在选择过程中此解会被淘汰，即不允许加油服务延误。

为了使结果能最大限度地趋于最优值，将所有方案的种群最大规模设为200，迭代次数设为200。

方案一：随机生成种群，分别用不同的交叉算子和变异算子进行测试，实验结果如表3所示。

表3 遗传算法求解结果

方案二：利用最近插入法[12]生成初始种群的初值，实验结果如表4所示。

表4 利用最近插入法生成初始种群的 遗传算法求解结果

方案三：利用禁忌搜索法[13]生成初始种群的初值，实验结果如表5所示。

方案一中由于遗传算法的初始解为随机解，而初始种群规模不大且遗传代数不够，导致最终解质量较差。方案二求解的路径长度为61 300 m，等待时间为321.3 min，延误时间为0 min。方案三求解的路径长度29 240 m,等待时间为761.941 2 min，延误时间为0 min。方案二与方案三均可用遗传算法使解进一步优化且能得到较优解。

表5 利用禁忌搜索法生成初始种群的 遗传算法求解结果

选取方案二中(如表4所示)第3次运行的结果作为最优值，车辆总路程为65 200 m，无延误时间，等待时间为265.8 min，而单车单航班服务方式总路程为88 320 m，车辆的总行驶路程减少26.2%。

4 结束语

根据机场燃油加注保障服务的业务构建了燃油加注车辆调度的数学模型，利用基于不同搜索策略的遗传算法求出满足软时间窗限制且调度成本最低的车辆调度解决方案。通过对最大车载容量限制，最大车辆行驶距离以及适应值函数设置不同的参数,该解决方案也适用于机场提供配餐服务和加注清水服务的车辆调度。

在航班保障服务实际运行中，由于航班计划时刻容易受到天气、航路管制等因素的影响，车辆的调度方案要根据航班时刻的变化做适时调整。后期需要在该静态调度方案的基础上，对车辆的动态调度[14]做进一步研究。