军事逆向物流网络优化模型及算法研究

赵方庚

(蚌埠汽车士官学校，安徽 蚌埠233011)

1 引言

军事逆向物流，是指在平战时，从军事力量手中回收不合格或者失去原军事使用价值的军用物资，为满足一定的军事需求，从军事消费点一端返回并加以适当处理，直至最终完成再利用所进行计划、管理和控制的过程［1］。军事逆向物流的网络结构不仅直接影响资源的回收利用，还关系到军事物流保障的效率和效益，科学、合理的网络结构是系统高效运行的重要保证。

随着人们对环保问题的日益关注，军事逆向物流也逐渐成为相关领域的研究热点，但现有研究主要针对军事逆向物流的运作模式［2］、运行机制［3］和管理措施［4］等问题进行定性的分析，基本没有涉及军事逆向物流的网络优化问题。在民用领域，逆向物流网络优化得到了相对较多的关注。王亚楠等［5］通过建立物流逆向配送网络关系的数学模型，利用双向反馈信息加权算法进行网络配送优化计算，达到了提高网络运行效率的目的;高阳和刘军［6］在考虑产品回收量和消费市场需求量不确定的条件下，以第三方物流企业收益和制造商收益最大化为目标，建立了基于第三方回收多周期再制造逆向物流网络模型;吴洪波和谢梦星［7］以各种设施的投资和运营成本之和最小为优化目标建立了随机规划模型，确定了网络中各设施的数量和位置，并对各条路径上的物流量进行了合理分配;王雁凤和黄有方［8］构建了基于双层规划的过期药品逆向物流网络优化模型，并设计了求解该模型的分层遗传算法;Pishvaee 等［9］以运输和开设成本为优化目标，建立多阶段逆向物流网络的混合整数规划模型，并研究了其模拟退火算法;Niknejad 和Petrovic［10］建立了包括产品回收过程的库存与生产规划优化模型，并提出了求解问题的两阶段模糊混合整数优化算法;Roghanian 和Pazhoheshfar［11］建立了逆向物流网络的随机混合整数规划模型，并研究了基于优先级的遗传算法。上述研究虽对商业逆向物流网络建设有较强的指导作用，但都以经济效益为优化目标，无法适用于军事逆向物流环境。此外，在基本逆向物流网络优化算法方面，Pishvaee等［9］应用的模拟退火算法虽取得了较好的优化结果，但在组合优化领域，模拟退火算法并不是最高效的智能优化方法，其计算效率仍有一定的提高空间。基于此，本文建立了军事逆向物流网络优化的数学模型，并研究了求解模型的遗传算法。

2 军事逆向物流网络优化模型

2.1 问题描述

本文以军事逆向物流中的常见形式装备维修保障为例，研究其逆向物流网络优化问题。装备维修逆向物流是一个多阶段物流网络问题(如图1 所示)，其网络节点由部队用户、收集/检测点、维修点和报废点组成。其中，收集/检测点负责从部队用户处收集故障装备或器材，经过必要的检测后，将故障装备或器材分为可修复件和不可修复件;然后可修复件被送往维修点进行维修，不可修复件则送往报废点进行相应的报废处置。问题中，收集/检测点、维修点和报废点均有能力约束。逆向物流网络优化的目的是选择合适的收集/检测点，并确定网络中各节点间的装备或器材流量。

图1 装备维修逆向物流网络结构示意图

为简化研究，在模型中作如下假设:①从部队用户返回的所有装备或物资都必须收集;②部队用户的位置固定且已知;③维修点、报废点的数量、位置和能力已知。

2.2 数学模型

模型中参变量及符号定义为:I为候选收集/检测点集合;J为已知的修理点集合;K为已知的报废点集合;L为已知的部队用户集合;r为平均报废率;dl为部队用户l返回的物资数量;fi为开设收集/检测点i的固定成本;si为收集/检测点i的安全系数;cfli为从部队用户l到收集/检测点i的单位运输成本;cmij为从收集/检测点i到维修点j的单位运输成本;cdik为从收集/检测点i到报废点k的单位运输成本;pfi为收集/检测点i的能力约束;pmj为维修点j的能力约束;pdk为报废点k的能力约束。Xli为从部队用户l到收集/检测点i的返回物资数量;Zij为从收集/检测点i到维修点j的可修件数量;Wik为从收集/检测点i到报废点k的不可修件数量;Yi为变量，如果在位置i开设收集/检测点，则Yi =1，否则Yi =0。

模型中，目标函数(1)为最小化逆向物流系统的总经济成本，其中第一项为收集/检测点的开设成本，第二项为物资从部队用户到收集/检测点的总运输成本，第三项为可修件从收集/检测点到维修点的总运输成本，第四项为不可修件从收集/检测点到报废点的总运输成本;目标函数(2)为最大化系统的军事效益，使系统中物资的安全性最大;约束(3)用以确保部队用户返回的所有物资都被收集;约束(4)和(5)用以保证收集/检测点的流量平衡;约束(6)用以确保部队用户返回的物资只被送往开设的收集/检测点，且不超过收集/检测点的能力限制;约束(7)和(8)用以保证送往维修点和报废点的物资数量均不超过它们的能力限制;约束(9)和(10)定义了变量的取值范围。

在上述军事逆向物流网络优化模型中，目标函数(2)是求安全性的最大值，为便于计算，在不影响优化效果的前提下，可将该目标修改为求目标函数最小值的情况:

对上述多目标优化模型，本文采用如下方法将之转化为单目标优化模型:

3 军事逆向物流网络优化模型的优化算法

由前可知，军事逆向物流网络优化模型是一个混合整数规划模型，变量、约束众多，传统的精确算法求解规模较大的此类问题时效率较低，难以满足解决实际问题的需要。为此，本文采用遗传算法对问题进行求解。

3.1 算法流程

应用遗传算法求解军事逆向物流网络优化问题首先初始化所用到的参数;然后生成pop_size 个可行解构成初始种群，并对各可行解进行适应度评估;接着利用各遗传操作算子进行迭代搜索，直到满足预定的终止条件算法结束。在每步迭代过程中，算法按照轮盘赌策略从种群中随机地选择两个个体，并将个体进行交叉和变异，得到新的子个体。上述遗传操作过程将进行pop_size/2 次，得到的子个体在进入种群的同时，种群中较差的(适应度低的)个体将被淘汰，以保持种群规模不变。在每次迭代的最后，算法还将在种群中的最佳个体上应用局部搜索过程，以加速算法收敛。另外，算法的终止规则设定为迭代固定的次数。

3.2 染色体表示及解码方法

图2 染色体表示示例

表1 解码过程及结果

本文采用基于优先级的编码方法构造军事逆向物流网络优化模型的解。染色体由［L］+3［I］+［J］+［K］个正整数组成，其中［L］、［I］、［J］、［K］分别表示部队用户、候选收集/检测点、维修点和报废点的数量，各数字则分别表示对应节点的优先级。图2 所示为一染色体示例，该示例由4 个部队用户、3 个候选收集/检测点、3 个维修点和2 个报废点组成。染色体分为三部分，第一部分表示部队用户和候选收集/检测点之间的物资供给关系，第二部分表示候选收集/检测点与维修点间的物资供给关系，最后一部分则表示候选收集/检测点与报废点间的物资供给关系。

对于上述基于优先级的染色体表示方法，需要将之进行解码，以获得各节点之间的物资供给关系。为便于说明，以图3 所示的单级染色体为例，介绍其解码方法。图3 中，(a)为染色体编码，(b)为供应方和需求方之间的运输成本，(c)为供需量及解码后得到的物资供给关系(箭头表示流向，其上数字表示流量)。具体解码过程为:首先选择优先级最高的节点，图3(a)中对应为节点(供应节点1);然后查找成本矩阵，找出该节点向对应最低运输成本(min{13，17，16}= 13)所指向的节点(需求节点1);再根据两个节点的供需量，在二者之间安排最大可能的物资供给(min{350，600}=350);继续在染色体中寻找次高的优先级，并按上述过程安排物资流。如此反复，直至所有需求都得到满足，即完成解码过程。图3 所示算例，其解码运算过程及结果见表1。

图3 染色体解码方法示意图

3.3 适应度评估及初始种群的生成

染色体的适应度反映了其所表示的解的质量。在本文算法中，公式(12)所定义的目标函数被用于评价染色体的适应度。

初始种群中的个体均采用随机生成的方法，即对染色体中的各级分别随机生成长度为［L］+［I］、［I］+［J］和［I］+［K］的数字串，经解码算法运算后，计算相应的适应度值。

3.4 交叉算子

选择算子得到的两个父代个体将进行交叉，以产生新的子个体。本文对各部分染色体均分别应用相同的单点交叉方法，交叉所得到的两个子个体中，选择其中较优的子个体进入新种群。

3.5 变异算子

为避免遗传搜索过程过早的陷入局部最优解，算法以一定的概率进行变异。变异方法较为简单:首先在各段染色体中均随机选择两个编码位，然后分别交换它们的位置，即可得到变异后的个体。

3.6 局部搜索过程

在每次迭代的最后，算法将应用局部搜索过程对种群中的最佳个体进行优化，以加快算法收敛速度。局部搜索过程应用2－opt 的思想，分别对各段染色体的任意两个编码位进行交换操作，算法将尝试所有可能的编码位组合，以期发现更优的个体。

4 计算实验及分析

4.1 算法实现及参数设置

本文所提出求解军事逆向物流网络优化问题的遗传算法利用C 语言在Visual C ++.net 环境中实现。算法中的参数设置如下:种群规模pop_size =30，交叉和变异概率分别设为0.8 和0.1，算法终止条件为迭代300 代。

4.2 算例及计算结果

由于没有可用的军事逆向物流网络优化算例，本文自行设计了6 个算例，算例中，部队用户的规模分别是{50，60，70，80，90，100}，候选收集/检测点的数量均为8 个，其开设固定成本(fi =1000)均相同，各候选收集/检测点的安全系数si ={0.05，0.08，0.1，0.12，0.15，0.18，0.22，0.1}，维修点和报废点的数量均分别为5 和3，各节点的位置坐标均在区间［0，100］内随机生成，节点之间的运输成本为相应节点之间的欧几里得距离，各部队用户的返回物资量为区间［1，10］范围内的随机数，各收集/检测点的能力上限各维修点的能力上限各报废点的能力上限pdk平均报废率r =0.2。

应用所研究的算法，对上述各算例均独立运算10 次，得到的计算结果见表2。其中，第三列给出了10 次运算中得到的最佳解的目标函数值，第四列为10 次运算结果的平均目标函数值。

为验证算法性能，应用所研究的遗传算法求解了文献［9］中的15 个有代表性的逆向物流网络优化基准算例(算例基本情况见表3)，并将本文算法所得10 次独立运算的平均结果与文献［9］中模拟退火算法的优化结果进行了比较(见表4)。从表4可知，在15 个算例中，本文算法求得的13 个算例的平均结果优于文献［9］中算法的计算结果。

表2 计算结果

表3 基准算例基本情况［9］

表4 本文算法与文献［9］中算法的平均计算结果比较

11 654823 659542 0.715 12 1112097 1115163 0.275 13 1573641 1582957 0.589 14 2189368 2205633 0.737 15 3079756 3098121 0.593

5 结束语

优化的网络结构是军事逆向物流系统高效运行的关键。本文建立了军事逆向物流网络的优化模型，研究了求解模型的遗传算法并完成了算法程序设计。为验证算法性能，应用本文算法求解了文献［9］中的基准算例，实验结果表明:所研究的算法具有比文献［9］中的算法更高的精度。

［1］ 毛军凌.军事逆向物流及其发展策略研究［D］.北京:后勤指挥学院，2007.

［2］ 姜玉宏，樊玉强，颜华.基于物联网技术的军事逆向物流系统研究［J］.军队采购与物流，2012(4):65 -67.

［3］ 张义桂，黎明.军事逆向物流运行机制浅析［J］.军队采购与物流，2011(3):64 -66.

［4］ 任岚燕，何婧.加强军事逆向物流管理，建设资源节约型后勤［J］.军队采购与物流，2009(3):65 -67.

［5］ 王亚楠，司玲玲，杜海艳.基于双向反馈信息的逆向物流网络优化方法［J］.计算机仿真，2012，29(10):162 -164.

［6］ 高阳，刘军.基于第三方回收再制造逆向物流网络设计［J］.计算机系统应用，2013，22(7):16 -21.

［7］ 吴洪波，谢梦星.汽车再制造逆向物流网络模型研究［J］. 科技与管理，2014，16(2):80 -84.

［8］ 王雁凤，黄有方.考虑居民选择行为的过期药品逆向物流网络设计［J］.华中师范大学学报(自然科学版)，2015，49(1):52 -59.

［9］ NIKNEJAD A，PETROVIC D. Optimisation of integrated reverse logistics networks with different product recovery routes［J］. European Journal of Operational Research，2014，238(1):143 -154.

［10］ ROGHANIAN E，PAZHOHESHFAR P. An optimization model for reverse logistics network under stochastic environment by using genetic algorithm［J/OL］. ［2014 -09］http://dx. doi.org/10.1016/j.jmsy.2014.02.007.

［11］ PISHVAEE MS，KIANFAR K，KARIMI B. Reverse logistics network design using simulated annealing［J］. International Journal of Advanced Manufacturing Technology，2010，47:269-281.