基于改进遗传算法军事应急物流路径优化研究1

《基于改进遗传算法军事应急物流路径优化研究1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、http://www.paper.edu.cn基于改进遗传算法军事应急物流路径优化的研究1高庆春1张立毅2韩应征11太原理工大学信息工程学院，太原（030024）2天津商业大学信息工程学院，天津（300134）E-mail：gqc1984@163.com摘要：军事应急物流是一种特殊情况下的物流。本文根据军事应急物流的特性建立了基于硬时间窗的路径优化模型，并采用改进遗传算法进行求解。分析了初始种群的产生、适应度函数的确定、编码方法和遗传操作算子的选取，给出了算法的运行流程。经计算机仿真表明，与基本遗传算

2、法求解相比，具有更佳的路径选择、更快的配送时间。关键词：军事应急物流；路径优化；遗传算法；硬时间窗中图分类号：TP181．引言近年来，我国突发性公共安全事件频繁发生。无论是03年肆虐全国的非典疫情，还是08年的汶川大地震，不管是08年拉萨市的打砸抢事件，还是09年乌鲁木齐的“七·五”打砸抢烧暴力事件，都造成了大量的人员伤亡和财产损失。在这些突发性事件发生后，军队承担起抢险救灾、平叛暴动和反对恐怖主义的责任，军事应急物流也应用而生。军事应急物流是指用于满足军队平时和战时紧急需要的物流活动，是以各种突发事

3、件所必需的各种应急军事物资为目的，以追求军事效率最大化、灾害损失最小化为目的的特种军事物流活动[1]。在军事行动或灾害发生后都要求将物资和人员快速运送到所需点。如何快速有效地完成物资和人员的配置就是军事应急物流中路径优化的研究内容。遗传算法（GA）是模拟生物在自然界中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，具有较强的全局搜索能力和自适应性，适合解决连续变量函数优化问题和离散变量优化组合问题[2]。但存在早熟和早收敛等问题[3]，为了克服上述缺陷，本文对遗传算法的遗传算子进行了一定改进，

4、并将改进后的遗传算法运于军事应急物流路径优化求解中。2．数学模型的建立2.1建模的基本思想军事应急物流为应急作战和灾后抢险救灾提供物资保障，其要求和目标是时间尽量短。在现代应急作战时，作战双方比拼的就是双方的后勤补给能力和机动能力，谁抢先布置，谁就能迅速做出战役战术的调整，占据优势，掌握时间优势和战场的主动权；在抢险救灾时，灾后72小时是救援工作的黄金救援时间，如果救援人员和救援物资能够尽快到达受灾点，就能够有更多的时间展开救援将损失减少到最小。因此，军事应急物流的路径优化就是使配送时间尽可能短的路径

5、。1基金项目：山西省科技攻关（20090321020）资助课题无论是在应急作战还是抢险救灾的应急情况下，配送车辆的数量是无法满足每个配送点都有一辆车专门进行配送的要求的，又由于各个配送点的重要性和时间性要求是不尽相同的，所以军事应急物流的路径优化必须是在满足各个配送点时间要求的前提下，使整个路径所用时间最短。-6-http://www.paper.edu.cn2.2建立模型基于以上考虑，所建模型是以配送路径的总时间最短作为目标的带硬时间窗的车辆路径规划问题模型。在应急条件下，各种环境条件要比一般情况下

6、的物流复杂得多，这就对军事应急物流提出了许多挑战。如果考虑所有影响路径选择的因素，将会大大增加求解难度。为了突出在应急条件下时间这个重要目标，并且简化模型，降低求解难度，作如下假设：（1）配送中心只有一辆车出发参与配送；（2）所有的配送点之间都存在连接路线；（3）车辆载重量满足所有配送点的要求；（4）每个配送点的时间约束可以提前获取；（5）配送点之间的道路条件都相同，不考虑因道路条件的不同对车辆行驶速度的影响。即一辆车从配送中心出发遍历所有的配送点之后形成的是一个闭合的配送路径。设有个配送点，已知配送

7、点的坐标是，配送中心坐标是，从配送点到配送点的距离为，行驶时间为，配送点的物资必须在前送抵，要求合理安排车辆的行驶路线，使得总配送时间最短。因此建立模型为：S.T．式中，是在无道路障碍影响下的平均速度，、是车辆到达配送点和配送点的时间，是配送点与配送点连接关系有效性的判定。3．改进遗传算法路径优化3.1编码方法路径优化问题一般选用符号编码方法。在本文中采用自然数编码，将配送中心编码为0，配送点依次从1到进行编码。起始位为0，按配送路径通过的配送点编码排列构成一条染色体。如配送路径为：配送中心0—节点4

8、—节点2—节点1—节点3，则该路径编码后的染色体为04213。3.2初始种群初始种群通过随机方式来产生。若已知配送点数目为，初始种群染色体个数为，则产生的种群为行列的种群矩阵，该矩阵每一行都是一条染色体，且第一列元素都为0。初始种群具体的生成方法是，对1到-6-http://www.paper.edu.cn的自然数进行随机排列，并在排列的序列前加元素0产生一条染色体，依次随机生成条染色体赋值给种群矩阵。3.3适应度函数适应度函数是评价群体中每一个个体优劣