战时物资配送模型及算法研究*

曹冠平 王跃利 丁 茜

（军事科学院 北京 100091）

1 引言

物资配送优化问题是军事物流学中的一个重要内容，是运筹学中运输问题的一个分支，不仅涉及多个单位、多种资源，还需满足资源、经费、时间、安全等多种约束条件，具有大规模、多约束、多目标等特点。采用传统的线性规划方法进行求解比较困难，有必要借助智能优化算法进行科学定量决策。当前，军内外专家学者展开了大量相关研究。如，韩景倜等人以保障时间最短为目的，研究了运力充足情况下的单种物资调运问题［1］；任杰等设计了满足应急时间约束的，基于成本最小的车辆调度数学模型，并通过设置罚函数将车辆载质量约束和时间约束转化为运输成本，最后借助遗传算法进行了求解［2］；但兵兵等以总配送时间最短、动用车辆数最少和时间平衡性最佳为目标，建立了基于需求可拆分条件下的应急物资调度数学模型，并设计了一种改进蚁群优化算法进行求解［3］；朱毅等以配送时间最短为目的，研究了保障力有限情况下的器材配送问题，并用改进粒子群算法进行了求解［4］；文仁强等以调度时间最短为优化目标，对无满载限制情形下的应急资源多目标优化调度问题进行研究，并通过蚁群算法进行求解［5］；姜大立等以应急时间最短和车辆空载率最低为目的，对单需求点物资调运问题进行了研究，并用多目标粒子群算法进行了求解［6］；宋远清等在不考虑运输成本的前提下，研究了需求随机的车辆调度问题［7～8］，宋远清运用遗传算法对车辆调度问题进行了求解［9～10］；邹明等运用遗传算法对航空装备保障的调度优化进行了研究［11～12］。

上述研究从不同视角、运用不同方法对物资配送优化等进行了分析，取得了很好的效果，但仍存在一些不足：一是物资配送过程中，对运输车辆不足的情况考虑还不够充分，部分研究虽然考虑了保障力量有限这个约束，但所建模型多以最短时间为目标，忽略了各需求点对物资需求紧迫程度的差异性，没有兼顾保障时间、车辆装载量以及物资需求紧迫度等因素；二是运用遗传算法求解时，对计算过程中如何避免不可行解，提升算法收敛速度考虑不够，往往只是借助罚函数来淘汰非法解，算法搜索效率不高。鉴于此，本文以配送时间和需求紧迫度的乘积最小为目标函数，建立了满足运输车辆最大装载量约束的物资配送数学模型，并利用遗传算法对最优物资配送方案进行求解。为有效确保解的优质性和算法的收敛速度，在合理编码的基础上，设计了特殊交叉和变异算子。最后，通过算例进行了仿真，结果表明所建模型和算法能够快速求出满足要求的最佳方案，对做好战时物资保障具有很强的指导性和操作性。

2 数学模型的建立

2.1 问题描述

假设某综合保障中心负责辖区所有单位战时的物资保障工作。中心有m台运输车辆来进行物资配送，车辆序号集 K={k|k=1，2，…，m}，设A={1，2，…，n，n+1 }为地点集，1代表保障中心，其他n个物资需求点由2-n+1进行统一编号；Lij表示地点i到地点 j的距离；R表示各单位物资需求总量，rj表示第 j个单位所需物资量，P表示运输车辆的最大载重量；ωj表示第 j个单位的物资需求紧迫度，v表示运输车辆的平均运行速度。物资配送要求：每台运输车辆定向保障相应的单位，行进路线和顺序固定，结合各需求点物资需求紧迫程度，在最短时间内完成配送任务。

为更好地明确研究边界，做如下假设：1）各物资需求单位和保障中心之间以及各物资需求单位之间均满足运输车辆通行条件；2）问题中各已知信息能够及时获取，保障中心物资存储量大于各物资需求单位的总需求量，即只考虑物资运送时间，不考虑物资装卸载时间；4）车辆完成配送任务后不需要返回需求点上。

2.2 模型建立

模型参数和决策变量如下：

F={fk|k∈K}为配送方案集，其中第k台车的配送方案，表示配送过程中车辆依次经过的地点序列，e为第k台车经过的地点总数。如 f1={1，3，5，6，8}，表示配送过程中，第1台车辆经过的地点依次为1、3、5、6、8。

TSj表示物资需求点 j配送时间和需求紧迫度的乘积，有：

xjk为决策变量，当需求点 j由第k台车配送时，xjk等于1，否则等于0。

根据以上描述，构建数学模型如下：

目标函数：

约束条件：

3 算法求解

针对上述模型，我们采用遗传算法进行求解，求解的基本流程如图1。

3.1 染色体编码

本文中，我们采用自然数编码方式来构造表示运输车辆可行路线的染色体。即：将数学模型的解向量编成一条长度为m+n+1的染色体{1，ip，…，iq，1，ir，…，is，1，…，1，it…，iu，1} ，在 染 色 体 中 ，ip(2≤p≤n+1)等自然数为某物资需求单位的编号，1表示保障中心，共有m+1个，它将染色体切分为m段，分别表示m台运输车辆的配送任务序列。染色体的编码可解释为：第1台运输车辆从保障中心出发，按照{ip，…，iq}的顺序进行物资配送；第2台运输车辆从保障中心出发，按照{ir，…，is} 的顺序进行物资配送；依次类推，第m台运输车辆从保障中心出发，按照{it…，iu}的顺序进行物资配送。所有运输车辆配送完毕则物资保障任务结束。

图1 遗传算法求解基本流程图

例如：若 m=3，n=10，染色体为 {1，2，5，3，1，4，11，6，1，7，9，8，10，1}，按照编码规则可以确定配送方案：第1、2、3台运输车辆配送顺序分别为1→2→5→3，1→4→11→6和 1→7→9→8→10。

3.2 初始化种群

初始种群是进化计算开始时的群体，设种群规模为N，本文初始种群产生方法如下：第一步，将物资需求单位的编号进行随机排序；第二步，按染色体编码顺序从左至右进行计算，如果第一台车辆装载量大于前α个单位物资需求量之和且小于前α+1个单位物资需求量之和，则得到第1台车辆的配送序列；第三步，删除染色体中前α个物资需求单位的编号，染色体剩余部分继续按步骤2的方式计算，求得第2台车辆的配送序列，如此反复，直至所有车辆和物资需求单位的编号均被安排完；第四步，在每两个配送序列之间插入“1”后，将所有配送序列连接起来，最后在首尾添加“1”，即得到一条初始染色体；第五步，重新对物资需求单位的编号随机排序，按相同办法产生剩余染色体直至种群规模达到N。

3.3 计算适应度

适应度函数定义的好坏直接影响整个算法的执行效率，针对本文设计的模型算法，将适应度函数f(x)设为目标函数的倒数，即：

适应度函数值越大的染色体越优越，也越有可能接近最优解。

3.4 交叉和变异操作

为有效保持群体的多样性，需要对染色体进行交叉和变异操作。交叉时，由于染色体中包含多个“1”，直接交叉容易产生误码，出现大量不可行解，进而降低算法的收敛速度。同时，考虑到如果某种排列能够得到较优的解，应当适当保留染色体的顺序，因此，我们对交叉方式进行了改进，具体如下：第一步，将父代染色体中的“1”删除，并记录其位置；第二步，随机选择父代染色体一个基因位i；第三步：保留两个父代染色体中位于基因位i之前的基因值，将之后的基因值按对方基因值重新排列；第四步：将“1”插入之前记录的位置，得到子代染色体。

以3辆车10个需求点为例，若：

父染色体 1 为 {1，6，3，11，1，7，8，5，2，1，4，9，10，1} ；父 染 色 体 2 为 {1，11，5，6，1，3，10，8，1，4，7，2，9，1}

随机选取基因位5，交叉后：

子 染 色 体 1 为 {1，6，3，11，1，7，8，5，10，1，4，2，9，1} ；子染色体 2 为 {1，11，5，6，1，3，10，7，1，8，2，4，9，1}

变异时，为防止改变染色体的结构和物理性状，减少无效染色体的产生，采取交换变异的方式，具体如下：第一步，将染色体中的“1”删除，并记录其位置；第二步，随机选择染色体上2个基因位，交换二者的位置；第三步，将“1”插入之前记录的位置，得到新的染色体。

3.5 选择操作

选择策略采用轮盘赌和精英保留相结合的方式进行，即：在生产下一代种群时，先采用轮盘赌法从父代中选择一部分染色体进行交叉和变异操作进入下一代种群（选择概率为GGAP）；其他个体则由父代中最优个体直接复制而得。

3.6 算法终止条件

设定算法的最大迭代次数为M，当迭代次数超过M时，算法结束。

4 仿真实验及分析

假设在一次保障任务中，某保障中心担负辖区所有11个单位的物资配送，保障中心仅有4台运输车辆，车辆载重量均为16t，平均行驶速度为50km/h，计算时间时，只考虑车辆到达最后一个需求单位的时间，不考虑物资装卸载和返回时间。已知各单位 物 资 需 求 集 合R={4.6，3.6，6.2，5.2，6.4，7.0，5.4，3.8，8.6，7.4，5.0}，紧迫度集合ω={0.13，0.08，0.06，0.07，0.06，0.09，0.05，0.11，0.12，0.14，0.09} ，保障中心和各物资需求单位之间的距离如表1（1代表保障中心，2～12为各物资需求单位的编号），现要求在符合上述条件下，设计最佳配送方案。

表1 保障中心和各物资需求单位之间的距离（单位：km）

在运用遗传算法进行求解时，设置种群规模N=50，M=500，GGAP=0.9。通过Matlab编程对算例进行求解，得到最佳配送方案，见表2。

表2 物资配送最佳方案表

结果分析：从得到的配送方案看，能够完全满足各运输车辆的最大载重量约束，并且各运输车辆任务完成时间比较一致，在满足物资需求紧迫度方面，需求紧迫的11、2、10、9号单位得到了优先保障，其他单位的配送顺序，也都综合考虑了配送时间和紧迫程度，实现了保障方案的最优化。

5 结语

战时，物资消耗巨大、需求时间紧迫、保障力量有限，科学的物资配送方案是部队保持战斗力的关键。本文针对现有战时物资配送问题中存在的不足，通过建立物资配送问题的数学模型，并运用遗传算法进行了求解，为提升算法的有效性和收敛速度，对初始种群产生方法进行了合理设计，多染色体交叉和变异算子进行了有效改进，使得算法能够快速求出满足要求的最优解，为战时物资配送问题提供了一个行之有效的方法。本文设计的模型和算法也适用于军兵种物资配送、路径寻优以及任务指派等问题。下一步，将进一步对车辆载重量不同、物资需求种类不同等情况的物资配送问题进行研究。