基于Dijkstra算法的最优路径搜索方法

针对传统Dijkstra算法在应用中存在的不足,提出了一种基于Dijkstra算法的最优路径搜索方法.该方法设计了区域限定模型,以避免大量无用结点参与计算带来的时间和空间的浪费.在此限定区域内使用优化的存储结构实现了含有启发式信息的搜索策略.路网实验结果表明,应用启发式搜索策略使搜索的路径结点总数和计算时间明显减少,搜索过程能够快速地趋于目标结点.     

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.     

动态流量多约束优化路径算法

基于多重上联链路网络,建立一个考虑多服务质量(QoS)度量约束限制的网络路径寻优调度模型,并针对时延和剩余带宽提出动态流量多约束优化路径算法(MOPA).基于MOPA和最短路径约束,给出了具有一个多重上联链路的确定性网络拓扑中实现优化流量费用的工程方法.通过分析网络资源现状及目标作用的重要程度,以主次目标形式考虑,建立目标之间的关联,简化多目标之间关系,使用迭代方法求解非线性约束条件下的流量和代价的优化解,动态选择最优路径使流量费用比最优化并实现工程应用.实验表明,该算法适用于多链路网络各种负载下的流量优化.     

加强的混合遗传算法求解能力约束弧路径问题

为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA). 该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力. 同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较. 结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.     

最优路径查询的研究与实现

车辆导航正成为现代交通的一种服务趋势,而其中重要的、必不可少的一部分就是最优路径的查询.对最优路径查询的原理、数据组织、数据结构和查询算法进行了研究,然后利用实验数据,实现了最优路径查询功能,证实了实现最优路径查询的方法是有效的.     

基于改进的蚁群算法求解最优路径方法

基本蚁群算法在求解时经常出现局部最优解,限制了该算法整体搜索性能。本文对此缺陷进行了改进,改进之一是引入临界值来更新信息素;改进之二是搜索最优解的方式改进为双向搜素。把改进后的算法用于求解电力故障抢修问题中的最优通路,通过实验仿真表明改进后的算法达到了预期效果。     

道路网络中门到门包含重复节点的最优路径算法

设计了用于包含交通约束的受限路网中基于兴趣点(PO I)的门到门包含重复节点的寻路算法。首先利用距离最短准则建立PO I和路网间的临时拓扑关系,然后根据受限路网中最优路径的结构特征,构造包含驶入路段的节点进行寻路拓展,以此为基础进行标记设定广度优先搜索,即可获得门到门包含重复节点的最优路径。在道路密度较大的北京市路网中的试验结果表明,该算法能够根据交通约束规划出实用的最优路径,对于长度约60 km路径的计算平均耗时在3 s左右,可以满足车辆导航应用的实时性要求。     

道路网络中门到门包含重复节点的最优路径算法

设计了具有交通约束的受限路网中,基于兴趣点(POI)的门到门包含重复节点的寻路算法。该算法首先利用距离最短准则建立POI和路网间的临时拓扑关系,然后根据受限路网中最优路径的结构特征,构造包含驶入路段的节点进行寻路拓展,以此为基础进行标记设定广度优先搜索,即可获得门到门包含重复节点的最优路径。在道路密度较大的北京市路网中的试验结果表明,该算法能够根据交通约束规划出实用的最优路径,对于长度约60km路径的计算平均耗时在3s左右,可以满足车辆导航应用的实时性要求。     

基于时间约束的人气最优路径搜索

当旅游景点数目庞大,而限定时间不足以访问任何路径中的所有景点时,现有的搜索方法找不到事实上存在满足条件的路线.提出了一种高效的最优路径近似搜索算法PSScaling,使用修整参数δ,将景点的人气分数调整为一个整数,然后利用路径标签上缩放后景点的人气分数和子路径的时间代价选择最优的子路径向终点扩展,在同一路径中挑选最佳的访问景点组合.最后,通过实验分析,验证了本文提出的算法能够在很高的执行效率下找到近似的最优路线.     

多约束最短路径模型与求解

提供满足驾驶员多个心理期望的路径是导航系统该解决的关键问题,其本质是资源约束最短路径问题,属于NP难问题,无法使用传统的最短路径算法解决.提供了多约束路径规划的数学模型,并使用了蚁群算法对其求解,在算法中针对问题重新设计了信息素更新规则和启发因子.实验证明算法具备良好的寻优能力,能准确找出路网中满足多种属性约束的路径.     

公交网络最优路径选择算法研究

公交乘客出行路径的选择是公共交通信息查询的重要内容.依据公交线路网络的特点以及公交路径选择的需要构造了公交线路网络的数学模型,在Dijkstra算法的基础上综合考虑乘客出行的乘车习惯、线路距离、换乘次数和乘车费用等因素,并考虑了多种不同的换乘方式和不同的线路类型对选路的影响,设计并验证了能够满足多种出行特点的路径选择算法.     

果园移动机器人的全局最优路径规划研究

为了实现移动机器人在果园环境下自主行走,对果园移动机器人在复杂果园环境中的最优路径规划进行研究.首先,利用栅格法定义了移动机器人在栅格上的运动方向、障碍物及信息编码,模拟建立出果园的环境地图模型.然后分别编写Dijkstra算法、A*算法,对果园机器人进行全局最优路径规划.通过分析比较,得出A*算法所规划的最优路径更为方便,搜索效率更高,更加满足果园机器人的实际工作需求,提高其工作效率.     

二次网络规划基解的一个优化方向及算法

给出了二次网络规划基解的一个优化方向；并获得二次网络规划的一个近似算法和有效算法。     

铁路车流径路优化算法的研究

建立了一种求解车流径路的启发式算法，目标函数是消耗的总车辆公里数最小，约束条件为区段能力和车流共同径路。以现行铁道部使用的＂全国铁路环状径路图＂为基本路网结构，点间车流和区段能力亦以现行运营的实际数据为依据，进行了车流径路计算。     

改进的蚁群算法在智能导游系统路径优化中的应用

为了解决游客选取最短旅行线路的困扰,在智能导游系统中加入路径分析的功能.将改进的蚁群算法应用于最短路径分析中,通过获取不同景点的ID号以及地理位置找到一条通过每个景点且只通过一次的最短旅行路线,仿真结果表明达到了预期的目标.     

免疫算法与其他随机优化算法的比较分析

详细描述了免疫算法的基本原理、步骤和寻优机理，以及抗体的抑制和促进、记忆单元更新、亲和性计算等特点。阐述了免疫算法抗原、抗体与实际问题的映射关系。用其他随机优化算法(模拟退火算法、遗传算法、进化规划等)与免疫算法进行了比较研究，给出了他们的异同点、免疫算法的优点等。利用旅行商问题(TSP)、随机优化算法测试函数对免疫算法及其他算法进行了测试分析。实例分析表明，免疫算法是一种收敛速度快、收敛性好的算法。     

染色装箱问题及其启发式算法

研究了装箱问题的一个新颖的衍生问题:染色装箱问题,即在装箱问题中,给每个物件指定一个颜色,要求每个箱子中所装的物件颜色各不相同,使得所需要的箱子数目尽可能少.该问题是通常装箱问题的一种推广.笔者给出了染色装箱问题的一个启发式算法,同时研究了只有两种颜色的染色装箱问题:即2-色装箱问题,并给出了一个最优算法.     

广域网中网络拓扑算法研究

网络拓扑发现是网络管理系统中的一个重要组成部分。介绍了在广域网中用于拓扑发现的两种算法,即以CNRG算法为代表的基本算法和启发式算法,并比较了两者的发现结果。结果表明,启发式算法与基本算法相比,在高效性、完整性以及准确性方面都有所提高。     

基于栅格地图-蚁群算法的机器人最优路径规划

通过栅格法建立栅格地图作为机器人路径规划的工作环境,采用蚁群算法作为机器人路径搜索的规则．将所有机器人放置于初始位置。经过NC次无碰撞迭代运动找到最优路径．到达目标位置．为防止机器人在路径搜索过程中没有达到最大迭代次数时路径大小已不发生变化而陷入局部最优。可通过对各路径上的信息素进行增减来使机器人路径搜索跳出当前值继续搜索．直到迭代完毕,获得最优路径．     

DNA杂交测序算法研究进展

DNA杂交测序是计算生物学的核心问题之一,其研究目标是在杂交实验的基础上重构DNA序列,已证明带有错误的杂交测序属于强NP-难问题。随着组合优化的研究,精确算法和启发式搜索算法,尤其是后者,被用于求解此类问题。目前,许多文献已提出了重构算法,但现有算法在解决实际问题时仍存在缺陷。综述了国内外已提出的重构算法,在此基础上进行了比较,分析了存在的主要问题,指出了当前新的研究热点,对未来的研究与发展趋势进行了展望。