基于遗传禁忌混合算法的战时后方仓库弹药配送多任务车辆调度

雷 敉，陈 金，杨志远，高 军

（军械工程学院装备指挥与管理系，河北石家庄 050003）

基于遗传禁忌混合算法的战时后方仓库弹药配送多任务车辆调度

雷 敉，陈 金，杨志远，高 军

（军械工程学院装备指挥与管理系，河北石家庄 050003）

后方仓库承担着战略战役级弹药物资的周转、储存、供应的重要任务，在整个弹药保障体系中具有不可替代的作用，对后方仓库弹药配送的车辆调度进行合理安排是提高弹药保障效率的关键因素，是实现精确保障的前提条件。本文针对能够以汽车配装运输的通用弹药保障，建立了带时间窗约束的多任务车辆调度数学模型，对基本遗传算法进行了改进，构造了一个两层搜索结构的遗传禁忌混合算法，其算法的优化能力、运行效率、可靠性相对于基本的遗传算法均得到了提高，通过仿真进行验证取得了良好的效果。

弹药配送；多任务车辆调度；遗传混合算法

1 问题分析

后方仓库作为战时弹药保障的枢纽环节，其储备的弹药物资能否及时、准确、高效地输送到作战前沿，关系着整个战役的进程，甚至决定战争成败。在战时的弹药配送中，作为执行主体的后勤系统运输分队能否科学、合理地进行车辆调度是提高整个保障效率的关键，也是实现弹药精确保障的重要条件［1］。本文针对能够以汽车配装运输的通用弹药保障，建立了战时后方仓库弹药配送多任务车辆调度问题的数学模型，并应用遗传禁忌混合算法对问题进行求解。

战时车辆调度问题一般可分为两种。若保障点的需求量是单个运输单元（若干辆车）装载容量的整数倍，则为单任务车辆调度问题，即每个运输单元只给一个保障点送货；如果每个保障点的需求量都小于运输单元装载容量，则单一运输单元可以同时为多个保障点送货，这就是多任务车辆调度问题。

战时后方仓库弹药配送多任务车辆调度问题可以描述为：在给定的条件下，要求合理安排若干个运输单元去往若干个需求单位的行车路线，把需求的弹药从后方仓库送到部队，使得目标函数取得最优。目标函数可以取为运输总里程数最短、运输总时间最少、需要的运输单元数最少等。文［2］实现了带时间窗的多目标派车问题优化；文［3］在运力不足条件下解决了战时物资调运的问题；文［4］改进了传统的遗传算法，提出了战时备件配送车辆调度的优化方案。

2 模型建立

现做出如下假设：

（1）设后勤运输分队有K个运输单元，每个运输单元都有一定的装载能力限制，且满足单个运输单元的容量大于每个保障单位的需求量；

（2）每个保障单位所需物资只能由单独运输单元完成，且其需求量是已知的，同时所有保障单位的需求都必须得到满足；

（3）每个运输单元行驶线路的开始和结束位置都在后方仓库；

（4）每个保障单位都有一个指定的保障时间窗口，物资的运输必须在此时间范围内进行。

设后方仓库有K个运输单元，每个单元k的载重量为Qk（k＝1，2，…，K），总共有L个单位需要保障，每个单位i的需求量为qi（i＝1，2，…，L），且要求物资运到处在时间范围［ai，bi］内，保障点i到j的运输距离为dij，后方仓库到各单位的距离为d0j（i，j＝1，2，…，L）。设si表示车辆到达保障点i的时刻，ti表示车辆在保障点i的卸货时间，tij表示车辆从保障点i行驶到保障点j的运输时间。再设nk为第k个运输单元保障的单位数（nk＝0时则表示未使用第k辆车），用集合Rk表示第k条路径，其中的元素rki表示保障单位rk在路径k中的顺序为i，rk0＝0表示后方仓库，s0＝0表示运输单元从后方仓库出发的时刻为0。将车辆运输总里程作为战时多任务弹药配送车辆调度问题的目标函数，将运输时间及其他要求作为约束条件，建立数学模型：

式（1）为总运输里程最短的目标函数；

式（2）表示每条路线上各保障点的货物需求量之和不超过运输单元的载重量；

式（3）保证了每条路线上的任务数不超过总任务数；

式（4）表明每个单位都得到保障；

式（5）表示每条路线上的保障单位；

式（6）规定每个保障点只能由一个运输单元进行保障；

式（7）表示当第k个运输单元保障的单位数≥1时，则该单元参加了运输，取sign（nk）＝1；当第k个单元保障的单位数＜1时。表示未使用该运输单元，sign（nk）＝0；

式（8）反应了每条运输路线上车辆到达下一个保障点的时刻＝车辆到达当前保障点的时刻＋当前保障点的等待时间＋从当前保障点到下一个保障点车辆的行驶时间＋从当前保障点到下一个保障点车辆的行驶时间；

式（9）表示车辆在某个保障点的等待时间取决于车辆到达该点的时刻与该点保障时间窗开始时刻的关系。当车辆到达该保障点的时刻小于该保障点时间窗开始时刻时，车辆需要在该单位等待，一直到时间窗开始时刻，才能进行卸货；即等待时间为该保障点的时间窗开始时刻与车辆到达该点的时刻的差；当车辆到达该单位的时刻大于或等于该单位的时间窗开始时刻时，则车辆在该保障点不等待，即等待时间为0；可见，该式保证了车辆卸货的时刻大于或等于该单位的保障时间窗开始时刻；

式（10）表示车辆到达某单位的时刻必须小于或等于其时间窗结束时刻。

上述模型具有较好的扩充性，便于设计求解算法和使用计算机编程求解；同时考虑的目标函数和约束条件都比较全面，与现实较为接近。

3 算法设计

本文首先利用遗传算法进行全局搜索，使群体中的个体比较稳定地分布在解空间的大部分区域，再以群体中每个个体为出发点，用禁忌算法进行局部搜索，以改善群体的质量。该混合算法有效地结合了GA的全局搜索能力和TS的局部搜索能力，是一种高效的优化方法。

针对战时弹药配送多任务车辆调度问题，本文设计的遗传禁忌混合启发式算法的主要步骤如下：

Step1：输入原始数据及所需参数，包括群体规模、最优保持个数、交叉概率、变异概率、禁忌表长度、最大迭代数等，同时令GA和TS的迭代计数器为0；

Step2：形成初始化种群；

Step3：适应度计算；

Step4：判断是否满足GA终止条件；若满足，则跳出遗传算法主优化过程并输出优化结果；否则，转入Step5；

Step5：选择与交叉操作；

Step6：禁忌算法移动操作，通过改变当前解的状态达到移动的目的，从而产生一个试验邻域解；

Step7：适应度计算，计算出Step6所得到的所有邻域解的适应度；

Step8：禁忌表处理和蔑视操作，

Step9：判断是否满足禁忌算法终止条件。若满足，则跳出禁忌算法优化过程，并转入Step3进行遗传算法优化操作；若不满足，则继续返回Step6进行禁忌操作。操作步骤如图1所示。

图1 遗传禁忌混合算法流程图Fig.1 Steps of hybrid algorithm

4 实例分析

战时后方仓库接到弹药保障任务，需对12个作战单位进行弹药保障，各单位之间距离如表1所示，各作战单位的需求量、卸货时间和时间窗约束如表2所示。

仓库领导对后勤运输分队提出以下要求：一、在规定时间内送达。作战条件下情况紧急，弹药必须在每个部队用户时间窗区间内送达，弹药送到时间早于时间窗的上界时，车辆必须等待；晚于时间窗的下界时，带来时间延迟，贻误战机。二、总运输里程最短。运输分队从后方仓库出发，直到完成任务回到仓库，为该运输单元的运输里程，所有运输单元的运输里程之和构成总运输里程。三、由于各单位需要的作战物资较少，且运力紧张，要求使用尽可能少调用运输单元。

表1 节点间距离矩阵Tab.1 Matrix of inter node distance

表2 需求量、卸货时间和时间窗Tab.2 Dem and、discharge time and time w indow

其中，每个运输单元的最大装载容量是500箱，在保证弹药运输安全的情况下平均车速为60 km／h。到中午12：00时应安排驾驶员30分钟的吃饭休息时间，车辆卸货完毕后返回后方仓库。

采用本文设计的模型求解该问题步骤如下：

（1）通过运输距离除以车速60 km／h，得到相应运输时间矩阵。

（2）将各个数据输入到遗传禁忌混合算法程序中，并设置各参数：群体规模n＝20，交叉概率Pc＝0.85，变异概率Pm＝0.01。

（3）通过MATLAB进行运算求解，得到最优调度方案。

为了体现本文设计的遗传禁忌混合算法的优势，以该案例为基础数据进行实验，分别采用基本遗传算法和遗传禁忌混合算法进行计算。两种算法的参数相同。算法终止条件为迭代次数达到500代或最佳染色体保持20代这两者中达成其中之一即终止。两者算法计算结果对比如表3所示。

表3 两种算法计算结果对比Tab.3 Results of vehicle dispatching and route selecting

从中对比可发现：在配送总距离方面，采用基本遗传算法的配送总距离的平均值为854.8 km，而采用遗传禁忌混合算法的配送总距离的平均值为746 km，比基本遗传算法低16.6%；在使用车辆数方面，采用基本遗传算法的平均使用车辆数为4.6，而采用遗传禁忌混合算法的平均使用车辆数为4辆，较基本遗传算法性能提升15%；在计算时间方面，采用基本遗传算法的平均计算时间为12 s，而采用遗传禁忌混合算法的平均计算时间仅为2s，较基本遗传算法性能提升400%。

5 结 论

弹药物资收发和运输车辆调度是实现物资配送的两个具体工作。其中，收发环节是后方仓库弹药保障业务流程的核心环节，而由后勤运输系统负责的车辆调度作为弹药收发的外延，是整个弹药保障物资输送到部队的最后一步，其安排是否科学、合理，是否能满足精确保障的需要，决定了整个后方仓库弹药保障成功与否。针对战时后方仓库弹药配送多任务车辆调度问题，设计的遗传禁忌混合搜索算法，相比较与单一算法其搜索效率有了很大程度的提高，优化能力提升显著，可以认定遗传禁忌混合算法适用于解决战时车辆调度问题上。

［1］ 曲倩倩，曲仕茹，温凯歌.混合遗传算法求解配送车辆调度问题［J］.计算机工程与应用，2008，44（15）：205－208.

QU Qianqian，QU Shiru，WEN Kaige.Hybrid genetic algorithm for distribution vehicle routing problem［J］.Computer Engineering and Applications，2008，44（15）：205－207.

［2］ 李芳，郑晴，邱俊茹，等.带时间窗的某物流配送车辆调度问题的方案优化分析［J］.数学的实践与认识，2010，9（17）：176－181.

LIFang，ZHENG Qing，QIU Junru，et al.An optimization analysis on a vehicle scheduling problem of logistics and distribution with time windows［J］.Mathematics in Practice and Theory，2010，9（17）：176－181.

［3］ 李仁传，严永林，刘楠.运力不足条件下的战时物资调运模型及算法［J］.军事运筹与系统工程，2007，6（2）：37－40.

LI Renchuan，YAN Yonglin，LIU Nan.The material distribution model and algorithm under the condition of lack of capacity［J］.Military Operations Research and Systems Engineering，2007，6（2）：37－40.

［4］ 张立峰，赵方庚，孙江生，等.基于遗传算法的战时备件配送车辆调度［J］.测控自动化，2009（25）：222－224.

ZHANG Lifeng，ZHAO Fanggeng，SUN Jiangsheng.et al.Genetic algorithm for the vehicle scheduling problem of the wartime spare parts［J］.Automation of Measurement and Control，2009（25）：222－224.

雷 敉 男（1991－），湖南邵阳人，硕士生，主要研究方向为物流管理理论与应用。

陈 金 男（1992－），山东泰安人，硕士生，主要研究方向为军械物流供应链。

Multitasking Vehicle Routing for Delivering the Explosive During Wartime Based on a Mixed Algorithm of Genetic Taboos

LEIMi，CHEN Jin，YANG Zhiyuan，GAO Jun

（Equipment Command and Management Department，Ordnance Engineering College，Shijiazhuang 050003，China）

The rear warehouse is responsible for the storage and supply of ammunition.In the entire ammunition support system has irreplaceable role.The reasonable arrangement of the vehicle scheduling is the key factor to improve the efficiency of ammunition support，and it is the precondition to realize the accurate guarantee.For transportation to car equipped w ith general ammunition，I w ill build up a mathematical model of multitasking vehicle w ith Time W indow constraint and construct a mixed algorithm of genetic taboos w ith two－layer searching structure.The algorithm has ability of optimization，operating efficiency and reliability compared w ith basic genetic algorithm.Good results are obtained by simulation.

delivering the explosive；multitasking vehicle routing

TP 301.6

A