最优路径规划算法设计报告.docx

. .. .. . 最优路径规划算法设计 一、问题概述 兵力机动模型的功能是支持实施机动的实体按照指定路线 ，由作战空间的 一点向另外一点的位置移动 ，并带入实体在移动过程中发生变化的状态信息 。 兵力机动模型包括行军模型 、战斗转移模型 、机动能力评估模型 。 涉及的 关键算法包括最优路径规划 、行军长径计算 、行军时间计算 、行军所需油料计 算、行军方案评估与优选等 。 最优路径问题又称最短路问题 。是网络优化中的基本问题 ，如 TSP 问题等。 下面先举例说明该问题 。 最短路问题 （SPP－shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地 。从甲地 到乙地的公路网纵横交错 ，因此有多种行车路线 ，这名司机应选择哪条线路呢 ？ 假设货柜车的运行速度是恒定的 ，那么这一问题相当于需要找到一条从甲地到 乙地的最短路 。 旅行商问题 （TSP－traveling salesman problem ） 一名推销员准备前往若干城市推销产品 。如何为他 （她）设计一条最短的 旅行路线 （从驻地出发 ，经过每个城市恰好一次 ，最后返回驻地 ？） 最短路问题是组合优化中的经典问题 ，它是通过数学方法寻找离散时间的 最优编排 、分组、次序、或筛选等 ，这类问题可用数学模型描述为 min f (x) s.t. g(x) 0 .下载可编辑 . . .. .. . x D . 其中， f (x) 为目标函数 ， g( x) 为约束函数 ， x 为决策变量 ， D 表示有限个点组 成的集合 。 一个组合最优化问题可用三个参数 ( D, F , f ) 表示，其中 D 表示决策变量的 定义域 ， F 表示可行解区域 F { x | x D, g( x) 0} ， F 中的任何一个元素称为 该问题的可行解 ， f 表示目标函数 ，满足 f (x* ) min{ f (x) | x F } 的可行解 x* 称为该问题的最优解 。 组合最优化的特点是可行解集合为有限点集 。由直观可 知，只要将 D 中有限个点逐一判别是否满足 g(x) 0 的约束并比较目标值的大 小，就可以得到该问题的最优解 。 以上述 TSP 问题为例 ，具体阐述组合优化问题 ： 此模型研究对称 TSP 问题 ,一个商人欲到 n 个城市推销产品 ，两个城市 i 和 j 之间的距离 dij d ji ，用数学模型描述为 min dij xij i j n s.t. xij 1 i 1,2, , n ， j 1 s.t. n xij 1 j 1,2, ,n ， i 1 i , j s xij | s | 1,2 | s | n 2, s {1,2, , n}, xij { 0,1}, i, j 1,2, , n, i j 约束条件决策变量 x 1 表示商人行走的路线包含从城市 i 到 j 的路，而 x 0 ij ij 表示商人没有选择走这条路 ； i j 的约束可以减少变量的个数 ，使得模型中共 有 n (n 1) 个决策变量 。 每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时 .下载可编辑 . . .. .. . 间为代价的 ，在 TSP 问题中，用 n 个城市的一个排列表示商人按这个排列序推 销并返回起点 。 若固定一个城市为起终点 ，则需要 (n 1)! 个枚举 。以计算机 1s 可以完成 24个城市所有路径枚举为单位 ，则 25 个城市的计算时间为 ：以第 1个 城市为起点 ，第 2 个到达城市有可能是第 2 个、第 3 个、 、第 25 个城市 。 决 定前两个城市的顺序后 ，余下是 23 个城市的所有排列 ，枚举这 23 个城市的排列 需要 1s ，所以， 25 个城市的枚举需要 24 s 。 类似地归纳 ，城市数与计算时间 的关系如表 1 所示 。 表 1 枚举时城市数与计算时间的关系 城市数 24 25 26 27 28 29 30 31 计算时间 1 s 24 s 10 min 4.3h 4.9 天 136.5 天 10.8 年 325 年 通过表 1 可以看出 ，随着城市数的增加 ，计算时间增加非常之快 ，当城市 数增加到 30 时，计算时间约为 10.8 年，实际计算中已无法承受 。在城市数较多 时，枚举已不可取 ，我们可以采用一些别的方法缩短计算时间 。 TSP问题是 NP 难问题，其可能的路径数目与城市数目 n 是成指数型增长的 ， 所以一般很难求出其最优解 ，因而一般是找出其有效的近似求解算法 。遗传算 法可以用来解决一些较为复杂的系统问题 ，显然旅行商问题是需要编码运算的 ， 而遗传算法本身的特征正好为解决这一问题提供了很好的途径 。 NP