考虑行程时间相关性的可靠最短路径算法

可靠最短路径(RSP)问题反映了出行时间的可变性,比只考虑平均出行时间的标准最短路径问题更加实际可行。本文提出了一种考虑路段行程时间相关性的均值-标准偏差RSP问题的求解思路。该算法采用拉格朗日代入和协方差矩阵分解技术,解决了混合整数非线性规划(MINLP)的非线性和不可加性带来的困难。将该问题分解为标准最短路径问题和凸优化问题,证明了凸优化问题的最优解,并将拉格朗日乘子范围与协方差矩阵的特征值联系起来,提出采用次梯度法进行拉格朗日乘子更新。该算法能降低了原问题的复杂性,可扩展到大型网络。

机械臂逆运动学避障最优求解算法

针对多自由度机械臂在障碍物环境下逆运动学求解存在多解性和碰撞问题,提出了一种将碰撞检测算法、最短行程方法与差分进化算法相结合的具有避障能力的机械臂逆运动学最优求解算法。首先,以六自由度机械臂为研究对象,对机械臂和障碍物进行建模,并建立求逆运动学解的目标函数,目标函数由末端执行器位姿误差函数、目标角度与初始角度之间的变化量函数、碰撞检测函数加权求和组成;其次,利用差分进化算法对目标函数进行最优求解,为了减小函数权重对求解速度和精度的影响,设计了一种自适应权重优化算法,使得求解关节角度在优化求解初期快速达到最短行程位姿角度附近,而在优化求解后期具有更高的求解精度,即可求得具有避障能力、行程最短且高精度的最优逆运动学解;最后,以UR5机械臂为例,通过MATLAB软件中的Robotics Toolbox工具箱对所提算法进行仿真验证,验证了所提算法的有效性。

交通信息网格中的最短出行路径并行算法

根据城市路网的特点,提出了一种新的路网图的分割方法;在此基础上,提出两种网格最短路径并行算法GPSPA1和GPSPA2.这两种算法克服了传统并行标签算法只适合在共享内存的并行机器上使用的缺点,适合网格环境下使用.实验结果表明:分割器不能完全分割源点和目标点时,GPSPA2比GPSPA1效率高;完全分割时,两种并行算法的加速比大约都是3.GPSPA2应用于交通信息服务网格系统2.0版中.

基于Dijkstra算法的电网故障行波定位方法

为避免电网故障行波定位方法中环网的复杂解网运算,提出了一种基于Dijkstra算法的电网故障行波定位新方法。该方法在电网中某条输电线路故障后,在所有变电站检测记录初始行波到达时间。然后,利用Dijkstra算法计算最短路径,建立最短路径距离矩阵,并利用最短路径矩阵和初始行波到达时间计算故障距离,建立故障距离矩阵。最后,对故障距离矩阵中的元素进行有效性识别,并综合所有有效故障距离得到精确的故障点位置。仿真结果表明该方法无需复杂环网的解网运算,可有效提高网络定位的可靠性与准确度。

基于网络的故障行波定位算法

为了解决电网故障双端行波定位中任一定位装置故障、启动失灵或时间记录错误等导致的定位失败难题,提出了基于网络的故障行波定位算法,根据电网中故障行波到达各变电站的精确时间和行波传输的最短路径进行综合定位计算。运用Floyd算法计算电网的最短路径矩阵,匹配行波波头到达各变电站的精确时间;分析不经过故障线路的最短路径,在线计算行波传播速度;并寻找经过故障线路的最短路径,在线计算故障点位置;为每个变电站设置权重,对所有不同路径的计算结果加权求和,得到故障点的精确位置。EMTP仿真分析和现场运行结果表明,该定位算法误差小于150m,可靠性高、鲁棒性强,较好地满足了电网运行要求。

瞬时动态用户最优问题的统一模型及算法研究

本文建立了瞬时动态用户最优(IDUO)配流问题的变分不等式(VI)模型。该模型满足Wordrop第一原理要求,使得乘客在任意决策节点都选择当时交通条件下到达讫点的最短路径。所给算法在每一个小时段都能给出路段流入率、流出率及路段流量,对行人进行诱导。

铁路车流径路优化分布式算法

针对铁路车流径路优化的计算量随着路网中节点数和车流数的增加呈指数型增长的问题,引入分布式计算方法进行求解。对于任意一个固定顺序的车流排列,基于线路能力约束条件,构造车流径路优化模型。定义对该车流排列评价的函数,将车流径路优化问题分解成车流排列的评价计算问题和车流排列优化问题。设计分布式计算网络结构及网络程序流程。采用改进的禁忌搜索法,在服务器端完成车流排列空间的优化搜索,在不同的客户机端进行车流排列的评价计算,利用计算机网络将二者有机地结合起来,形成分布式算法。将车流排列优化问题归纳为旅行商问题,分析模型算法的复杂性。对算例进行计算表明:对构造的车流径路优化模型采用分布式算法进行求解可以节省大量时间,但存在对计算机网络配置要求高的问题。

寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法．首先利用计算几何中凸亮与中轴的结构将点集划分成若干个子点集，然后反复采用求子点集凸壳及划分剩余干点集的方法，求得通过于点集的子路径，最后将各子路径连接成一条回路．中国货郎担问题存在多项式时间算法求得最短回路．所设计的算法的时间复杂性为O（n2lbn），将它用于中国货郎担问题，得到一条长度为15404km的最短回路．与陈沐天等人采用几何分块方法所得的最短回路相一致．

基于综合运输网络的客流分配优化模型与算法

以综合运输网络条件下的客流分配为研究对象,提出更适合表现旅客出行需求和各种运输方式相互竞争关系的运输细分方式,采用可量化表征综合运输网络当前客流状态的区间饱和度和径路饱和熵,并结合旅客出行广义费用函数,构造旅客出行阻抗函数,给出以综合运输网络中旅客出行总阻抗最小为目标的客流分配优化模型。基于k条最短路算法和混沌优化算法,在径路选择时考虑当前综合运输网络的旅客出行阻抗因素,设计客流分配迭代优化的动态求解算法。算例表明,利用给出的模型和算法能够得到可行和更为细分的综合运输网络客流分配方案。

基于LTI和网格界面剖分的三维地震射线追踪算法

将二维线性走时插值射线追踪算法(LTI)推广应用至三维模型,并结合网格界面剖分方式,提出了一种三维射线追踪算法.该算法既可获得高精度的全局最小走时和射线路径,又具有快速稳定的特点.三维模型计算结果表明,在模型参数包括网格密度完全相同情况下,本文算法较传统的三维最短路径算法在计算效率、走时和射线的计算精度上均有明显改进.

最短射线路径追踪方法的优化

对求出的射线路径进行整体优化,以减小离散化所产生的误差,从而减小射线路径的误差。对射线路径优化过程进行了推导,并提出了最短射线路径的优化循环迭代算法,求出了优化的最短射线路径。应用理论模型验证了最短射线路径的优化循环迭代算法的可行性;相对于理论路径而言,优化最短射线路径法得到的射线路径误差较小。将该方法应用于最短射线路径追踪和折射波静校正等资料处理的过程中,可以减少运算量和运算时间。

基于最短时间的公交乘车路径查询模型

很多经典的公交路径查询算法都把焦点放在行驶路径最短搜索上,而忽略了越来越影响人们出行时间花费的等车和换车上。本文利用有向带权图建立了一种综合考虑等车、换乘和运行时间的最短时间公交出行路径查询模型,通过灵活的权值设定策略优化查询目标。实验表明,提出的模型有效、实用,具有很好的灵活性。

VNS中动态行程时间与多端动态最短路算法

对车辆导航系统中路径引导信息的供给与需求进行了综合分析 ,提出了最短路划分方法与多端动态最短路问题 。

基于遗传算法的TSP问题优化求解

旅行商问题(TSP)是典型的NP完全问题,本文运用遗传算法求解TSP问题,提出了该算法在解决这一问题中的一些处理方法,使用该算法能够较快地求出一批最短路径,可根据需要设置叠代代数,求得理想最优解。

具有局部重复路径的多路旅行商问题的研究

首先对连通图上允许旅行商走回头路的 TSP的问题进行了研究 ,证明了问题解的存在性 ,给出了利用连通图的顶点间最短路径构造完全图的求解方法。然后 ,对连通图上允许路径部分重复的 MTSP问题进行了初步的研究 ;采取“分治”的方法并结合遗传算法 ,设计了求解路径部分重复的 MTSP问题的有效算法。讨论了关于求解多个旅行商完成任务的最短时间和最短路径的问题 ;并给出了在限定时间内完成任务的条件下 ,求最小分组 (人员配置 )的问题的方法。可重复路径的MTSP问题的研究 ,在现实中有很大的使用价值。诸如 :交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等 ,都可以抽象成 TSP或

旅行商问题的一种模拟退火算法求解

旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以处理的NP难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。首先介绍了旅行商问题,模拟退火算法原理及其算法实现。应用模拟退火算法对TSP进行研究,给出解决TSP的一种比较精确的算法并用Matlab实现了算法。最后用该算法对TSP进行了仿真,验证了该算法的有效性。

走时层析成像正反演方法研究

在资源勘探及工程质量检测等领域的走时层析成像技术具有分辨率高、探测范围广、成像结果直观等特点。走时层析成像技术主要包括两部分研究内容:估计射线路径及走时,进行图象重建。本文基于射线理论,应用最短路径射线追踪方法进行了射线走时的正演计算;并通过对多种反演算法的对比研究,选用SIRT算法进行快速反演成像,最后给出了仿真计算结果,并进行了分析比较,证明了本文正反演算法的有效性和实用性。

旅行商问题的一种启发式算法

用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n列的顶点上的图,如何从这些图上搜索出近似最优解的方法.

基于单亲遗传算法求解卫勤保障最短回路问题

目的提出一种用于求解卫勤保障最短回路问题的有效算法。方法采用仅使用变异算子和选择算子来繁殖后代的单亲遗传算法(PGA)。该算法基于K-随机近邻算法,同时结合了随机两点位置互换、相邻两点位置互换、环形部分逆转、随机插入等4种变异算子,在选择操作过程中结合贪心策略,进一步提高PGA算法的"爬山"能力。结果通过对CTSP31以及多组TSP标准数据集的测试结果表明,该算法相对于文献中已有算法更加有效。结论该算法可作为今后开发计算机辅助软件的基础,为提高卫勤指挥的质量和速度而提供辅助优化决策。

一种带有时间窗的货物配送路线设计算法

提供了一种有大量的客户数据,只需对部分客户进行带有时间窗要求的货物配送的优化路径选择算法。该算法首先通过寻找的隐含条件利用可行的算法将问题规模进行缩小,然后利用特殊情况获取限制条件,不断缩小搜索范围,从而搜索到有效解。该算法针对具体问题设计,适合应用于工程实践。