当前位置：文档之家 › 基于遗传算法的军事运输路径优化_石玉峰

基于遗传算法的军事运输路径优化_石玉峰

  • 格式：pdf
  • 大小：137.57 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

基于混合编码遗传算法的战时军事物流调运协同优化问题研究

基于混合编码遗传算法的战时军事物流调运协同优化问题研究
关键词：调配协同；运送优化；中转作业；自修复；混合编码遗传算法 中图分类号：Ｅ９１１；Ｅ１４ 文献标志码：Ａ 文章编号：１６７２－８２１１（２０１８）０１－００４４－０８
１ 引言
现代战争是高技术条件下的局部战争，后勤保 障要求适时、适量、适地，因此构建战时军事物流保 障网络时既要注重保障能力，又要兼顾保障效率。 在传统后勤补给和即时后勤补给战略基础上，混合 后勤补给战略［１］ 中的战时军事物流保障网络是由 后方仓库、前沿补给基地、前线补给点三个层级组 成。 前沿补给基地是在战役方向建立的主要后勤 补给基地，通常负责较大作战区域范围内的物资保 障；前线补给点是在战术中心附近建立的物资补给 中转站，通 常 负 责 较 小 作 战 区 域 范 围 内 的 物 资 保 障。 在这个网络中，物资流动的起点是后方仓库， 终点是前线补给点。 战时环境下，军事物流调运业 务需要根据各前线补给点的物资需求，同时考虑前 沿补给基地、后方仓库的现存物资储量和调运能 力，通过调整控制路径的选择以及物资的调配、运 送计划，实现节点之间调运任务的协同优化。
２ 问题描述与分析假设
２．１ 问题描述 为了更直观地描述问题，将战时军事物流保障
网络简化为三级网络（拓扑结构如图 １ 所示），这个 三级网络中存在 Ｉ 个供应点（ 代表后方仓库）、Ｊ 个 中转点（代表前沿补给基地） 和 Ｋ 个需求点（ 代表 前线补给点）。 该问题包含两个阶段：物资由供应 点向中转点调配并在中转点进行物流作业阶段、从 中转点向需求点运送阶段。
２０１８ 年 ３ 月 第 ３２ 卷第 １ 期
军事运筹与系统工程
Ｍｉｌｉｔａｒｙ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ ａｎｄ Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ
Ｍａｒ． ２０１８ Ｖｏｌ．３２ Ｎｏ．１

基于遗传算法的物流配送车辆路径优化问题

基于遗传算法的物流配送车辆路径优化问题

10.16638/ki.1671-7988.2016.06.002基于遗传算法的物流配送车辆路径优化问题苏楠，鹿静，王栋梁（长安大学汽车学院，陕西西安710064）摘要：在当代社会，物流越来越受到各国的重视，是企业创造利润的又一有效途径。

文章主要研究在物流配送中的一个方面，也就是车辆路径优化问题，主要采用遗传算法进行计算。

依据遗传算法，建立车辆路径优化的数学模型，配送路径的限制条件。

在用遗传算法进行计算时，采用自然数序列进行编码，在选择时采用最优个体保留策略和轮盘赌法，变异时不只是单一的变异，而是两位基因同时变异，最终求得最优解。

我国物流起步较晚，不及一些发达国家，所以有很大的进步空间。

关键词：物流；路径优化；遗传算法中图分类号：U468.8 文献标识码：A 文章编号：1671-7988 (2016)06-04-03Routing optimization problem of logistics distribution vehicle basedon genetic algorithmSu Nan, Lu Jing, Wang Dongliang( College of automotive engineering, Chang'an University, Shaanxi xi’an 710064 )Abstract:In contemporary society, the logistics gets more and more national attention ,it is another effective way for enterprises to create profits.This paper studies one aspect of the logistics and distribution, which is the vehicle routing problem, mainly using genetic algorithms to calculate. The mathematical model of VRP is built on genetic algorithm with distribution route restrictions.When calculated with the genetic algorithm, the natural number sequence is encoded,the best individual retention policies and roulette method is used on piled with not just a single mutation, but simultaneously two gene mutation, and ultimately get the optimal solution.China's logistics start late, less than some developed countries, so there is great potential for improvement.Key words: Logistics; Route optimization; Genetic AlgorithmCLC NO.: U468.8 Document Code: A Article ID: 1671-7988 (2016)06-04-03引言遗传算法是来源于达尔文的进化论，模拟生物的一代代繁衍，进化。

军事运输的模糊时间路优化

军事运输的模糊时间路优化

军事运输的模糊时间路优化
石玉峰;任怡
【期刊名称】《甘肃科学学报》
【年(卷),期】2005(017)001
【摘要】基于模糊规划原理,提出了军事运输的模糊时间最优路问题;建立了模糊机会约束规划模型和模糊相关机会规划模型;设计了基于遗传算法的求解步骤,并处理了运输中的"必经点"和"禁止点"问题,并给出了算例.
【总页数】3页(P101-103)
【作者】石玉峰;任怡
【作者单位】西南交通大学,交通运输学院,四川,成都,610031;四川师范大学,草堂校区,四川,成都,610071
【正文语种】中文
【中图分类】E919.1;O159
【相关文献】
1.基于多模式时间最短的公铁联合军事运输路径优化 [J], 吴洋;张艳萍;李遂汝
2.基于模糊多目标决策理论的军事运输路径优化研究 [J], 石玉峰;门志强
3.公路军事运输线路中断下运输时间优化 [J], 尹旭日;吴更生
4.模糊粒子群优化算法的第四方物流运输时间优化 [J], 卢福强;刘婷;杜子超;毕华玲;黄敏
5.基于模糊信息优化技术的一个新模糊时间序列模型 [J], 薛晔
因版权原因，仅展示原文概要，查看原文内容请购买。

遗传算法的物流系统路径优化

遗传算法的物流系统路径优化

遗传算法的物流系统路径优化
华欣
【期刊名称】《电脑编程技巧与维护》
【年(卷),期】2009(0)S1
【摘要】遗传算法可以很好地解决物流配送路径优化问题。

但是由于遗传算法交配算子操作可能会使最好解遗失,所以将遗传算法和模拟退火算法结合来解决这一问题。

实验结果表明,用有记忆功能的遗传模拟退火算法求解物流配送路径优化,可以在一定程度上解决上述问题,从而得到较高质量的解。

【总页数】3页(P70-71)
【关键词】物流配送;遗传模拟退火算法;模拟退火算法;路径优化
【作者】华欣
【作者单位】空军航空大学基础部计算机教研室
【正文语种】中文
【中图分类】F252;TP18
【相关文献】
1.基于遗传算法的电子商务物流车辆路径系统的优化 [J], 朱小社;邱春红
2.基于改进遗传算法的冷链物流路径优化 [J], 袁紫微
3.物流配送中烟花算法结合遗传算法的异质车队路径优化方法 [J], 庞凌
4.基于聚类—遗传算法的物流配送路径优化研究 [J], 高涵; 杨杰; 张军
5.基于遗传算法的冷链物流配送路径优化研究 [J], 郑义彬; 邱兴宇; 孙源泽; 刘立博
因版权原因，仅展示原文概要，查看原文内容请购买。

基于遗传算法的后勤运输车路径规划

基于遗传算法的后勤运输车路径规划
束条件 可以如式（ ） （ ） ４ 、５ 所示进行描述 。
∑ｑ ≤Ｑ （） Ｂ
因子 。 ・
（） ４
其 中 ： 为每辆 配送车辆 的载运上 限值 ；（・ Ｑ ｇ ）为需求量计算
。
｛ ≤ 茎
（ ５ ）
图 ２ 基 于遗传算 法的车辆路径优化 流程
其中 ： 为平均车速 ； Ｔ为配送任务所要求 的最大 时间限度 ； 为
８ ２
Ｓ＝ ｛０ 曰 Ｂ … ， ， １ Ａ ，“，控， Ｂ Ａ ｝
四 川 兵 工 学 报
（） ２ 最大代数 Ｇ＝１０ ０ 交叉概率 Ｐ ｃ＝１０ ． 变异概率 Ｐ ｍ＝ ． ０１
ｈｔ ：／ｃ ｇ ｊ ｌ ｒ． ｏ ／ ｔ ／ ｓｂ ．Ｏ ＇ ｖ ｃ ｍ ｐ ＵＳ ｅ
其中： ｎ为需求 点 的数 目； 。为 运输 起始 点 ； 为 运输 终 止点 ； Ａ Ａ 为第 ｉ 个需求 点。
Ｄｌ ＝ 【 １ １ ２ １ ９ １ １ ４ ６ １ ３ ６ ４
和运输时间。
参考文献 ：
Ｄｏ ＝
［ ］ 祝 崇隽 ， 民， １ 刘 昊澄． 供应链 中车辆路径 问题 的研 究进展及 前景 ［ ］ 计算机集成制造 系统 ，０ １ １ （ ） １ ６ Ｊ． ２０ ，１ ７ ： — ［ ］ 朗茂祥 ， 思继． ２ 胡 用混合遗传 算 法求解物 流配送路 线优化
配送路线 的优化 从数学的角度属于 Ｎ ．ａ Ｐｈｒ ｄ问题 ， 随着节点 数量增多 的呈 现维数灾现象 ， 因此传统 的枚举法往往 并不适 用 。
另外在实 时战略实施过 程 中 ， 化算 法必 须要求 时效 性 和通用 优
性， 能够 实现路径选取方案 的动态优 化管理 Ｊ 。
收 稿 日期 ：０ １ ２—１ ２ １ —１ １

基于遗传算法的物流配送路径优化技术研究

基于遗传算法的物流配送路径优化技术研究

基于遗传算法的物流配送路径优化技术研究物流配送是指将货物从供应商处运送到客户处的过程，它是现代供应链管理中重要的环节之一。

在日益复杂和竞争激烈的商业环境下，高效的物流配送路径成为企业获取竞争优势的关键。

然而，不同的运输线路和运输方式使得物流配送路径的选择具有挑战性。

基于遗传算法的物流配送路径优化技术为解决这一问题提供了一种有效的方法。

遗传算法是一种模拟生物进化过程的优化算法。

它通过模拟自然选择、交叉和变异等操作，逐步优化问题的解。

在物流配送路径优化中，遗传算法可以用来寻找最优的路径组合，以降低配送成本、缩短配送时间、提高配送效率。

首先，物流配送路径优化问题可以被建模为一个旅行商问题（TSP）或车辆路径问题（VRP）。

TSP是指旅行商沿着若干城市之间的路径依次访问每个城市，并返回出发地的问题。

VRP是指一组拥有相同容量的车辆从中心点出发，依次访问若干客户点并返回中心点的问题。

这两个问题都是NP难问题，传统的解法往往耗时且无法保证得到全局最优解。

而基于遗传算法的优化技术则可以在较短的时间内找到较优的解。

其次，遗传算法的基本步骤包括个体编码、初始化种群、适应度评估、选择操作、交叉操作和变异操作。

个体编码是将解决方案表示为染色体的过程。

对于TSP问题，可以使用二进制编码或城市编号序列编码。

对于VRP 问题，可以使用二进制编码或路径编号序列编码。

初始化种群是产生初始解的过程，一般使用随机生成的方式。

适应度评估是根据问题的目标函数，计算每个个体的适应度值。

选择操作是通过一定的策略，从当前种群中选择优秀个体用于交叉和变异。

交叉操作是将两个个体的基因信息进行交换，产生新的个体。

变异操作是对个体的某一位置进行基因信息的变换。

通过迭代执行上述步骤，遗传算法能够不断优化解空间，直至找到较优的解。

最后，基于遗传算法的物流配送路径优化技术还可以结合其他技术手段，进一步提高优化的效果。

例如，可以将遗传算法与模拟退火算法相结合，通过模拟退火操作来增加算法的全局搜索能力。

基于遗传算法的军事物流中心选址模型研究

基于遗传算法的军事物流中心选址模型研究1. 引言在现代军事作战中，物流的效率和准确性对于保障军队的战斗力至关重要。

军事物流中心的选址是军队物流系统中的关键环节之一。

本文旨在研究基于遗传算法的军事物流中心选址模型，以提供科学的决策依据。

2. 军事物流中心选址的意义军事物流中心的选址决策会影响到军事行动的成功与否。

选址过程需要综合考虑多个因素，如地理位置、交通条件、资源配备等。

合理的选址决策可以提高后勤保障的效率，最大程度地减少后勤时间成本与资源浪费。

3. 遗传算法的原理遗传算法是一种模拟生物进化过程的优化算法。

它通过模拟基因的遗传、交叉和变异等操作，以求得问题的最优解。

在军事物流中心选址模型中，遗传算法可以用于搜索最佳选址方案。

4. 军事物流中心选址模型构建（1）确定军事物流中心选址的目标函数，如最小化总运输成本、最大化保障效果等。

（2）建立地理数据和交通数据的空间数据库，包括地理位置、道路、交通网络等信息。

（3）设定军事物流中心选址的约束条件，如资源配备、安全要求等。

（4）使用遗传算法对选址模型进行求解。

5. 遗传算法在军事物流中心选址中的应用（1）编码与初始化：将可能的选址位置编码为遗传算法的染色体，并进行初始化。

（2）适应度计算：根据目标函数和约束条件计算每个染色体的适应度。

（3）选择：采用轮盘赌算法或锦标赛选择法，选取适应度较好的染色体作为父代。

（4）交叉与变异：对选出的染色体进行交叉和变异操作，生成新的子代染色体。

（5）代替：用子代替代父代，继续迭代直到满足停止条件。

6. 案例分析通过收集军事物流中心选址的实际数据，并建立相应的数学模型，利用遗传算法对其进行求解，可以得到最佳的选址方案。

模型的求解过程可以结合现实情况进行优化调整，得出更加切合实际的结果。

7. 结论与展望本文研究了基于遗传算法的军事物流中心选址模型，通过该模型可以辅助军队在选址过程中做出科学决策，提高后勤保障的效率和准确性。

基于遗传算法的车辆运输路径优化研究

基于遗传算法的车辆运输路径优化研究在现代交通运输领域中，路线优化问题一直以来都是一个关键的难点。

尤其是对于车辆运输来说，如何在保证安全和效率的前提下，找到最优的路线方案，一直是业界和学术界研究的热点问题。

近年来，随着遗传算法这一优秀的优化方法的发展和应用，基于遗传算法的车辆运输路径优化研究也得到了广泛关注和研究。

本文将以此为主题，探讨基于遗传算法的车辆运输路径优化研究相关问题。

一、遗传算法的基本概念在深入探讨遗传算法在车辆运输路径优化中的应用前，有必要先了解遗传算法的基本概念。

简单来说，遗传算法是一种基于生物遗传学的模拟优化方法，它通过模拟进化过程，寻找问题的解决方案。

遗传算法是由三个基本运算组成的：选择、交叉、变异。

其中，选择算子通过适应度函数来确定适应度高的个体，交叉算子通过交换两个个体之间的某些属性信息，生成新的个体，变异算子则是通过改变个体中的某些表现型信息，来产生新的个体。

二、车辆运输路径优化问题车辆运输路径优化问题可以简单地理解为，对于给定的起点、终点和其中间的多个节点，如何找到一条最短的路径，使得总的运输成本最小。

车辆运输路径优化问题是一个NP难问题，因此在实际应用中，往往需要采用一些优秀的算法来解决这个问题。

三、遗传算法在车辆运输路径优化中的应用基于遗传算法的车辆运输路径优化原理非常简单，就是将车辆的行驶路线看作一个遗传个体，通过遗传算法的选择、交叉、变异等操作，不断优化路线方案，最终找到符合要求的最优路径。

首先，我们需要定义适应度函数。

适应度函数是用来度量某个个体的优良程度的函数。

对于车辆运输路径优化问题来说，适应度函数可以用总的运输成本来表示。

这个成本包括了车辆的油费、路桥费用、人员工资等等直接和间接的成本因素。

接下来，我们需要初始化一个种群。

这个种群包含了多个个体，每个个体代表了一种可能的车辆路线方案。

在初始化时，我们需要为每个个体设置随机的初始值，这样就可以产生多个不同的路线个体。

基于遗传算法的军事物流运输计划

２ ０１ ５拄
海 军 航 空 工 程 学 院 学 报
Ｊ ｏ ｕ ｒ ｎ ａ ｌ ｏ ｆ Ｎａ ｖ ａ ｌ Ａｅ ｒ ｏ ｎ ａ ｕ ｔ ｉ ｃ ａ ｌ ａ ｎ ｄ Ａｓ ｔ ｒ ｏ ｎ ａ ｕ ｔ ｉ ｃ ａ ｌ Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ
２０资分别 以一定规 格的运输 箱托运 ） 。保 障基地 首先要
性， 则此算法一定 可以获得很好 的求解结果 。 车 辆路径 问题 （ Ｖ ｅ ｈ ｉ ｃ ｌ ｅ Ｒ ｏ ｕ ｔ ｉ ｎ ｇ Ｐ ｒ ｏ ｂ ｌ ｅ ｍ， Ｖ Ｒ Ｐ） 是
近２ Ｏ 年来 运筹 学 、 图论 、 网络分 析 、 应 用数学 、 计算 机 应用及 交通运 输等学科 研究 的一 个热点 问题 ， 它 已被
标优 化模型 。通 过改进遗传算法 对模型求解 ， 得 到了较为满意 的结果 ， 可以在满足 多车型多 品种货物 配送约束 的
条件下 ， 实现运输 车辆最少 、 车辆满 载率高 、 车辆运输路 径最短的 目标 。
关键词 ： 车辆装载 ； 车辆路径 ； 遗 传算法 ； 多 目标优化
中 图分 类 号 ： Ｅ ２ ３ 文献标志码 ： Ａ
合 车型 的 车厢 中 ， 使 得满足 配 送要求 的同时 ， 让 车辆
装载率 达到最 高ｕ 。实际上 ， 车辆装载 问题 、 装箱 问题
或背包 问题 等都是裁剪 与装填 问题 的一 个分支 ， 剪裁 问题与 装填 问题 也称 为布 局 问题 。 】 。求 解算 法 主要
有： 数学 规划 法 （ 包括 分枝 定界 法 、 动态规 划法 、 整 数
划 与控 制 ， 形成从 市 场到 战场 紧密 的物 资保 障连 接 ， 满 足信 息化 条件 下军 事行 动适 时 、 适地 、 适量 的精 确 需求 保 障 ， 是军 事后 勤保 障 的重要组 成部 分 ， 是遂 行 作 战任 务 的关键 因 素之一 。车辆装 载 和车辆 路径 问

遗传算法在多车型军备物资配送路径优化中的应用


本 文中所要研 究 的是 多次 配送 下 ， 车型 、 一 配送 多 单 中心、 多个离散军备 需求地 点 的物资 配送路 径选择 与优化 问题 ， 每个军备需求点都 有 固定 物资需 求量及 相应 的服务 时 间区段 ， 拟启 用不 同容 量类 型最 少 的 车辆总 数 ， 配送 从
备 物质 配送 车 辆进 行 优化 调度 ， 而这 一 问题 属 于典 型 的
Ｖ Ｐ Ｖ ｈｃ ｏｔ ｇ ｒｂｅ ｓ 问题 ． Ｒ （ ｅｉｌ Ｒ ｕｉ ｏ ｌ ） ｅ ｎＰ ｍ
中心 出发经 过 既定 的线路 后 返 回 ， 且要 求 车辆 为 非满 载
（ 装载货 运量小于车辆容量 ） 到达各 个需求 点时 间应 尽可 ， 能满 足对 应 点 时 间窗要 求 ， 车 辆不 能按用 户 的要 求 到 若
摘要 ： 结合部 队物流客观实 际和可能承担的军备物 资保 障任务 ， 构建 了带 有软时 间窗 的多车 型军备 物资配 送线 路 Ｍ Ｒ Ｓ Ｗ 双层 优化模型 ， Ｖ ＰＴ 上层 为多车型线路优化模型 ， 下层为配车方 案整数规 划模型． 通过遗 传算法算 子设 计 以及双层优化流程设计求 解 ＭＶ Ｐ Ｔ 模型 ， ＲＳＷ 并给 出 了具 体应 用算例 ， 用结果 证 明该 双层 优化模 型及遗 传 应
算法 的有效性 和合 理性 ， 能迅速 为后 勤部 队军备物资配送路径选择提供 决策依据． 关键词 ： Ｒ 软时 问窗 ； Ｖ Ｐ； 双层优化 ； 遗传 算法 ； 军备保 障运输
中 图分 类 号 ： Ｐ０ ． Ｔ ３ １６ 文献 标 识 码 ： Ａ 文 章 编 号 ：０ ６— ７７ ２ １ ）２— ０ ３— ４ １０ ０ ０ （０ ０ ０ ０ １ ０
１ １ 军 备 物 资 配 送 问题 分 析 ．
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

基于遗传算法的军事运输路径优化
石玉峰1 , 粟 实2 , 彭其渊 1
(1. 西南交 通大学交通运输学院 , 四川 成都 610031;2. 中铁集装箱运输有 限责任公司 哈尔滨分 公司 , 黑 龙江 哈尔滨 161000)
摘 要 :在建立军事运输路径优化模型的基础上 , 设计了求解最小广义权路径的遗传算法 ;针对军事运输中 的必 经点和节点保序问题 , 构造了特殊的染色体编码规则和交叉 、变异的处理方法 ;提出通 过对初始种群染色体 的预 处理来提高算法的性能 . 最后 , 进 行了算法的比较实验和结果分析 , 以验证算法的可行 性和有效性. 关键词 :军事运输 ;最优路径 ;遗传算法 ;必 经点 ;节点保序 中图分类号 :U 116. 2 文献标识码 :A
F ti =W tm in W/ ti ,
(5)
其中 :W t m in为第 t代种群中染色体广义权值中的最小者 , 即最优者. 如果染色体适应度函数值越大 , 则路径
越好 , 反之则越差.
2. 4 染色体选择
采用改进的轮盘赌选择法 [ 3, 4] . 在选择新个体时 , 首先在当前代的可行个体中选择最佳个体直接进入
第 2期
石玉峰等 :基于遗传算法的军事运输路径优化
2 43
基因长度 , 以及对中间部分基因节点位置做随机排列来得到初始种群中的染色体. 由于路径的好坏与基因
的排列顺序有关 , 为了提高遗传算法的收敛性能 , 本文提出在种群初始化时应对染色体做预处理 , 当检查
发现染色体中的两相邻基因生成的无效弧数 (没有实际的弧相连 )大于该路径总弧数的 60%时 , 则该染色
本文中运用遗传算法来设计军事运输路径优化算法.
2 路径优化的遗传算法设计
遗传算法[ 3] 是由 H o lland等于 20世纪 70年代创立的 , 期间经过 Bake r, G o ldberg等人的不断发展和 完善 , 现已应用于许多领域. GA s是一种以自然选择和遗传理论为基础 , 将进化论中的适者生存规则与同 一群染色体的随机信息交换机制相结合的搜索算法. 按以下算法步骤通过不断迭代 , 求得最优解. 2. 1 种群初始化 本文中采用字母与整数混合编码方式构造染色体 , 染色体的基因是网络的节点 , 而节点的排列顺序代 表着起点到终点的路径[ 4, 5] . 设路网 G 的节点数为 N , 则染色体的基因数也设定为 N. 为了解决必经点问 题 , 本文中设计了这样的染色体基因组成方式 :第一个为起点 “O”;接下来是中间节点 , 分为两部分 , 一部 分由必经点集合 VK 中的全部节点构成 , 设共有 m 个节点 , 另一部份为 k 个其它节点组成 , 0≤k ≤N -m - 2;然后是终点 “D”. 如果 k <N -m - 2, 则在 “D”点后补 “ 0”, 使基因总数保持为 N. 这样 , 染色体中实际 的有效基因长度 , 即从 “O”到 “D”为 m +k +2. 通过产生 [m +2, N ] 之间的随机整数来确定染色体的有效
下一代 (若有多个 , 则随机选取一个 ), 然后对其它个体采用轮盘赌方式进行选择 , 如果在当前代中没有可
节点集合 Vb 与前节点集合 Vf. (2)路径优化模型 . 在建立完网络图后 , 军事运输路径优化问题转化为搜索具有最小广义权的网络
优化问题 , 同一般的最短路径优化问题类似 , 其数学模型为 :
F (P 0 )
=m in P
WP
,
WP = ∑ w(i, j) +∑ w(l);
(i, j)∈ AP
Ab stract:On the basis o f establish ing the optim al m ode l of m ilitary transportation routes, a gene tic algorithm w as designed to ob tain the route w ith a m inim um genera lized w eigh.t T o so lve the prob lem s of “ necessity-nodes”, i. e. , the nodes a m ilitary transpo rta tion route must pass, and orde r preserv ing of nodes, the ru les of coding and the m ethods of cro ssover and mu tation w ere constructed. Initial chrom osom es w ere predisposed to im prove the efficiency of th is algo rithm. In the end, com parative experim ents w ere perform ed and the experim en tal resu lt w as ana ly zed so as to show the feasibility and effectiveness of the algo rithm. K ey w ord s:m ilitary transportation;op tim al route;genetic algo rithm;necessity-node;node orderp reserving
l∈ VP
VK VP ,
(1) (2) (3)
如果
i ∈ Vb ∉ VP , 则
j∈
V
i f
∉
VP .
(4)
其中 :式 (1)为目标函数 ;式 (2)为路径 P 的总广义权定义 ;式 (3)表示必经点集合一定包含于路径的节点
集 VP 中 ;式 (4)为节点保序约束 , 即有后节点位于路径上 , 则至少存在一个对应的前节点也位于路径上 ; w (i, j)为弧 (i, j)的广义权值 ;w (l)为节点 l的广义权值 ;AP 表示路径 P 中的弧集 ;VP 表示路径 P 中的节 点集合 ;P0 表示所求的最优路径.
1 模型建立
(1)运输网络图 .根据军事运输任务建立从起点 “O”到终点 “D”的运输网络图 G =(V, A, W ), 其中 : V代表节点集 (交通枢纽 、城镇 、军供站 、交叉路口或特殊节点等 ), A 代表弧集 (路段 ), W 表示节点和弧的
收稿日期 :2004-03-22 基金项目 :空军科研项目 (K JZ03452) 作者简介 :石玉峰 (1973 - ), 男 , 工程师 , 博士研究生 , 研究方向为军事运输优化 、决策支持系统 .
体无效 , 需重新生成.
2. 2 保序处理
对每个染色体进行节点保序检查 , 如果有基因点或基因点对没有满足要求 , 则视情况进行处理. 如果
需保序的两个基因顺序错误 , 则可对需保序的两节点互换位置 , 或直接删除这两个节点 (必经点除外 ), 并
在 “D”后增加两个 “0”基因. 如果缺少保序的前节点 , 则可以删除保序后节点并在 “D”后增加一个 “0”基
因 , 或当染色体从 “O”到 “D”的有效基因长度小于 N 时增加配对的保序前节点并删除 “D”后的一个 “0”
基因.
2. 3 适应度函数
对于第 t代种群中的每一染色体所代表的路径 , 用式 (2)求出其对应的广义权 W ti , 其中 i =1, 2, …, N ,
如果染色体中存在没有实际弧相连的基因序列节点对 , 则其对应的弧权值取一较大数 wmax. 为了增加优秀 个体繁殖的机会提高算法的性能[ 3] , 本文中建立带有自适应能力的适应度函数 :
第 40卷 第 2期
西 南 交 通 大 学 学 报
V o.l 40 N o. 2
2005年 4月
JOURNAL OF SOUTHW EST JIAOTONG UN IVERS ITY
A pr. 2005
文章编号 :0258-2724(2005)02-0241-04
军事运输是运用各种交通工具 , 实现军队人员和装备物资在空间上的位移 , 以保障军事活动的顺利进 行. 近年来发生的几次高技术条件下的局部战争表明 , 由于战争的突发性 、速决性急剧增强 , 对军事运输的 快速性和适应性提出了更高的要求. 无论是战时的部队战役战术集结和转移 , 还是平时的抢险救灾 , 通过 对运输路径的合理优化 , 可以极大地提高军事运输能力 [ 1] . 因此 , 运输路径优化研究历来是世界各国军队 的一项重要课题. 作者以军事运输路径优化为对象 , 重点研究路径存在必经点和节点保序要求时的军事运 输路径优化问题.
24 2
西 南 交 通 大 学 学 报
第 40卷
广义权集合. 关于节点和弧的广义权主要基于这样的原则来确定. 由于军事运输路径优化问题实际是一个
多目标优化问题 , 通常要求时间最短 、费用最少 、危险性最低 , 而这些目标通常与运输集结转运和保障时间
(主要指交通枢纽和军供站的装卸车 、生活保障等 )、线路里程 、行军速度 、耗油量 、安全警戒支援代价 、危 险性 (自然环境特性 、敌袭 )等方面有关[ 1, 2] . 对于多目标优化问题 , 采用线性加权和法把多目标转化为单
过某个节点 (称为后节点 ), 必须先到其它节点 (称为前节点 , 不一定与后节点直接相邻 , 可以有多个且可
共用 )进行伪装或做防护加固. 对于必经路段 , 可将路段的起 、止点转化为必经点 , 然后与其它必经点一起
构成必经点集合 VK. 关于节点保序问题的处理 , 首先建立后节点集合 Vb, 然后建立相应的前节点集合 Vf , 如节点 i∈ Vb , 则有相对应的前节点集合 Vif. 通过处理后得到新的运输网络图 G, 以及必经点集合 VK 和后
军事运输与一般运输在路径优化方面的一个最大不同点在于必须考虑必经点 、必经路段 [ 1] 和节点保