基于换乘次数最少的公交网络最优路径模型研究

结合乘客出行心理分析,提出以换乘次数最少为目标的公交乘车模型。在公交网络建模方面,综合考虑公交站点空间关系,提出空间数据到拓扑模型再到搜索模型的公交网络双层建模方案。通过搜索模型的建立,将最小换乘次数问题转化为两点间的最短路径问题进行求解。在搜索算法的设计上,首先提出改造的边权为1的Dijktra算法,以此为基础设计前驱节点算法。并以前驱节点算法为前提,设计所有最短路径算法,能够高效地求解两点间的所有换乘次数最小的乘车方案。最后,以大连市公交数据为例,验证了建模方案和算法的可行性。     

针对公交的最优路径算法

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

最短路径算法在公交网络中的应用

在纷繁复杂的城市公交网中,如果想寻找到一条从当前某个站点到达另一个目的站点的最短路径,应该怎样实现呢?针对这个问题,采用数据结构中最短路径的思想进行了思考和研究,并采用Dijkstra算法来实现搜寻计算操作和过程。     

基于换乘次数最少的公交网络最优路径模型研究

结合乘客出行心理分析,提出以换乘次数最少为目标的公交乘车模型.在公交网络建模方面,综合考虑公交站点空间关系,提出空间数据到拓扑模型再到搜索模型的公交网络双层建模方案.通过搜索模型的建立,将最小换乘次数问题转化为两点间的最短路径问题进行求解.在搜索算法的设计上,首先提出改造的边权为1的Dijktra算法,以此为基础设计前驱节点算法.并以前驱节点算法为前提,设计所有最短路径算法,能够高效地求解两点间的所有换乘次数最小的乘车方案.最后,以大连市公交数据为例,验证了建模方案和算法的可行性.     

基于路径集合运算的公交网络寻径算法研究

大规模多换乘网络中最短时间路径精确查询的算法是公交网络寻径问题的研究难点之一,近似搜索算法的求解满意度不高,而精确搜索算法的效率较低.提出了基于路径集合运算的公交网络寻径算法,按换乘次数从低到高依次求取路径集合,通过删除大量冗余路径来优化路径集合并减少计算量,最后生成最短时间路径汇总集合用于快速精确寻径.实验结果表明了算法的可行性和有效性.     

最短路径问题的一种高效实现

本文通过时Dijkstra最短路径搜索算法的分析,从数据存储结构方面对此问题进行了探讨,并提出了一种数据文件结构,实验证明该实现具有较高的效率.     

动态网络中一种高效的最短路径树维护算法

现有的动态最短路径树算法在某些边的权值频繁变化时,会造成动态网络中的最短路径树频繁更新,而且当网络中的路由器毁坏或增加新的路由器时,该算法难于应用到构造最短路径树中。针对上述问题,提出一种最短路径树的维护算法。对权值频繁变化的边进行处理,避免将其加入到最短路径树中,减少最短路径树的更新次数,当网络中的路由器毁坏或者增加时,通过减少冗余边的入队操作,对网络中的最短路径树进行维护。实验结果表明,与高效的最短路径树动态更新算法相比,该算法的更新时间效率更高。     

基于备选路径集的在线最短耗时公交换乘方法

面向城市公交出行者,在给定出行起讫点及起始时间的情况下,提出一种基于备选路径集的在线最短耗时公交换乘方法：在预处理阶段离线地运用双向广度优先搜索方法得到点对之间的静态备选路径集;结合实时公交到站时间预测数据或发车间隔等静态的公交运营数据,进行最短耗时评估,在线地从中选择耗时最短的路径。将该方法运用于沈阳公交路网案例中（公交到站时间预测数据仿真生成）,并嵌入沈阳市公交出行查询系统,结果表明了其实用性。     

网络最短路径的一种更新策略

求解最短路径问题被广泛用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动,而一旦发生改变,传统算法必须再次计算从源点到各节点的最短路径。然而虽然节点发生了变动,可是最短路径却未必全部发生了改变,这就造成了不必要的浪费。鉴于此提出一种基于Dijkstra算法的最短路更新策略,将Dijkstra算法做了改进,使其不必重新计算也能在连通图发生改变的时候更新最短路径。     

基于权值设定策略的公交出行路径查询模型

在公交查询系统中,出行者往往考虑到换乘次数、出行距离、乘车费用、线路类型等诸多因素。因此出行路径查询模型要考虑到多重目标。为此基于带权有向图定义了一个新的查询模型,该模型能够通过调整权值来满足多重查询目标,并以满足最小换乘次数、优先乘车条件和最少途经站点数三重目标的出行路径查询为例,讨论了权值设定策略。实验表明,提出的模型有效、实用,具有很好的灵活性。     

基于电子眼的应急物流运输路径自动规划研究

传统应急物流运输路径自动规划方法无法对灾区路况进行整体把握,导致规划的路径中出现道路损毁的情况,车辆无法到达,影响安全的同时,绕路延长运输时间.因此,设计一种基于电子眼的应急物流运输路径自动规划方法.首先确定电子眼的相关参数,设计其工作逻辑,完成传输图像视频的遍历检测,为路径规划提供参考,选择GIS系统中的栅格数据,作...     

物流运输网络连通可靠性分析的高效分解算法

可靠性分析是衡量物流运输网络运行服务水平的主要手段之一。给出了一种评估物流运输网络连通可靠性的高效分解算法,算法充分利用分解过程中获得的相关信息,通过引入保持网络可靠性不变的串联边化简、并联边化简以及节点合并等规则,并结合向量集分解方法,能够快速实现对网络状态向量空间的分解,达到提高网络可靠性评估效率的目的。实例分析以及和现有方法的比较验证了算法的性能和分解效率。     

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

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

一种公交网络最优路径新算法*

从出行者的实际情况出发,提出步行愿望系数,综合考虑最小换乘次数、最短时间以及最小费用等因素,提出了一种公交网络最优路径新算法,应用于广州市大学城内公交线路查询,实现相应的仿真系统。     

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

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

城市公交查询系统的研究与设计

给出了城市公交查询系统的空间数据结构。在Dijkstra算法的基础上,借助人工智能中状态空间搜索和动态截枝的思想,提出了状态空间搜索求第K最短路径的智能搜索算法。该算法能对所查询的交通路线与乘车方案等用电子地图的形式给予显示,并更换不同城市的地图。测试表明,该系统具有速度快、多媒体显示、维护方便、通用性强等特点。     

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.