基于改进K最短路算法的公交线网优化研究

文章研究了公交场站选址和线网设计组合优化问题,建立以站间直达为关键约束的线网优化模型并给出求解算法。在所构建的公交网络中,利用改进的K最短路算法和相应的路径筛选条件获得从节点出发的K最短路径树,找出符合条件的单个K最短路径树作为初始解;通过不同节点的K最短路径树的叠加、删除、替代的优化过程,获得最优的K最短路径树组合,得到最优的公交线路集、场站位置。算例结果表明:公交网络规模越大,所需场站越多;K值越大,所需场站越少;不同场站可相互配合进行布局,实现公交线网性能的提升。     

一种优化D算法最短路径实现方法的研究

D算法（Dijkstra,狄杰斯特拉算法）是典型的单源最短路径算法,用于计算一个节点到其它所有节点的最短路径。从存储结构角度,提出一种优化D算法的最短路径方法,利用基于COMArcEngine技术加以实现。     

多集散点车辆路径优化的混合算法

为使多集散点车辆路径优化结果全局最优,以订单为基准建立多集散点车辆路径优化模型.采用粒子群算法与改进蚁群算法组成的混合优化算法求解模型.由粒子群算法的粒子位置向量得到每辆车所需运送的订单号,用蚁群算法优化单车路径,根据优化的总路径评价和筛选粒子,直到满足终止条件.该模型和混合算法是所有车辆对所有订单节点的路径优化,突破了多仓库问题直接或间接转化为多个单仓库车辆路径优化问题中的局部节点求解的限制.实例求解结果表明,用该混合算法优化的车辆总路径长度小于用蚁群算法求得的结果.     

无线传感器网络中能量全局优化精确数据收集

在多跳无线传感器网络进行精确数据收集时,靠近汇聚节点(sink节点)的传感器节点因为需转发其他节点的数据,其能量消耗快,容易使网络造成能量空洞,缩短网络寿命。为延长网络寿命,提出一种能量全局优化的精确数据收集算法(EGODGA),有效地收集传感器节点的数据。与经典的最短路径算法Dijkstra不同,EGODGA算法同时考虑链路代价和节点代价,找出从源节点到目的节点的最小代价路径,实现网络能量全局优化。仿真结果表明:在相同的条件下,与经典的最短路径算法Dijkstra和对瓶颈节点能量均衡问题解决较好的MAXLAT算法相比,EGODGA算法可以通过优化网络拓扑子树的节点数目,实现网络的能量均衡,缓解网络瓶颈问题,延长网络的整体寿命。     

基于点线回路优化求解TSP的一个新算法

快速有效地解决TSP问题,有着重要的理论价值和极高的实际应用价值。提出了基于点线回路优化求解TSP的算法,首先将原基本回路切去一些点(线段、路径)变成残缺回路,然后把切去的点(线段、路径)重新插入到残缺回路的所有节点之间,生成新的基本回路,切去点(线段、路径)的数量,从一个变到基本回路节点数的一半。算法实现容易、运行速度快,生成的结果接近其最优解。算法尽量避免了陷入局部极小,使得在短时间内能够求解较大规模的TSP问题。     

基于BDD的图表示及其算法

给出基于二元判决图BDD的无权图和有权图的符号化表示,同时给出该表示下的算法设计及实现,并以连通度算法和最短路径算法作为例子。     

基于递归BDD的网络系统可靠度算法

在网络系统可靠度的BDD算法中,将网络系统表示成BDD时二叉树中存在一定重复和冗余项,从而影响了不交化最小路集的搜索效率.为此,提出了一种基于递归BDD(RBDD)的网络系统可靠度算法.在该算法中,RBDD包括2个二叉树,一个是包含1个伪叶节点的二叉树,另一个是伪叶节点对应的二叉树.理论分析和实例都表明由RBDD得到的...     

改进的贪婪算法在无人机组网中的研究与应用

针对小型军用无人机平台小、速度快、能量有限导致的集群组网中节点生存时间受限、投递率低等问题,借鉴贪婪算法,提出一种复合权值的无线自组网路由算法。为减小边缘节点和低能节点对路径的影响,在算法中添加了边界评价因子和能量均衡2个优化参数对节点进行筛选,再利用Dijkstra算法的思想寻找网络中能量-拥塞复合权值最小的转发路径进行数据传输。仿真结果表明,与AODV算法和AOMDV算法相比,该算法在投递成功率、端到端时延、网络生存周期、路由开销方面均有良好性能。     

油田监测系统的ZigBee路由算法节能优化

根据油田监测网络的部署特点,对ZigBee路由算法进行节能优化.给出了节能优化算法的实现方法,不但考虑路径的长度,还充分考虑节点剩余能量,减少网络瓶颈节点.采用NS-2软件进行仿真分析,仿真表明,优化算法可以延长网络生存期.     

障碍物下辅助力导引IWD优化传感器部署策略

为进一步提升传感器节点部署算法性能,提出基于智能水滴优化(Intelligent water drop algorithm,IWD)辅助力导引的传感器节点部署算法.首先,对障碍物存在情况下的结构模型进行设计,给出该模型的路径损耗指数和通信半径的计算策略,同时对传感器节点IWD优化部署策略进行流程设计;其次,为增强传统IWD算法性能,采用辅助力导引方式对传统IWD进化泥土参数更新进行重新设计,增强泥土更新后水滴多样性保持效果,从而实现算法性能提升;最后,利用MATLAB制作了大小为60m×70m,规模为100组节点,包含障碍物4个的仿真算例,并选取标准IWD优化策略和差分进化算法作为对比算法,对所提算法在传感器节点部署上的覆盖率和效率优势进行验证.     

最少波长数算法实现波分复用的时域复杂度改进及对比研究

优化降低波长转换次数成为光纤传输当前的研究热点,为了进一步改进波分复用技术的传播速度,做了以下工作:提出了计算源节点与各目标节点之间的最短路,以获得所要的组播树;应用波长图的设计、MPH算法实现最小成本树,完成了这次改进算法的设计;理论上分析了最少波长数的实现、波长和路由分配,验证了算法的合理性。从建立的仿真模型结果表明:算法在计算最少波长转换次数、位置确定方面具有明显的优势;达到了WDM网络的成本降低,网速提高的目的。通过与传统的Dijkstra与Floyd算法对比设计的算法在时间复杂度、空间复杂度以及结合性方面有着一定提升。这一研究对于WDM网络传输的改进具有明显的意义。     

能量感知多路径负载均衡路由算法

针对移动自组织网络的网络拥塞问题,基于能量感知技术并结合负载均衡和拥塞控制方法,提出了一种能量感知多路径负载均衡路由算法。该算法利用能量感知选择满足条件的节点作为路由节点,建立多条连接源节点和目的节点的有效路径;同时分析路径的跳数、节点缓冲区的占用情况,从有效路径中选出用于传输的最优路径;然后对最优路径上的节点和路径的负载情况进行建模分析,当节点能量、节点负载、路径负载到达设定的阀值,就将最优路径上的流量分流到其它路径。利用NS2仿真软件,在不同的场景下对该算法以及QMRB、SMORT进行仿真测试。仿真结果显示:提出的算法与其它路由算法相比将网络性能提升了近20%,起到了均衡负载的作用,能有效地解决网络拥塞问题。     

移动机器人全局动态路径规划融合算法

针对移动机器人全局动态路径规划效率较低的问题,提出一种基于安全A^*算法与双速度模型动态窗口法的全局动态路径规划融合算法.首先,通过安全A^*算法得到全局最优路径节点,将其作为临时目标节点,为动态规划提供全局信息,避免出现局部最优.然后,采用时间序列Bottom-Up算法减少路径节点数,从而减少迭代次数、计算代价和储存代价,提高算法效率.最后,采用双速度模型对动态窗口法进行改进,通过避障重规划机制,解决全局动态路径规划时移动机器人绕远甚至绕圈的问题,并通过MATLAB平台进行仿真实验.仿真结果表明：文中算法的规划效率可提高46.18%,保证了路径的安全性和移动机器人速度的平稳性,文中算法的路径质量和规划效率更佳.     

PRM路径规划算法优化研究

针对限定环境下移动机器人路径规划问题,运用PRM(probabilistic roadmap method)算法进行初始路径规划,并提出一种基于改进的节点增强法与几何平滑策略的路径优化算法.利用节点增强法对初始规划路径进行优化处理,采用新增节点逐步取代原路径节点,减小路径中的拐点个数,从而缩短路径长度.同时采用一个基于几何平滑策略对优化路径进行平滑处理,以达到路径平滑的目的.仿真结果表明,该优化算法不仅能有效降低搜索路径的长度,而且能大幅度提高路径的平滑度.     

基于打破对称性的快速寻路算法

基于Java实现了跳点搜索算法,给出了算法实现的过程.实验结果表明:跳点搜索算法找到了一条从起始节点到目标节点的最优路径,且能够有效地识别和消除网格地图上的路径对称性,大幅度减少了节点扩展的数量.对比A*、宽度优先搜索、最佳优先搜索和Dijkstra可知,在所求解的路径长度一致的情况下,跳点搜索在平均搜索时间上显著快于其他算法.因此,跳点搜索是快速、高效的.     

基于启发式策略的最短路径算法

在讨论经典Dijkstra算法和启发式策略算法（A^＊,矩形算法等）的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径．该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间．该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果．实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50％的搜索节点数和搜索时间．     

一种基于排序的旅行售货员问题算法：（Ⅱ）搜索范围的确定

本文在本篇论文第一部份［１］的基础上，讨论了如何通过缩小路径起点的取值范围来缩小搜索范围，以达到既减少计算量，又能取得较大的搜索最优路线成功概率之目的．本文利用数据处理技术中Ｚｉｐｆ定律的有关假设与结论，证明了：当城市数目ｎ增大时，用本算法得出的最优解逐渐趋近于在原来未缩小的搜索范围内得到的最优解，而由本文确定的实际搜索范围远远地小于原搜索范围。     

一种改进工业自动导引车路径规划算法

为了解决当前工业自动导引车(automated guided vehicle,AGV)栅格地图下路径规划算法存在路径转弯较多、弯曲度较大、搜路时间较长且距离障碍物近等问题,基于A?算法提出了一种改进路径规划算法.首先,通过在全局地图中设置路径关键节点,生成关键点拓扑地图,并利用Floyd算法进行最短路径规划,输出路径节点集合;其次,利用A?算法对集合中相邻节点进行路径规划,并将生成的路径进行拼接;最后,通过引入贝塞尔曲线对拼接路径进行平滑处理,以获取全局路径.实验结果表明:本文算法规划的路径转弯更少、弯曲度更小、搜索时间更短且能完全避开障碍物行走,更符合工业AGV的应用环境.