城市战斗中的道路问题分析

本文利用集合论的方法 ,对城市中的道路进行分类 ;并按图论中最短路径问题给出一种最新解法 ;这对城市战斗和其它实际应用都有十分重要的意义。     

确定部队最佳机动路径的一种求解法

本文介绍了应用图论中求最短路径的一种算法,确定部队最佳机动路径的基本原理、方法步骤和在计算机上的实现方法.同时对该算法在计算机上实现过程中存在的问题进行了研究讨论,提出了一种新的解决方法.     

舰空导弹协同制导路径优化问题研究

协同制导可以大大改善超视距舰空导弹的作战空域.在网络中心制导中,为了合理选择协同制导平台,提出了协同制导平台选择的指标,将协同制导平台表示为图论中的节点,利用图论中求最短路径的方法分析单因素最优时的制导路径,采用层次分析法求解多因素约束下的最优路径.最后通过实例分析模型的应用,根据不同协同制导路径的权重,指挥员可以作出最优的选择.     

救灾物资的紧急调运模型

针对某地区防洪救灾中物资的调运问题,利用图论中最短路的知识,根据问题实际,将物资的调运方案分成3个阶段.在每个阶段以费用最小或时间最短为目标.以各单位之间物资的供求平衡为约束,建立了规划模型.通过编程求解,制定了不同情况下物资紧急调运的具体方案,包括用车数量、行车线路、用车时间和费用.     

基于时间序无圈有向图的多准则优化成像调度

合理有效地利用遥感卫星资源获取更多高质量影像数据是卫星成像调度的重要工作。提出了一种新的成像调度解决方案。应用图论相关理论,建立卫星成像时间序无圈有向图模型,利用多项准则作为衡量标准对不同成像路径进行评价,提出时间序多准则最短路径算法求取优化成像路径。理论分析和实验表明,该解决方案可以在较短时间内获得多条pareto优化成像路径,具有良好的调度性能。     

基于Hopfield神经网络的战时物资筹措模型

战时物资筹措是国防动员的一个重要组成部分,它实质上是一种基于约束的最短路径问题,Hopfield神经网络曾被用来解决最短路径优化问题。采用连续型Hopfield神经网络求解战时物资筹措问题,在已知供需量、通行参数等数据的情况下可快速确定物资筹措方案。这种方法针对战时物资筹措的特殊性如时间严格、道路通行受阻等具体情况具有很好的适应性。实验结果证明在问题规模较大的情况下模型具有收效速度快、计算结果准确性高等优点。     

基于图论的电视指令制导空地导弹航路规划

针对电视指令制导空地导弹的作战使用特点,建立了导弹航路代价模型,分析了影响导弹航路规划的距离和角度约束,基于图论理论并采用逆推方式实现了导弹的航路规划并给出了导弹发射区。仿真结果表明,所得航路不仅满足导弹的各种使用限制、路径最短,还可以有效地规避航路中的威胁,提高导弹的生存概率。     

时变道路网最短路径算法的研究

道路或区域通行限制在日常交通和部队兵力机动过程中普遍存在。通行限制情况下的最短路径问题属于时变道路网最短路径研究的范畴,对时变道路网最短路径算法及算法效率的研究有着广泛而现实的意义。重点讨论了道路网的模型描述、时变道路网拓扑结构的构建技术,最短路径算法的高效实现等内容,并给出了该算法的应用实例。试验结果显示,该算法有效可行。     

一种基于分层分析算法的实时最优消防应急救援路径算法

针对现有消防应急救援算法未充分考虑路网中不同路段的畅通度、道路规格、交叉路口数量以及路网动态变化等因素,提出了一种实时的分层分析算法计算最优路径。首先利用层次分析法对道路的权重进行综合判定,然后使用局部规划技术应对突发事件,修正全局路径,保证车辆行驶时间最短,最后使用MapInfo建立电子地图,以山西省太原市城区范围为原型,计算某单位发生火灾或抢险救援的实例。实验结果表明,该算法可以有效解决动态最优路径问题,同时实际应用证明该算法有效可靠。     

随机网络的α最短路径问题

为了求解随机网络中满足置信度为α的最短路径问题,提出了一种BP神经网络遗传算法。首先给出了随机网络的定义,建立了α最短路径模型;然后采用BP神经网络拟合非线性函数,遗传算法优化BP神经网络输出的方法求解该问题。实验结果表明,提出的模型和算法能有效求解随机网络的α最短路径问题。     

Robust shortest path problems with two uncertain multiplicative cost coefficients

We consider a robust shortest path problem when the cost coefficient is the product of two uncertain factors. We first show that the robust problem can be solved in polynomial time by a dual‐variable enumeration with shortest path problems as subproblems. We also propose a path enumeration approach using a K ‐shortest paths finding algorithm that may be efficient in many real cases. An application in hazardous materials transportation is discussed, and the solution methods are illustrated by numerical examples. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

基于k短路径的兵力机动路线优化方法

由于传统Dijkstra算法只能求解最优路径,结合兵力机动路线选择的需要,将求解k短路径的实用算法引入到兵力机动路线优化问题中,给出了算法的数据结构和步骤。在道路权重的确定上,提出将路程、通行能力和安全性三项指标相结合的思想,并给出了综合权重的计算方法。仿真实验表明所提方法具有较强的实用性。     

A note on the stochastic shortest-route problem

This paper develops an algorithm for a “shortest route” network problem in which it is desired to find the path which yields the shortest expected distance through the network. It is assumed that if a particular arc is chosen, then there is a finite probability that an adjacent arc will be traversed instead. Backward induction is used and appropriate recursion formulae are developed. A numerical example is provided.     

Finding the Kth shortest path in a time‐schedule network

We consider the problem of finding the Kth shortest path for a time‐schedule network, where each node in the network has a list of prespecified departure times, and departure from the node can take place only at one of these departure times. We develop a polynomial time algorithm independent of K for finding the Kth shortest path. The proposed algorithm constructs a map structure at each node in the network, using which we can directly find the Kth shortest path without having to enumerate the first K − 1 paths. Since the same map structure is used for different K values, it is not necessary to reconstruct the table for additional paths. Consequently, the algorithm is suitable for directly finding multiple shortest paths in the same network. Furthermore, the algorithm is modified slightly for enumerating the first K shortest paths and is shown to have the lowest possible time complexity under a condition that holds for most practical networks. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

On three basic methods for solving bottleneck transportation problems

For solving transportation problems essentially three types of methods are known: primal methods, the Hungarian method and the shortest augmenting path method. In this paper we present the specialization of these approaches to the bottleneck transportation problem and report some computational experience.     

武警部队快速机动中最优路径的实现

紧急条件下武警部队快速机动最优路径,是一个多目标多约束随机动态交通网络寻优问题。在分析交通网络拓扑化特点及最短路模型前提下,着重研究道路通行能力带给复杂公路网络道路寻优问题的影响,并结合GIS系统利用改进的Dijkstra算法求解。     

分段线性凸费用网络流的两个算法

本文讨论了分段线性凸费用网络流问题,推广了线性费用网络流中的负回路方法和最小费用路方法,从而得到了求分段线性凸费用网络的最小费用流的两个算法。     

Shortest path interdiction problem with arc improvement recourse: A multiobjective approach

We consider the shortest path interdiction problem involving two agents, a leader and a follower, playing a Stackelberg game. The leader seeks to maximize the follower's minimum costs by interdicting certain arcs, thus increasing the travel time of those arcs. The follower may improve the network after the interdiction by lowering the costs of some arcs, subject to a cardinality budget restriction on arc improvements. The leader and the follower are both aware of all problem data, with the exception that the leader is unaware of the follower's improvement budget. The effectiveness of an interdiction action is given by the length of a shortest path after arc costs are adjusted by both the interdiction and improvement. We propose a multiobjective optimization model for this problem, with each objective corresponding to a different possible improvement budget value. We provide mathematical optimization techniques to generate a complete set of strategies that are Pareto‐optimal. Additionally, for the special case of series‐parallel graphs, we provide a dynamic‐programming algorithm for generating all Pareto‐optimal solutions.