针对公交的最优路径算法

在总结公交网络特点的基础上,提出了运用“燃烧”算法来计算公共交通系统的最优路径算法。并用一个简化的例子来说明了这种算法的算法流程,最后结合北京公交网络的一些数据,对这种算法以及经典的Dijstra算法做了几点比较,无论在空间还是时间复杂度上这种算法都大大优于Dijstra算法。     

一种移动机器人全局最优路径规划算法

针对移动机器人全局最优路径规划问题,首先提出一种基于线性操作的遍历式算法,该算法通过场扫描方式生成步长转换矩阵(STM,Step Transform Matrix),并在步长转换矩阵中搜索考虑方向一致的最短路径,从而可以得到避免不必要路径转折的全局最短路径.其次提出了一种评价标准来区分路径优劣.最后通过仿真与圆形波传播算法进行了路径规划对比实验,实验结果表明本文所提算法在所提出的路径评价标准下可以获得比波传播算法更优的路径.     

最优路径森林分类算法综述*

针对快速分类算法最优路径森林（OPF）分类算法进行了研究。进行了OPF分类算法研究及应用现状的调查。OPF算法是近期兴起的一种基于完全图的分类算法。在一些公共数据集上与支持向量机(SVM)、人工神经网络（ANN）等算法的对比中,该算法能取得类似或更好结果,速度更快。该算法不依赖于任何参数、不需要参数优化、不需要对各类别的形状做任何假设、能够处理多类问题。旨在全面系统的向国内读者介绍OPF算法的研究及应用进展。     

复杂网络环境下一种面向对象的最优路径算法研究

为了更好地描述现实世界中复杂的网络环境,采用面向对象的方法设计了跨图层的道路网络结构。文中从节约存储空问、提高运算速度出发,在Dijkstra算法基础上,对其进行改进,给出了算法面向对象的实现方法。最后将此面向对象实现的算法应用于上海市区道路图来寻找两点问的最优路径,结果证明算法有效可行。     

基于MapX的公交网络最优路径研究

Mapx是Maplnfo公司向用户提供的具有强大地图分析功能的ActiveX控件产品。分析和讨论了公交网络的特点及公交最优路径算法,充分利用MapX控件的属性和方法以及面向对象语言的灵活性对公交网络最优路径进行分析。基于MapInfo平台建立了公交网络空间数据库和属性数据库,给出了在VC＋＋可视化环境下基于MapX控件的公交网络最优路径实现方法及其应用。     

公交出行最优路线查询系统设计

针对目前城市公交出行最优路线研究存在的问题,重点增加了对合理区域内步行换乘和站点、路线的等级划分等因素的考虑.首先建立站点和路线数据库表,起讫两点双向展开搜索,充分考虑合理区域内步行换乘的情况,利用公交路线集合求交集和公交站点集合求交集的方法查询出公交出行最优路线候选方案集,然后对路线等级、站点等级和里程进行综合比较,最后选取公交出行最优方案.利用该算法进行模糊化查询可实现一次换乘的候选方案更多,真实地反映出公交出行的实际换乘情况,提高了出行效率.     

一种限制搜索区域的多比例尺最优路径规划算法*

针对现有大区域范围路径规划算法存在的一些问题,提出一种限制搜索区域的多比例尺最优路径规划算法。该算法在进行路径规划时,一方面根据路网的多比例尺信息对路网进行分级,另一方面对搜索区域进行合理限制。测试实验表明此算法可以提高路径规划的效率。     

动态交通网络中最优路径查找算法*

在真实交通网络中,可能出现某高速公路在某一时刻内通过的车辆过多,从而改变了该时刻道路的即时速度,这就需要对道路的交通流量进行监控。针对这一问题,通过建立交通网络的速度模式库,根据道路可达速度的变化更新速度模式。基于A*算法与速度模式库,提出针对动态交通网络的最短路径查询算法。采用真实数据集对算法进行测试,结果表明,应用该方法能够有效地解决在速度模式发生变化的情况下最优路径的查找,使交通网络中的最优路径查询更为准确有效。     

一种基于层次图模型的最优路径算法

论述了一种新的基于层次图的最优路径算法,即将一个平面图划分若干子图,子图抽象为一个高层图。最短路径的计算首先在高层图中进行,缩小了最优路径的查找范围,降低了最优路径计算的时间开销。     

高效的多关键词匹配最优路径查询算法KSRG

为改进基于关键词的最优路径查询算法,在大规模图以及多查询关键词下复杂度过高与可扩展性不足的缺陷,依据查询关键词序列构建候选路径的策略提出一种高效查询算法。该算法在路径构建过程中优先满足查询关键词的全包含条件,以关键词引导下的路径拓展替代盲目的邻边拓展,从而高效地构建候选路径;通过变量缩放与无效路径裁剪,将问题求解复杂度由阶乘级转化为多项式级,进一步降低算法复杂度,提升可扩展性。通过四组图数据集下的实验,验证了算法在查询效率与可扩展性上的提升。     

公交网络路径规划问题中的一种高效索引方法

TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引。TTL采用Time-dependent Dijkstra为核心算法构建索引,存在两个不足：大量的昂贵的出堆操作拖慢了建立索引的效率以及所求得的路径具有较多的换乘次数。针对这两个不足,提出了一种基于旅程的索引TAIL。TAIL预先生成部分路径,在查询阶段通过匹配部分路径得到最优解,避免在原图上做查询,提高效率。TAIL并不是基于图结构,而是以旅程为单位存储公交数据。在生成路径时,首先扫描路过起点的旅程,找到从起点直达的站点;然后扫描从直达站点出发的旅程,找到一次换乘可达的站点;如是这般,从可达站点出发扫描旅程,发现更多的可达站点。为了在早期找到最早到达路径,从而减少旅程的扫描量,TAIL并没有严格按照换乘次数的顺序扩展站点。这种方法避免了昂贵的堆操作,也保留了旅程的完整性。在真实数据集上测试表明,与TTL相比,TAIL有较短的建立索引的时间,生成的路径的换乘次数也较少。     

求解广义旅行商问题的混合染色体遗传算法

提出了针对广义旅行商问题（GTSP）的混合染色体遗传算法（HCGA）。目前,广义染色体遗传算法（GCGA）是求解GTSP问题的最好方法,但这种方法在编码设计上存在不足,使得算法全局搜索能力较差。在GCGA算法基础上,设计了二进制和整数混合编码的染色体,并更新了交叉和变异算子设计,得到改进算法HCGA。理论和实验结果都说明：HCGA比GCGA等多种算法具有更强的全局搜索能力。     

A demand based route generation algorithm for public transit network design

This paper presents a public transit network route generation algorithm. The main contribution of this work is the introduction of new route generation algorithms. The proposed route generation algorithm is tested on Mandl׳s Swiss Road network and the four large networks presented in recent previous work. Three parameters are used to evaluate the route sets generated by the proposed algorithm. These are the zero transfer percentage, the average travel time, and the total route cost. The route sets generated for the large networks have better parameter values compared to recent previous work.     

智能交通在数字化社区服务平台中的研究与实现

通过对常见的最短路径及其算法的分析,指出以往的最短路径算法不能实现公交路线的查询,提出更适合公交查询的最短路径算法以及在数字化社区服务平台中智能公交系统的实现。     

室内外一体化最优路径分析算法实现

为了弥补传统路径导航服务在室内立体空间方面的不足,提出了一种室内外一体化的网络数据模型和最优路径分析解决方案。以几何网络模型为基础,设计了一种楼层数据偏移策略,实现室内三维空间路径拓扑模型快速构建和二维可视化表达。对开源pgRouting库内置的高效Dijkstra路径查询函数进行扩展,实现了基于PostgreSQL库的任意两点之间最优路径和转弯方向语义信息查询。最后,利用GeoServer和OpenLayers等开源软件开发了室内外一体化路径查询原型系统,并采用大规模室内外一体化路径网络模型数据进行测试,定性与定量分析对比结果验证了该方法的正确性和高效性。该方法能够最大化兼容城市交通网络数据和成熟的最短路径分析算法,具有普适性与实用性。     

公交线路查询系统的数据库设计

本文以公交线路查询系统为例。对数据库设计进行了研究。从不同角度考虑,设计出不同结构的数据库．可以看出数据库结构设计对数据处理操作的影响。本系统使用Visual Foxfro6作为开发工具,通过数据库表的逐步设计,实现了预定功能。     

改进的蚁群算法在动态路径诱导中的应用研究

针对基本蚁群算法收敛速度慢和易陷入局部最优的缺点,在对信息素和启发信息进行标准化以消除量纲和取值范围影响的基础上,提出带方向的信息素更新和混沌选择策略来改进蚁群算法。将路网节点间的相对位置信息引入信息素更新,以加快搜索速度;使用混沌扰动改进选择策略,以避免出现早熟停滞现象。并将其用于城市交通动态路径诱导的研究中,以重庆市渝中半岛的路网为实例计算以最短行程时间为目标的最优路径,结果表明该算法是有效、可行的,比基本蚁群算法具有更好的全局搜索能力。