文摘

计划一次旅行通过整合运输路线和时间表从不同来源的信息机构,如公交车,渡船和火车可以复杂。一个用户友好的、信息丰富的旅程计划系统可能简化计划通过提供援助在更好地利用公共交通。在这项研究中,我们提出了面向服务的,multimodel智能旅程规划系统,我们开发协助旅客旅行计划。我们选择了伊兹密尔,土耳其,这个系统的试点城市。多准则问题在交通网络是一个著名的问题。我们的研究提出了一个渐进的查询算法来解决这个问题通过考虑传输计数和旅行时间。算法利用技术的高效算法包括基于公共交通优化的路由器,交通节点路由和收缩在交通上的层次图。我们使用迪杰斯特拉算法后的第一阶段查询算法通过减少搜索空间和运行时阶段特定的规则。实验结果表明,我们的查询算法需要0.63秒的平均处理时间,这对用户体验是可以接受的。

1。介绍

大城市有一些普遍的交通问题,如交通拥堵,停车困难,排放的污染物和温室气体。政府当局支持更强的使用公共交通系统对缓解交通拥堵,减少碳排放。巨大的发展已经发生在世界各地的大城市的公共交通系统自上次几十年。因此,使用公共交通系统越来越复杂。大多数情况下,不止一个大城市的交通机构操作。路线和时间表信息,这些服务可以在他们的网站,但没有连接其他形式的运输信息。不容易集成来自不同数据源的路线和时间表信息机构的计划一次旅行。

公共交通系统的可用性可以显著增强,帮助人们更好地利用公共交通。用户友好的和翔实的旅程规划系统已经成为重要的替代路线通过提供建议。本研究的目的是提供一个智能的旅程计划系统(IJPS),协助乘客计划他们的行程。我们的动机是减少私人汽车的依赖,并鼓励更广泛的使用公共交通。由于这项工作,我们的目标是减少噪音和二氧化碳排放,避免交通堵塞和拥挤。

行程计划系统(比如伦敦伦敦交通局RATP巴黎奥地利AnachB等等正在使用在许多城市在整个世界。然而,几乎所有的商业项目。尽管如此,也有许多学术研究关注解决问题关于交通网络,包括最早到达的问题,文献中多准则问题。这些研究的一个重要部分站在图论技术,其中一个是迪杰斯特拉算法(1]。Multilabel纠正(多层陶瓷)算法(2),传输模式(3),收缩层次结构(CH) [4),交通节点路由(TNR) [5],trip-based公共交通路由(TB) (6)可以体现这一类。其他的研究,包括基于圆公共交通优化路由器(猛禽)[7)和连接扫描算法(CSA) (8),不是Dijkstra-based。他们使用数组组织时间表信息或基本时间表连接。一些研究执行预先计算使用预先计算的数据的表查找最短路径查询(3- - - - - -5),而另一些则不依赖预处理[7,8]。

在城市地铁等基础设施不足伊兹密尔,公交线路满足公共交通需求的重要组成部分。例如,最多8在巴黎地铁线路相交在一个转运站,55公交线路相交在伊兹密尔的转运站。这就增加了密度和交通网络的复杂性。本研究的主要贡献是一种新型的建议逐步查询算法(GPFA)解决多准则问题在这样密集的网络。GPFA有一个混合的方法,利用一些有效的算法的技术,包括基于公共交通优化的路由器,交通节点路由和收缩在交通上的层次图并修改Dijkstra算法快速计算的查询。第二,IJPS介绍表明替代路线通过考虑模态转移和用户首选项。另一个目的是告知乘客利益(POIs),停车场和事件(音乐会、展览等)位于他们的路线。因此,乘客将被鼓励社会和文化活动的开展,由于这种独特的特性。

论文的结构如下:部分2州多准则问题。部分3讨论了现有技术,适用于解决这个问题。部分4介绍了GPFA,我们的主要贡献。部分5概述系统的架构,并提供了实现细节。部分6介绍了场景分析结果,最后,部分7总结了论文的工作总结以及未来的发展方向。

2。问题定义

在图论中,图是一组顶点(节点) ,和一组边缘的形式 ,在那里 是要求不同的顶点。一个路径是一个连续的序列节点和边制定的吗 ,对于每一个( );边缘连接和 。路径的长度等于 ,边的数量遍历。定义为一个路径最短路径从原点到目的地如果路径从节点和结束节点的最短长度之间的所有路径来 。

找到所有可能的路径图中任意两个节点之间有大量的节点就是一个典型的例子的问题领域的计算复杂性理论(9]。这些问题需要大量的计算和内存地址来解决。而不是寻找所有路径,处理是最好的路径通常是首选的技术(10,11]。的最短路径问题是一个扩展算法的单源最短路径问题。单源最短路径问题发现从一个源节点最短路径到目的地(是平衡的 ,这是图中的所有节点的集合)。日元的算法是一种基本的处理工作最短路径问题12]。不仅找到最短路径,而且第二个最短,第三最短,等等的最短路径的成本增加。它使用迪杰斯特拉算法(1),或任何其他最短路径算法,找到最好的路径。数以百计的研究提供新的解决方案或改善现有的算法(13- - - - - -15]。

公共交通网络,有两个著名的问题定义(16]。最早到达问题只考虑时间的优化准则。当转移或其他标准的数量被认为,这个问题又被称为多准则问题。在这项研究中,我们想要见图回答这个问题1:“对于一个给定的起飞时间 啊,怎么可能从起源到目的地d最少的转移和最短旅行时间考虑模态参数和一个可接受的步行距离?”在一个可接受的响应时间。在这种情况下,最佳路径根据旅行不仅仅是一个最短的时间;这里,转移数量和用户首选项必须考虑,。

多准则问题有许多挑战需要克服。相比静态的公路网络,公共交通网络更困难模式,因为它们减少对大都市的分层次结构(17]。此外,这些网络中基于事件和需要建模时间的方法。许多算法执行在公路网络不能表现良好或甚至在交通网络失败。虽然基本路由只考虑静态边与旅行时间,交通网络使用一个旅行时间函数取决于所选的起飞时间。在多准则优化,需要考虑多个标准包括旅行时间和转移的数量。还根据用户偏好,可接受的步行距离,模态转移,必须考虑和车辆类型的限制。认为只有最好的路线,而是一些有利的选择应提供给用户。此外,预先执行更复杂的公共交通路由和预先计算的数据必须过滤有效地根据变量查询参数。

3所示。相关的工作

最近有很多旅行计划的发展近年来公共交通系统。高效的算法技术(通常基于Dijkstra算法)进一步发展了公共交通系统。韧皮等人给了一个优秀的调查,这些技术(16]。主要time-expanded和时间的方法已被用于模型时间表信息(2]。在time-expanded方法(18)每个节点模型出发或到达的事件。连续的出发和到达的事件是通过连接边缘连接。在时间的方法19),每个节点分配模型的一个火车站和一个边缘两个节点之间是否存在对应的两个站之间的直接连接。边的权重分配“动态”与旅行时间相关函数。最早到达的问题,Pyrga等人表明time-expanded方法构造大型图表和收益率差查询性能与时间的方法(2]。因此,在这项研究中我们集中在时间模型。

其中一个算法在时间依赖模型是multilabel纠正(多层陶瓷)算法,旨在找到所有帕累托最优解决方案(2]。被称为帕累托最优的路径如果另一个路径不占主导地位。多层陶瓷可以处理多个标准,由多个标签边缘建模为每个标准广义Dijkstra算法的算法。时间依赖模型的另一个技术转移模式(3]。它预计算和商店每个序列中间转运站可导致最优路线为每个源站所有从A组可获得站B这些序列的转移被称为转移模式,实现快速查询时间。收缩层次结构(CH)也是一个依赖于时间的技术执行预先计算节点收缩(4]。它逐渐从图中删除节点,添加快捷方式保存最短路径。CH已经应用于多模式交通网络(20.)和时间依赖模型(21]。每个顶点算法维护多个标签以确保最低转数。交通节点路由(TNR)是另一个技术决定了少量的交通节点,每一个最短路径穿过至少一个节点(5]。距离从每个节点预先计算的最亲密的交通节点(访问节点)用于表查找最短路径查询。TNR已经应用于公共交通旅行计划(22]。Trip-based公共交通路由(TB)是一种不同的方法,它使用一个图,节点代表旅行(不停止)和边代表旅行之间可能的转移(6,23]。两阶段预处理步骤是需要计算所有可能的转移之间的旅行和丢弃多余的转移。结核病递增的顺序决定了最优路线转移。

一轮基础公共交通优化路由器(猛禽)[7这不是Dijkstra-based)是一种不同的方法。而不是使用一个图表,它使用数组的时间表信息,包括停止,旅行,路线。它不依赖于预处理和运作轮通过最小化传输计数和到达时间。戴着圆 ,确切的旅程组成转移计算。另一个non-graph-based算法连接扫描算法(CSA) (8,24]。它不是基于行程和路线(如“猛禽”);而不是基本连接的时间表组织按出发时间排序的数组中。这个数组查询每扫描一次,在实践中是非常有效的。Dib等人提出了一个启发式方法,遗传算法(GA)是结合可变邻域搜索(VNS)解决多准则最短路径问题在多通道网络25]。实验结果表明,该计算时间不是禁止集成在一个在线旅行计划系统。

我们建议逐步查询算法技术发布的公共交通网络,利用不同的算法。像猛禽一样,我们的算法有一个圆的基本方法取决于传输计数,但基于图论Dijkstra算法。转移中心在我们的算法(伊兹密尔的主要物品运输)对应于TNR交通节点技术。在预处理步骤中解释的部分4.1,我们发现和记录可用路径两转移在所有转移中心。我们从收缩启发层次结构插入每个转移中心副之间的捷径,这是通过一个直接连接的路线。

4所示。渐进的查询算法

在这项研究中,两个主要部分的IJSP已经开发了在面向服务的模型。这些主要部件更新服务和旅行计划Web服务(JPWS)。更新服务是一个Windows服务应用程序,每天晚上执行一些预处理任务。JPWS是一个Windows Communication Foundation (WCF) web服务和为客户充当路由引擎。

预处理任务包括四个步骤,即收集和转换传输数据,确定附近停止,可以转移中心,对路线规划在所有转移中心。JPWS旅程有一个方法,参数从用户应用程序和使用GPFA产生不同的路径。算法模式的更新服务和JPWS图给出2。部分4.1和4.2给详细解释的预处理任务和GPFA,分别。

4.1。预处理任务

站在一个通用的数据格式使应用程序能够在所有交通系统开放交通数据已经发布,常见的数据可用任何开发人员使用。一般运输饲料规范(GTFS)是一种常见的数据格式,这六个要求提要和七选提要代表停止,路线,旅行,和其他计划数据的交通网络(26]。在过去的年里,GTFS已成为最流行的格式和有1000公交公司提供GTFS数据截至6月,2017年。运输机构在伊兹密尔交通数据存储在不同的格式。更新服务从运输机构,收集当前数据集按照GTFS格式,并将它们存储到数据库中。伊兹密尔所需的所有提要生成运输网络。

点对点查询在交通网络中,需要一些脚边。是这样,任何阶段的旅程可以步行,或者乘客之间停止行走在两条线之间的转移。脚边还提供交通网络的各个部分之间的联系(公共汽车、火车、地铁、渡轮)在生成的多通道网络 。两个站和被添加的脚边(贴上附近停 和 )之间的距离 小于最大步行距离。附近停止使用欧氏距离计算。

TNR预计算技术从每个潜在的来源或目的地的连接,其访问交通节点和交通节点两两之间5]。在伊兹密尔,主要运输线路的火车,地铁和轮渡。乘客使用这些线可以转移到一个公共汽车线路达到他们的邻居。目前,有20个转移中心,位于主要在火车、地铁、轮渡站,每个包括34个停止。两个远程点之间的乘客旅行可能会通过一个或多个转移中心。我们的查询算法使用这个逻辑假设转移中心“访问中转节点”中文技术。因此,确定访问传输中心每个站是一个预处理,将更新后的交通数据。在这项研究中,一个可转让中心停止意味着至少有一个路径两停止和转移中心之间的转移。

查询的预处理计算和记录两转移的路径可用在所有转移中心。如果我们把运输图 ,由一组传输中心 ,和每个转移中心有一组停止 ,一组路径 对于每一个和( 和 )计算并存储在一个数据库表中。 是一个路径,没有或只有一个转移。符号描述了本文中使用的符号。

4.2。算法

在这项研究中,每一站(公共汽车、火车、地铁和轮渡)被表示为一个节点;一条连接两个连续停止在一个特定的方向是表示为一个有向边缘,从而形成一个运输图。如果两个停止在步行范围内,它们互相连接到脚边。通过脚边不同线路之间发生转移。车边的边的权值表示为平均旅行时间覆盖指定的运输环节。每条边的平均旅行时间是由一个旅行时间计算函数使用的统计旅行时间传输段在给定的时间间隔(例如, )。脚边的边的权值计算的地理交通段的长度和假设平均步行速度一个行人的6公里/小时。JPWS启动后,路线和时间的表数据,用于创建一个静态交通图像,加载到内存用于查询执行一次。为每个单独的查询,一个新的辅助图形是由静态图没有任何数据库查询。这副图是用于计算替代路线。节点和边user-unpreferred交通模式并不包含在辅助图形。

两行之间的传输需要时间,包括行走之间停止和连接线等。乘客们自然希望减少这等待时间27]。此外,乘客都是禁用的,年长的,背着沉重的行李或用更少的转移孩子们通常喜欢旅行。因此,我们开发了GPFA,产生一个路径主要是用更少的转移,然后根据其他标准。查询操作在最多五个阶段完成。如果必要数量的路径来实现最短路径不能被识别,继续下一阶段的操作。起飞时间的计算生成的路径,然后进行过滤和排序的结果。GPFA出现在图的阶段2。如果超过路径通过的最后阶段,只有旅行与得分最高显示给用户。

可能会有多个起源和多个目的地停止,这对应于选定的点。因此,唯一的问题是减少通过运行修改后的迪杰斯特拉最短路径问题的算法为每个起源停止所有目的地停在阶段2,3,5。我们修改Dijkstra算法的确定动态边忙边通往目的地。最短路径计算的总旅行时间的路径的总成本路径。所以,我们可以获得最快的路径传输计数我们目前工作。在我们运输图,转移中心节点之间的直接路线作为快捷方式绕过中间节点在旅行计划。这种方法是收缩的适应层次结构(21]。

我们有一个示例场景,如图所示3解释和澄清一些定义。乘客想要到达Dokuz Eylul从医学院大学工学院,位于不同的地方。他是准备从9点半在原点。保持简单,我们只显示停止转移。每个运输连接的行程,我们在几分钟内给旅游时间和到达时间在下一次传输停止(例如,)。GPFA建议路线选择通过考虑转移数量和旅行时间。在第一阶段,该算法检查常见的线之间存在和 ,这意味着直接起点和终点之间的路线。在这个场景中,没有直接的线连接的起源和目的。在第二阶段的算法,包含只有一个转移生产路线。在这种情况下,一个原点,即总线- 554,连接到一个目的地的线路,即总线- 304,散步。乘客等待5分钟的第一个服务总线- 554,当他到达原点停止。他游历32分钟后通过总线- 554,他下车后停止,走1分钟到达停止 。在那里,他等待1分钟上车- 304。经过40分钟的旅游巴士上- 304,然后他凌晨10:49到达目的地。在第三阶段的算法,包含两个转移的路线被发现。根据建议的路径之一,这个阶段,公共汽车的乘客可以开始旅程- 554,然后转移到Metro-31和总线- 490,分别到达目的地10:53点。在接下来的阶段,GPFA发现两个转移的路径,通过至少一个转移中心。在这种情况下,建议路径包括公共汽车- 554,Metro-31, Train-22,分别和总线- 878。的最后阶段发现的算法传输路径不运行在这个例子中,路径(被认为是3)已经获得。

起源的一些线路(如总线- 950)是在晚间时间晚上只有服务操作。这些线不采取任何一部分的结果选择出发时间。算法消除了所有路径包含线造成不可接受的等待时间。因此,时间表限制路线选择从时间和空间的角度,因为它是在28,29日]。下面的各个阶段GPFA将详细解释。

4.2.1。准备找到直接的路线

直接路径,没有转移,计算通过使用起源和目标线 。为一条线 ,如果 和 ,我们可以这样说是一条线,到达目的地从原点没有转移。一个路径在这个阶段获得的只有一个子路径,其中包含线 。形成直接路径每一行存储在简笔列表防止使用它在计算和传输路径。直接路径是通过使用静态数据没有任何数据库查询和最短路径算法。

4.2.2。找到包含一个转移的路线

在这个阶段的算法,其目的是找到一个路径,从一本线,结束于一个目的地。原点和目标线必须连接传输停止或必须有两行之间散步。迪杰斯特拉算法的修改版本开发获取路径从一个原点线开始和结束与目标线。该算法允许从一个原点开始,转移到目的地,到达目的地停止使用这条线(图4根据给定的限制如下:(我) , 。(2) 。(3) , , 。

在我们的算法中,每个节点(停止)的权向量的大小对外行数。与我们的方法,与传统的图,边不知道过程的开始。重量值被分配根据算法运行时的限制。边的权重,不满足这些需求仍然是无穷,而另一权重确定旅行时间函数。对应规则的最小费用路得到结果并返回路径对象。

修改后的版本的迪杰斯特拉算法运行每个起源行 。我们使用两个成本值和的算法。用于查找路径用更少的停止什么时候被用来确认用更少的行走路径。后找到一个路径传输,新生成的路径替换第二行与平行线使用静态数据。一个平行的线是一条直线,穿过第一站的最后一站在生产子路径。平行线然后添加到 。如果无法找到必要的路径计算,算法再次运行不用去寻找另一个路径和它的平行线。这一阶段持续直到找到路径,或与一个传输路径可以不再被发现任何行 。伪代码修改的迪杰斯特拉算法的路由算法中给出了包含一个转移1。

4.2.3。找到包含两个转移的路线

如果必要的路径数(无法找到路径)在阶段1和2(图2),继续通过识别过程包含两个转移的路线。在这个阶段,缘分 ,这与目标线相交停止直接或通过一个走路,决心。算法找到的路径从一个原点开始,继续一个缘分,与目的地和结束。任意线可以连接在一个传输停止或可能有两行(图之间散步5根据给定的限制:(我) , 。(2) , , 。(3) , , 。(iv) 。

修改后的迪杰斯特拉算法的伪代码路线包含两个算法中给出了转移2。在这个版本的迪杰斯特拉算法中,每个节点都有一个传输数财产除了距离财产。转移数属性用于保存转移的每个节点的最小费用路计数。发现有两个传输路径之后,新生成的路径替换第二行与它的平行线,然后取代第三行平行线。 , ,然后他们的平行线是添加到 。如果必要的路径数仍不能发现,该算法再次运行找到一种替代的路径不使用行 。这一阶段一直持续到生产路径或路径有两个传输再也不能与任何被发现 。

4.2.4。发现使用转移中心路线

如果必要的路径数为零,一个,或两个来源和目的地之间的转移无法找到停止,必须进行路径搜索在两个传输。考虑到交通基础设施在伊兹密尔,一个人做两个遥远的点之间的旅行可能会通过转移中心。在这个阶段,目标是找到路径超过两个转移和通过至少一个转移中心。如上所述,确定访问传输中心所有停止和查询每个转移中心之间进行预处理是通过更新服务。

使用传输中心查询过程可以发生在两种情况如图6。在第一种情况下,出发地和目的地停止共同访问传输中心(图6(一))。在这种情况下,零转移的路径和一个原点之间传输计算停止和常见的技术转移中心的指出阶段1和2。如果没有找到路径,路径有两个计算转移。相同的过程是常见的转移中心和目的地之间进行停止。之间的路径发现起源和转移中心;是一组之间的路径发现转移中心和目的地。结果集通过交叉生产吗和 ,在哪里 和 。

在第二种情况下,出发地和目的地停止没有常见的转移中心(图6 (b))。路径与零转移和一个原点之间传输计算停止并转移中心访问 ;路径有两个传输计算,如果必要的。相同的步骤进行转移中心和目的地停止。两个转移中心之间的路径计算和存储到数据库中,更新服务。是路径的集合之间的起源和转移中心吗 ; 是路径的集合之间的转移中心吗和转让中心存储在数据库中;是路径的集合之间的转移中心吗和目的地。在这种情况下,结果集通过交叉生产吗 , ,和 ,在哪里 和 。

交叉生产期间,如果目的地停止从一开始就停止的不同 ,他们之间插入。相反,如果最后一行的第一行是一样的吗 ,这两部分的总和。执行相同的步骤和 。

4.2.5。找到路线包含转移

如果路径仍不能生产,我们使用另一个修改版的迪杰斯特拉算法找到最小费用在两个传输路径。我们雇用一些常数改变算法的行为。常数的值添加到边缘体重每一行改变。如果转线不是一个目的地,但一个缘分,coefficient1添加到边缘的重量。如果转让行也不 ,coefficient2添加到边缘的重量。coefficient2>coefficient1,这些值是根据图中边的权值确定。添加到脚边的权重,所以少走路也有低成本的路径。修改后的迪杰斯特拉算法的伪代码路线包含转移给出了算法3。

4.2.6。算法的复杂性

在我们的实现中,所有未测量的节点用试探性的距离值作为键存储在一个优先队列的实现SortedDictionary < TKey TValue >类,搜索时间复杂度。每个节点可以从从队列中插入和删除一次。每个节点最多扫描一次,并且每条边放松一次。因此,最坏的我们修改Dijkstra算法的复杂性 。平均情况的复杂性远比最坏的复杂性感谢我们限制在访问节点和放松的边缘。

5。案例研究在伊兹密尔公共交通

人口超过400万,在土耳其伊兹密尔是第三大城市。每年大约有200000游客参观伊兹密尔,目前四个公共交通机构运作。路线和时间表信息从这些机构可以在他们的网站,但没有信息与其他形式的交通工具。

在这项研究中,我们提出的IJPS站在面向服务的体系结构(图7)协助国内外游客,当地人,城市交通的有效利用。我们选择了伊兹密尔,土耳其,这个系统的试点城市。IJPS表明替代路线,转会细节,出发和到达的时间根据用户偏好任何来源或目标点。系统提供最优路线选择根据多种标准,如预期的运输工具,最大步行距离,最少数量的变化,和最短旅行时间。IJPS运行在不同的平台上提供一个广泛的随时随地使用。应用程序可以在英文和土耳其对于移动web和桌面门户网站,在亭,为Android、iPhone、Windows Phone平台。示例屏幕如图8显示移动Web和Web应用程序。IJPS供应信息,包括天气、交通和道路条件,近似出租车费,活动中心,沿着路线和事件。

初的旅行计划,确定起点和终点。三种方法被用于确定起点和终点:从池中选择预定义的POIs,使选择停止或站名称和标记在地图上的位置。其他参数所需的运输工具,偏好关于行走之间转移,最大可接受的步行距离,和排序结果的标准。根据用户的喜好,活动中心和POIs的路由上可以显示在地图上。POIs沿途都表示为一个列表。另一个列表提供包括文化中心,如博物馆和展览、和事件中心,如电影院、剧院和音乐厅附近的路线。如果用户从列表中选择一个中心,(或将会)事件发生的日期和时间显示的旅程。

6。情景分析

在这里,我们提出一个实验性研究,调查GPFA减少搜索空间实现。一双示例查询术语叫做“Evka 3转移中心”和“Buca市政厅”执行评估阶段GPFA的搜索空间。表1显示了访问边数总计27506间边缘出现在图修改的迪杰斯特拉算法的2 - 5中使用的阶段。

访问边缘数量增加了上阶段的算法。我们减少了搜索空间为1.32%,7.89%,21.21%,77.39%,阶段2 - 5,分别;纯粹的迪杰斯特拉算法访问所有边缘的99.85%。减少搜索空间,这个学位突显出算法的良好性能。可视化搜索空间的对应和最优路径查询样例获得阶段2 - 5出现在图9。

验证的准确性、可靠性和一致性IJPS,我们创建了一个测试数据表;我们执行96107示例查询的第一站所有可用的公共汽车,火车,地铁和轮渡线线路的最后停止。从测试获得的统计信息查询如表所示2。阶段1和2被处决的100%所有查询结果独立于计数。操作继续第三阶段,因为69.2%的查询最短路径(假定为5)不能被发现在前两个阶段。第三阶段后,30.1%的查询在第四阶段实现加工最短路径(在这里也认为是5)。只有0.8%的查询,无法产生至少三个路径继续第五阶段。大约30%的所有查询结束前两个阶段;大约70%在第三阶段结束。在第一个四个阶段,我们观察到的平均运行时在1秒。但在第五阶段,平均运行时间是8.47秒,因为规则应用在这个阶段没有限制搜索空间的其他阶段。实验结果表明,我们的查询算法需要0.63秒的平均处理时间。应该注意的是,所有的运行时包含几个修改Dijkstra算法的运行。总的来说,GPFA产生精确的结果对所有查询系统用户与一个可接受的响应时间。

7所示。结论

在这项研究中,我们设计并实现了面向服务,multimodel IJPS协助旅客旅行计划。我们提出了一种渐进的方式找到与GPFA交通网络路径。我们的算法使用迪杰斯特拉算法的修改版本在几个阶段。修改后的迪杰斯特拉算法的跑几次在每个阶段根据停止和行数。我们提出了结果通过运行IJPS在伊兹密尔市的旅行计划。我们指定的边的权值动态与旅行时间相关函数。搜索空间降低了减少访问节点和边的数量修改Dijkstra算法。我们的研究结果表明,参观了边缘的数量增加了上阶段的算法。增加访问数量的边缘也导致增加了算法运行时。我们发现GPFA的平均响应时间是0.63秒。

IJPS是一个灵活的系统,可以应用到所有的公共交通工具。未来的交通工具在伊兹密尔可以集成到操作系统。IJPS有潜力被应用在任何城市。的性能可以增强IJPS结合其他multimodel加速技术。

符号

:	源节点、目的地节点
:	路径:获得路线作为路径的对象存储路线的细节
:	子路径:路径对象子路径列表,其中涉及到每个部分的路线
:	停止或站,转移中心
和 :	来源和目的地停止
:	运输线路(巴士、渡轮、地铁或火车)
:	起源:出站原产地转换站
:	目的地:入站停止转换的目的地
:	简笔列表:线形成的直接路径
:	命运线:线相交与一个目的地行停止直接或散步
, ,和 :	转换成本,走成本和转移成本。

的利益冲突

作者宣称没有利益冲突。

确认

在参与这项工作进行Unibel A.Ş.和科学技术研究委员会的支持下的土耳其拨款3110231。