复杂约束条件下求解带权最短路径方法

为了解决复杂网络条件下带权最短路径问题,提出了基于压缩图的禁忌搜索算法。通过基于约束条件的图压缩算法,将复杂约束条件下的带权最短路径问题转化为旅行家问题(TSP),并通过优化禁忌搜索算法来求解复杂约束条件下带权最短路径问题。仿真结果显示,基于压缩图的禁忌搜索算法具有求解快、时间复杂度低、收敛快、对图规模和约束条件不敏感的优点。

基于不同交通工具多约束条件的最短路径算法研究

多约束条件下的最短路径选择可以满足用户的出行需求,然而不同的交通工具在相同起始点下最短路径选择存在很大差异。为了满足多用户的出行需求,基于不同交通工具的多约束条件,对传统的Dijkstra算法进行改进,由传统的基于单约束条件向多约束条件改进,并对最短路径选择的准确程度进行优化。通过实例,验证算法的可行性和准确程度。

不确定随机网络下的带资源约束的最短路径问题

本文利用机会理论这种新的数学工具,研究了不确定随机网络下的带资源约束的最短路径问题,即在具有双重不确定性的网络中,寻找一条始于源节点终于目的节点并满足资源约束的最短路径问题。根据机会理论的运筹法则,我们给出了不确定随机网络带资源约束的最短路径问题的机会分布函数,并应用不确定随机变量的新型互熵建立了一个模型——带资源约束的新型互熵最小最短路径优化模型,用于解决这个问题,与之相对应的一个算法也被提出,本文最后设计了一个数值实验用来验证模型的有效性。

网络图中多约束条件下的路径选择问题

本文探讨了多约束条件下的路径选择问题。本文的工作在于对多约束条件下的路径选择问题进行了规范的描述和分类,并针对各类问题讨论了典型的求解算法,同时对现有算法进行了改进,使其更适用于求解管理科学领域中的MCP问题,从而拓展了该问题的应用空间。

无人侦察机的最短巡航路径问题

无人侦察机的巡航问题,如果不考虑其它约束条件,实际上是一个TSP问题。目前还没有求解TSP问题的比较有效的实时算法,本文我们首先利用Monte Carlo方法求得一个较好的初始解,再应用现代优化算法中的模拟退火算法就可以实时地求得一个较满意的解。

Floyd算法在多约束条件下飞行器航迹快速规划的应用

基于Floyd算法研究在多约束条件下飞行器航迹快速规划中的实际工程应用问题。首先,根据飞行距离和定位校准误差等多种约束条件建立符合工程应用的路径模型;然后,采用Floyd算法对模型求解,计算飞行器到达任务点的最短路径,实现飞行航迹的快速规划;最后,采用MATLAB仿真对方案的可行性进行验证,通过与A^*算法和最小偏角搜索算法对比,得出Floyd算法计算结果可靠、路径最优。

基于三次B样条曲线的叉车型AGV路径规划研究

针对工厂环境下叉车型AGV在沿给定参考路径运行时,因避障等问题产生的大幅度偏离参考路径的现象,将3次B样条曲线用于路径规划;规划路径在满足AGV运动学约束、最大曲率约束、起点和终点位姿等约束的条件下,使AGV以最短距离回到原参考路径;算法将路径规划问题转化为参数优化问题,将规划路径距离作为目标函数优化求解参数;算法最后使用Matlab针对直线和圆弧参考路径进行了仿真验证,结果表明文章算法能够在大偏差情况下,规划出一条最短路径,使AGV回到参考路径。

城市商业区智能泊车系统的设计与开发

针对石家庄市商业区停车压力和停车管理系统现状,基于运动车辆的当前位置、车库中的车位数量、道路状况、路口限制等动态约束因子,进行了智能泊车系统的技术设计与软件开发。通过建立复杂约束条件下的模糊预测模型,并使用扩展和改进后相邻节点低值传递的最短路径引导算法,实现了城市商业区泊车过程中动态最短路径与最佳路径的分析与可视查询,并介绍了模拟应用情况。

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明:所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。

生枝-剪枝算法在专用道设置问题中的应用

专用道设置问题中,将运输任务限定为一个,从而将问题转化为带约束条件的动态最短路径问题。针对该问题的实际特点,设计了生枝-剪枝算法。该算法的核心思想是:穷举所有从起点开始的行驶路径(生枝过程),然后利用剪枝规则剪除不符要求的分枝,最后在抵达终点的行驶路径中经过比较选出最优路径。

一种基于蚁群算法的QoS多播路由算法

采用启发式算法中蚂蚁算法解决包含带宽、时延和最小代价约束条件在内的多播路由问题,文章基于蚂蚁具有找到蚁巢与食物之间的最短路径原理工作,并在分析多约束Qo S的多播路由的基础上,提出了一种基于蚁群算法的Qo S多播路由算法(QMRA) 。