道路修复条件下灾后应急资源配送LRP研究

灾后道路中断、道路通行可靠性减弱从根本上影响着救援工作的效率,文章通过在应急资源配送定位路径问题的基础上考虑对障碍道路进行修复。通过构建应急设施定位、障碍道路修复以及配送路径选择的综合优化模型,以应急救援的时间总成本最小为目标。集中考虑应急设施定位选址、修复障碍道路和选择配送路径的基础上,以时间总成本最小为目标函数,通过结合相关案例仿真与数据分析的基础上运用多吸引粒子群优化算法对模型进行求解,以期为灾后道路选择、提升道路通行可靠性和应急物资配送效率提供借鉴于理论指导。     

考虑道路修复的应急资源配送可靠路径选择问题研究

灾害发生后第一时间选择可靠路径完成应急资源的配送分发是应急救援快速展开的必要保障。本文考虑道路修复下的应急资源配送可靠路径规划问题,引入了道路中断和通行可靠性降低来描述灾难对应急资源配送交通路网的影响,以最大化配送效率为目标,构建了道路修复与应急资源配送可靠路径选择集成优化模型,给出了道路修复与可靠路径选择的全局优化方案;设计了多吸引子的粒子群优化模型算法,并结合仿真与分析,验证了模型和算法的有效性。模型与算法的研究对于突发事件下不确定交通路网应急资源配送决策具有很好的指导意义。     

机器人避障问题

研究机器人在平面区域中绕过静态障碍物到达指定目的地的问题, 分别考虑了路程最短和时间最短两种目标下的最优路径, 给出了计算机自动搜索最优路径的模型和算法。     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

Bellman最优原理在复杂加权网络中的应用研究

针对现有算法及软件计算复杂加权网络介数的局限性,应用Bellman最优原理于复杂加权网络介数计算中,并针对复杂网络动态演化,节点众多,重点,节点间无边连接等特点作了相应修改.依算法实例计算出了复杂加权网络的最短路径长、最短路径和介数,最后经验证算法具有较快的运行速度和较准确的结果.     

时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。     

基于精英单亲遗传算法的冷链物流VRP模型优化研究

针对冷链物流配送的特殊性,探索冷链物流车辆路径问题(VRP)优化方案.首先,在保证货物不超载的条件下,建立基于时间和品质因素的顾客满意度约束的多配送中心VRP(MDVRP)模型;其次,采用重心分区法和改进的精英单亲遗传算法,求解顾客在配送中心的分配,确定配送车辆数以及顾客服务次序;最后,用Matlab工具编程对模型进行求解分析.结果表明构建基于满意度的冷链物流MDVRP模型更适合冷链物流配送最优路径选择,并且改进单亲遗传算法能够有效求解这类问题.     

不可恢复道路堵塞路径选择问题及其算法

针对不可恢复道路堵塞的路径选择问题，分析了堵塞发生的不同起始时间对通过被堵塞边的费用(时间)产生的影响，这种影响引起的后效性使得这个问题不适合用动态规划中逆序推算方法求解。本设计了一种算法(MDA)，对经典的Dijkstra算法中的权值计算进行了修正，证明了算法的复杂性为O(n^2)，并用该算法对模型进行了求解。最后通过一个算例分析，对算法进行了验证。     

检测网络社团结构的基于最短路径的$k$-均值算法

我们考虑复杂网络社团结构的检测问题,即检测出那些具有高于平均密度的边所连接的节点的集合.本文我们利用模拟退火策略来极大化可表示为稳定效益函数的模量(modularity),并结合基于最短路径的$k$-均值迭代过程来对网络进行分区.该算法不仅能检测出社团,而且能够识别出在最短路径度量下,该社团中位于中心位置的节点.社团的最优数目可以在无需任何关于网络结构的先验信息下自动确定.对人工生成网络和真实世界中的网络的成功应用表明了算法的有效性.     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。     

模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.     

网络最短的最优解集结构

The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily.     

Increasing Internet Capacity Using Local Search

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity.We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.     

A bicriterion shortest path algorithm

Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.     

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms

In this paper, a methodology for modeling surface wildfire propagation through a complex landscape is presented. The methodology utilizes a Delaunay triangulation to represent surface fire spread within the landscape. A procedure to construct the graph and estimate the rate of spread along the edges of a network is discussed. After the Delaunay data structure is constructed, a two pass shortest path algorithm is incorporated to estimate the minimum travel time paths and fire arrival times. Experimental results are also included.     

Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Shortest Path Problem on a Network with Imprecise Edge Weight

A network with its arc lengths as imprecise number, instead of a real number, namely, interval number and triangular fuzzy number is considered here. Existing ideas on addition and comparison between two imprecise numbers of same type are introduced. To obtain a fuzzy shortest path from a source vertex to all other vertices, a common algorithm is developed which works well on both types of imprecise numbers under consideration. In the proposed algorithm, a decision-maker is to negotiate with the obtained fuzzy shortest paths according to his/her view only when the means are same but the widths are different of the obtained paths. Otherwise, a fuzzy optimal path is obtained to which the decision-maker always satisfies with different grades of satisfaction. All pairs fuzzy shortest paths can be found by repeated use of the proposed algorithm.     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式