应急物流车辆调度优化中免疫算法的应用

潘世举

（军事交通学院，天津　300161）



应急物流车辆调度优化中免疫算法的应用

潘世举

（军事交通学院，天津300161）

应急物流的特性决定了车辆调度优化的重要性，它是保证应急物流质量和效益的关键因素。在对应急物流车辆调度优化进行问题描述和条件设定的基础上，构建了应急物流车辆调度的多约束模型，同时对免疫算法及其相关问题进行了介绍，最后重点使用算例对免疫算法的应用进行了实证研究，研究结果显示免疫算法在应急物流车辆调度优化中具有一定的应用价值。

应急物流；车辆调度优化；免疫算法

1　引言

应急物流是指诸如公共卫生、自然灾害、交通事故、社会安全等领域突发性事件发生后的救援物资配送和人员财产的转移，应急物流的突发性要求其必须具有快捷的响应能力，这对于突发性事件的救援和降低生命财产损失具有十分重要的价值。车辆调度优化问题是提高应急物流敏捷性的重要手段，车辆调度优化是指在已知货物起始点的物流运输网络中，科学地组织和安排行车路径，在满足若干条件约束下实现既定的目标。应急物流的车辆调度与普通物流的车辆调度之间有明显的差异，前者对时间性和敏捷性极为重视，而对物流成本的考虑则居第二位。本文使用免疫算法研究应急物流车辆调度优化问题，在将时间作为第一约束要素的前提下，以最小的物流成本寻找到最优的车辆行车路径。

2　问题设定及模型构建

2.1问题描述

设定本文所研究的应急物流运输方式为公路运输，假设共有m受灾区域需要通过应急物流来运输配送救援物资，救援物资配送指挥中心的运输车辆类型有K种，Qi为第i个受灾区域所需要的救援物资需求量，某种类型的车辆在某个受灾区域的货物卸载时间为utik，运输车辆最迟到达受灾区域的时间为Ktik，救援物资存储中心与受灾区域的运输费用为Cijk，运输时间为tijk，其中i，j=0，1，2，3...，m，0为救援物资储备中心编号，1，2，…，m分别为受灾区域编号。救援物资配送车辆的单车装载容量为qk，不允许出现超载的情况，且必须在规定的最迟时间之前将救援物资运送到受灾区域。于是问题转化为在上述设定的条件下，如何安排和组织救援物资运输车辆并规定每辆运输车辆的路线，使得总的运输距离最短，也就是总的运输物流成本最小。

2.2条件设定

出于构建模型的需要，将上述复杂的问题进行简化，做出如下的条件设定：救援物资存储中心与各受灾区域以及各个受灾区域之间的运输距离为已知量；救援物资可以提前送达受灾区域，但不能迟于最晚规定的时间；必须满足所有受灾区域的救援物资数量和运输时间，并且单个受灾区域的救援物资需求量小于运输车辆的最大载容量；受灾区域的路况和交通条件用路况系数来表示，有正常和高峰两种状态。

2.3模型构建

令g（v，e）为一个无向图，式中v=｛vi|i=0，1，2，...，m｝为点集合，e=｛（vi，vj|vi，vj∈v，i≠j｝为边集合，救援物资存储中心为v0，它是运输车辆的始点和终点，运输车队共有K种类型的运输车辆，每种类型的运输车辆其载重量为qk（k∈K），vi（i≠0）表示受灾地区，每个受灾地区对救援物资都有非负的需求量Qi，同一个运输路线上点i与点j相邻且位于其前面，救援物资运输车辆到达点i的时间是Atik，卸货时间为utik，从点i行驶到点j需要的时间为tijk，到达点j的时间为Atjk，最迟到达时间为Ktik，那么就有Atjk=Atik+utik+tijk，弧（vi，vj）表示点i与点j之间的距离dij，距离矩阵D=（dij）满足三角不等式。根据以上设定构建如下模型：

目标函数（1）表示总的救援物资配送费用最小；约束（2）表示k类型辆车h服务受灾区域点i时的援助物资需求量不能超过其最大载重量；约束（3）表示每个受灾区域点只配送1次物资；约束（4）、（5）表示任何一个受灾区域点只接受1辆运输配送车的服务；约束（6）表示点i、点j为k类型的运输车辆所服务，并且点i优于点j优先得到服务；约束（7）表示派出的救援物资配送车辆数量等于返回的车辆数量；约束（8）表示救援物资运送到需求点的时间必须满足最迟规定的时间；约束（9）表示k类型的车经过点i、点j的时间；约束（10）表示k类型的车从点i行驶到点j的费用。

3　免疫算法

免疫算法作为一种优化组合算法，借鉴和继承了免疫系统的记忆机制、学习性和适应性，在应用免疫算法解决优化组合问题时，其步骤与免疫系统都有着对应的关系，诸如抗原对应需要求解的问题，抗体对应候选解，抗体和抗原之间的匹配度使用亲和力来描述，两个抗体之间的相似度用排斥力来描述。

3.1抗体

使用自然数对抗体进行编码。救援物资存储中心用0表示，各个受灾区域节点用1，2，3，…，8表示。当m= 8时，抗体为012345678，其可以理解为：救援物资运输车辆从存储中心0出发，经过下面的子线路再返回到救援物资储备中心：

（1）救援物资储备中心0—受灾区域节点1—受灾区域节点2—受灾区域节点3—救援物资储备中心0；

（2）救援物资储备中心0—受灾区域节点4—受灾区域节点5—受灾区域节点6—救援物资储备中心0；

（3）救援物资储备中心0—受灾区域节点7—受灾区域节点8—救援物资储备中心0。

通常情况下在解空间集合中用随机的方法生成抗体，抗体群中抗体的个数一般为网络节点个数的2倍。

3.2亲和力

免疫算法的抗原使用目标函数值，其与抗体之间的匹配度即为抗体抗原之间的亲和力，也就是说抗体的优化程度使用亲和力来进行描述，取目标函数的倒数，即：

式中 f（v）为目标函数，抗体的优化程度与对应解的目标函数值大小成反比例关系，优化程度越高说明其亲和力越大，亲和力最大的抗体为最优抗体。

3.3排斥力

两个抗体之间的排斥力与不相同基因的数量成正比。

3.4免疫算子

对于车辆调度优化问题来说，父代个体使用浮点数编码方案，即：

使用顺序交叉方法生成子代个体如下：

3.5优质串保留

如果存在多个抗体、抗原之间较大的亲和力且抗体中包含的基因串相同，那么这个基因串就为优质串。优质串保留是指在优质串检测中对下一代的抗体群中的新抗体以一定的概率p0（0＜p0＜1）使用优质串代替原来的基因串。

3.6免疫算法的应用步骤

（1）将目标函数（1）作为抗原，令抗体群规模为N，抗体群规模大小一般为网络节点数量的2倍，并设定最大的进化代数为MaxGEN。

（2）在解空间中利用随机的方法生成P个候选解作为初始抗体群，未进化时的代数为NGEN=0，在抗体群中随机选择一个抗体作为最优抗体，并记为A，其亲和力为MaxAPP。

（3）计算抗体群中每个抗体的亲和力。

（4）对本代抗体进行基因交叉操作和基因变异操作，然后计算获得新抗体的亲和力。

（5）本代抗体群中最优抗体的亲和力记为CAPP，如果其大于MaxAPP，那么NGEN=0，这时MaxAPP的值为CAPP，并将其视为当前最优抗体，否则对NGEN进行递增操作。

（6）如果NGEN大于MaxGEN，就转到步骤（9）。

（7）计算本代抗体群中各个抗体之间的排斥力大小，并根据相关公式计算抗体群中各抗体之间的浓度调节适应度。

（8）下一代抗体群为浓度调节适应度最高的P个抗体，然后再对这P个抗体以一定的概率进行保留操作，回到步骤（4）。

（9）回到当前最优抗体并将其对应的应急物流车辆调度优化方案作为为题的解，算法结束。

4　算例实证

某地区发生了突发性自然灾害，并向救援物资储备中心发出了救援请求。救灾指挥中心需要向该地区8个受灾节点进行救援物资配送。经过分析决定使用一种类型的车辆进行物资运载，最大载重量为8t，每小时行车速度为60km，物资运载车辆必须保证在不超载的前提下将救援物资在规定的时间内送达受灾节点。表1、表2给出了各受灾节点的救援物资需求数量、救援物资储备中心与各受灾节点以及各受灾节点之间的距离，其中救援物资储备中心用数字0表示。

表1　各受灾节点数据

表2　救援物资储备中心与各受灾节点及各受灾节点之间的距离

根据免疫算法的相关求解公式，本实例中免疫算法个体种群规模为20，编码长度为12，交叉概率为0.6，变异概率为0.3，浓度阈值为0.25，提取概率为0.3，排斥力为0.01，注射概率为0.4，不进化代数的最大值为20，对免疫算法进行50次循环计算，得到的计算结果见表3。

表3　算例的免疫算法计算结果

因此该算例的救援物资最佳配送距离为600，与之对应的车辆调度路径为065408207310。

5　总结

本文使用免疫算法研究了应急物流车辆调度优化问题，经过实例分析证明，该算法具有可行性，并且提高了优化质量和效率，因此在应急物流车辆调度中具有一定的应用价值。

［1］高本河，伍慧飞.多资源调度中应急物流出救点最少问题的优化［J］.物流技术，2009，（1）.

［2］张裕华，潘郁.基于蚁群算法的应急物流配送车辆调度研究［J］.物流科技，2009，（5）.

［3］王海军，杨丽娟，万钰然.模拟退火算法在应急物流车辆调度中的应用［J］.物流工程与管理，2009，（6）.

［4］陈明华，李迎秋，罗耀琪.应急物流车辆调配问题的研究［J］.计算机工程与应用，2009，（24）.

［5］韩景倜，池为叠，韩小妹.基于应急物流体的应急救援物资调度模型［J］.系统仿真学报，2009，（18）.

［6］英升贺，李毅鑫.动态规划和整数规划在应急物流物资配送优化中的应用研究［J］.物流技术，2009，（8）.

Application of Immunity Algorithm in Optimizing Emergency Logistics Vehicle Dispatching

Pan Shiju
（Military Transportation Academy， Tianjin 300161， China）

The property of emergency logistics predestines the significance of vehicle dispatching optimization which plays a key role inensuring the quality and benefit of the emergency logistics process. In this paper， after describing the dispatching optimization problem of theemergency logistics vehicles and setting its premises， we built the corresponding multi- constraint model， at the meantime， introduced theimmunity algorithm and the related issues， and at the end， in a numerical example， studied empirically the application of the immunityalgorithm， showing that it was of certain application value in optimizing the dispatching of the emergency logistics vehicles.

emergency logistics； vehicle dispatching optimization； immunity algorithm

F224；F252.14

A

1005-152X（2016）07-0080-03

10.3969/j.issn.1005-152X.2016.07.018

2016-06-17

潘世举，男，河南平顶山人，军事交通学院学生，研究方向：军用车辆。