A Shortest Path Algorithm for Multi-stage Network with Linear Parameter

In this paper, we give the shortest path algorithm for multi-stage network with a linear parameter, and study its complexity.

Using Link Analysis Technique with a Modified Shortest-Path Algorithm to Fight Money Laundering

Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.

The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window ?within which the node may be visited and ?, is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time?t0, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t0;and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which ce are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].

An Investigation on the Effect of Migration Strategy on Parallel GA-Based Shortest Path Routing Algorithm

Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.

An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem

In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.

A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining

On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.

An Improved Genetic Algorithm for Flight Path Re-Routes with Reduced Passenger Impact

Adverse weather has serious implications for flight timeliness, as well as passenger and aircraft safety. This often implies that alternative flight paths have to be used by aircraft to avoid adverse weather. To reduce the impact of such path re-routes, exact techniques such as artificial potential field model and Dijkstra’s algorithms have been proposed. However, such approaches are often unsuitable for real time scenarios involving large number of waypoints and constraints. This has led to the use of metaheuristic techniques that give sub-optimal solutions in good time. In this work, an improved genetic algorithm-based technique has been proposed. The algorithm used an improved mutation operator, reduced passenger inconvenience and considered the schedules of aircraft.

The Shortest Path Analysis Based on Road Network

Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.

A~*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.

Grid-Based Path Planner Using Multivariant Optimization Algorithm

To solve the shortest path planning problems on grid-based map efficiently,a novel heuristic path planning approach based on an intelligent swarm optimization method called Multivariant Optimization Algorithm( MOA) and a modified indirect encoding scheme are proposed. In MOA,the solution space is iteratively searched through global exploration and local exploitation by intelligent searching individuals,who are named as atoms. MOA is employed to locate the shortest path through iterations of global path planning and local path refinements in the proposed path planning approach. In each iteration,a group of global atoms are employed to perform the global path planning aiming at finding some candidate paths rapidly and then a group of local atoms are allotted to each candidate path for refinement. Further,the traditional indirect encoding scheme is modified to reduce the possibility of constructing an infeasible path from an array. Comparative experiments against two other frequently use intelligent optimization approaches: Genetic Algorithm( GA) and Particle Swarm Optimization( PSO) are conducted on benchmark test problems of varying complexity to evaluate the performance of MOA. The results demonstrate that MOA outperforms GA and PSO in terms of optimality indicated by the length of the located path.

考虑鲁棒成本与绝对后悔的最短路径问题研究

为克服鲁棒偏差方法在处理区间路网时所求鲁棒最短路径的保守性问题,通过分析鲁棒成本的定义以及鲁棒最短路径过于保守的原因,结合算例分析提出了绝对后悔值的概念,并以鲁棒成本和绝对后悔值为目标函数建立了区间路网的多目标最短路径模型;根据最短路径模型的特点设计了分离路径决策变量与连续变量的Benders分解算法,同时基于传统有效路径的判断依据重新定义了符合该最短路径模型的有效路径,并在分解后的主问题模型中引入了有效路径约束以加快算法收敛速度;利用MATLAB生成了一个包含29个节点、70条双向通行路段的区间路网对模型与算法进行仿真测试。结果表明:考虑鲁棒成本和绝对后悔值的最短路径模型能在区间路网中找到不保守,且同时兼具鲁棒性的最短路径,能够有效克服鲁棒偏差方法的缺陷。

基于机器学习算法的卷烟营销智能客户拜访策略研究

为提高卷烟行业客户经理的工作效率和服务质量,提出一种基于机器学习算法的卷烟营销智能客户拜访策略。在构建卷烟客户价值分类模型的基础上,利用K均值聚类机器学习算法对零售客户进行分类,合理设置LKH超启发算法和Dijkstra最短路径算法的参数,对客户经理拜访路径进行最优规划和智能导航。仿真结果表明,基于机器学习算法的卷烟营销智能客户拜访策略显著提高了客户经理人均拜访户数、商户满意度,大大缩减了户均在途时间和商户拜访服务覆盖周期。文中提出的策略有助于推动卷烟营销工作质量变革、效率变革和动力变革。

面向可编程网络的高可靠路由优化算法研究

随着网络规模的不断扩大和复杂度的增加,网络的可靠性和性能变得越来越重要。在可编程网络中,路由优化算法成为提高网络性能和可靠性的重要手段之一。在网络中,路由优化是一个非常重要的问题,因为它直接影响网络的性能和可靠性。传统的路由算法存在一些问题,如收敛速度慢、资源利用率低等。为了解决上述问题,提出了一种新的路由优化算法,即结合Bellman-Ford的双向Dijkstra算法进行最短路径计算。具体来说,首先从可编程网络入手,分析了传统的路由算法存在的问题;接着,为了改进传统Dijkstra算法中无法对存在负权边进行求解的不足,在存在负权边时融入Bellman-Ford算法进行求解,对所有边进行V-1次松弛操作,预处理出源点和汇点到每个节点的距离上界,从而减少计算量;然后通过预处理出源点和汇点到所有节点的最短路径长度的上界,可以减少Dijkstra算法的搜索范围,从而提高搜索效率;最后通过仿真对所提出的算法进行了验证,并与传统的路由算法进行了比较。实验结果表明,所提出的算法在收敛速度、资源利用率等方面均表现优秀,能够有效提高网络的性能和可靠性。因此,以上的研究具有一定的理论和实际意义,对于网络技术的发展具有重要的参考价值。

时变交通拥挤和需求随机的移动设施运营优化

为了优化移动设施(Mobile Facility,MF)的运营,在充分考虑时变交通状况和用户需求随机性的基础上,构建了一个两阶段随机规划模型,以期为决策者提供有力的工具。在第一阶段,模型针对MF的数量、时刻表和路径进行决策;第二阶段则聚焦于用户需求的分配和未满足服务量的确定。在求解此模型的过程中,本研究结合了时间依赖最短路径算法与L-shaped算法。在解决MF的移动路径和用户到达服务点的时间依赖最短路径问题时,将时变路段行驶速度离散化为分段函数,使得路段行驶时间成为连续分段线性函数,并且满足网络先进先出的原则,从而可以修改现有最短路径算法高效求解时间依赖最短路径。在L-shaped算法中,视一阶段模型为主问题,二阶段模型为子问题。首先通过求解主问题获得一阶段的决策变量,然后利用这些变量求解子问题,为主问题生成最优割。通过主、子问题的迭代交互,实现了对模型全局最优解的收敛,同时,通过加入有效不等式,使得算法能够快速收敛。在上海市嘉定区COVID-19核酸检测服务的MF实例中,对所提出的模型和算法进行了实证研究。结果表明:多割L-shaped算法结合有效不等式显著提升求解效率;同时,随着用户需求分布情况数量的增加,完美信息期望值和随机解价值均显著增加,这强调了在决策过程中获取准确信息和考虑时变交通状况与需求随机性的重要性。

水库库容无人船自动巡航路径规划算法与仿真实验

该文主要探究水库库容无人船自动巡航最短路径的规划算法,并对算法应用效果进行仿真验证。使用模拟退火算法可以基于补测点寻找最短路径,但是循环次数较多、耗时较长;通过补测点聚类处理,将补测点分成若干点簇后再次寻找最短路径,耗时明显变短,但是仍然存在不同点簇之间路径差值较大的问题。使用点簇调整算法后,保证不同点簇之间的最短路径相近,达到降低能耗和提高效率的目的。仿真结果表明,在点簇调整后,3个点簇最短路径的差值从70398.48 m变为15356.29 m,在多艘无人船自动巡航路径规划中达到能耗均衡、精度较高的效果。

复杂背景下的结构光条纹中心提取算法研究

线结构光三维扫描建模系统中最关键的一步是提取光条中心线,但环境中各种因素的干扰给中心线提取带来困难。针对线结构光条纹图像存在光斑干扰、光强分布不均、光条宽度差别大、背景复杂等多种问题,提出解决方案。首先采用Otsu对结构光图像二值化;其次采用改进DBSCAN(density-based spatial clustering of applications with noise)算法保留核心点,去除边界点和噪声点;最后将核心点作为输入,构建图数据结构,采用适用于线结构光条纹图像的最短路径搜索算法得到光条中心线。实验结果表明,该算法运行时间在150 ms以内,误差在0.2像素以内,并适用于多种复杂环境,满足实时性、准确性和稳定性的要求。

面向枢纽机场的多因素滑行路径规划综合研究

针对枢纽机场滑行道容量不足问题,结合安全间隔、冲突解脱和公平性原则,以滑行路径最短作为优化目标,考虑燃油消耗和废气排放,建立滑行路径规划模型。采用Dijkstra算法将滑行路径转化为邻接矩阵,以加权的方式进行冲突解脱,在保证滑行道零冲突的前提下,减少总的滑行距离。以国内某枢纽机场2018年某日18:00—19:00内的实际运行数据结合19个跑道节点、71个滑行道节点进行验证分析。结果表明,提出的滑行路径规划方法可行,可提高机场场面滑行效率,有效降低油耗量及污染物排放。

基于Dijkstra算法的移动机器人最短路径规划设计研究

本研究针对移动机器人的路径规划问题,结合Dijkstra算法进行了深入探讨。设计了一套针对移动机器人的最短路径规划系统,该系统全面考虑了机器人的运动约束、环境信息以及目标位置等关键因素。在此基础上,提出了一种基于Dijkstra算法的路径规划方案,旨在实现高效且精准的路径规划,为移动机器人的自主导航提供有力支持。