文摘
本文提出另一种方法对时间多式联运问题。我们描述了一种新的图结构抽象多通道网络,电话转移图的分布式特性,适应交通网络的真实的信息来源。最短路径问题的分解转移图提出了优化计算时间。这种方法的计算测试是在几个实验多通道网络有不同的大小和复杂性。方法是集成在欧洲Carlink多式联运服务平台,它已经在现实场景进行验证。比较与其他相关工作。
1。介绍
多式联运的组合两个或两个以上的运输工具将乘客或货物从一个源到目的地1]。旅客可以使用公共(例如,公共汽车,出租车,地铁,铁路和船舶)或私人交通工具(如汽车、摩托车、自行车和步行)。多通道旅行在我们的社会成为一个真正的必要性为保证高水平的流动在城市和区域层面上(2]。
从过去的几十年里,许多研究项目是致力于发展多式联运系统,建议旅客运输方式的组合上门之旅(1,3- - - - - -5]。这些系统必须应对不同的运输信息来源,正态分布在实际场景中,也就是说,传输数据通常是由不同的公共和私人公司提供,可以存储在不同的位置。这些系统的另一个挑战是整合实时交通信息(例如,交通拥堵、延误、道路施工)为了适应现实条件提出路线。
提出了不同的抽象代表时间的多式联运问题。三个主要类别的方法可以确定:multigraph-based方法(2,6,7),约束满足问题的方法(8),和基于网格的方法9]。为了适应多式联运抽象真实信息的分布式特性,应该满足以下约束:(i)底层多通道网络被认为是平的,不包含层次结构,如区域层次结构;(2)涉及单峰网络可能是分布的,也就是说,单峰网络分别存储和访问;(3)如果有多个网络信息来源在单一模式,他们可能分布。上述方法放松这些约束建模和解决问题。
时间的另一种表示多式联运问题是部分中描述(10]。在这里,我们提出一个正式的描述这种抽象以及转移图的方法,在这个结构计算的最佳路径。这种方法测试并验证在现实Carlink平台的上下文(Carlink,无线连接汽车的平台,是一个项目的凯尔特集群项目,旨在开发一个智能无线通信服务平台之间的汽车)(11]。转移图方法提供了一个解决方案的时间多式联运问题满足定义的三个约束条件和适应真正的分布式特性传输信息提供者。
这篇文章的大纲如下。部分2描述了时间的转移图方法多式联运问题。节3这种方法计算测试。部分4描述了Carlink,真正的场景,方法验证,主要服务平台以及结果。节5结果与其他相关工作。最后,本文提出了一些结论6。
2。转移图方法多式联运问题
在现实场景中,运输信息来源通常是分布式的,也就是说,运输安排通常是由不同的公共和私人公司提供。除此之外,这些信息经常修改由于日常意想不到的扰动,如交通拥堵,延迟和道路施工。这些限制使交通管理和交通网络的更新信息。
本节介绍了转移图方法求解最短路径问题(SPP)在离散时间多通道网络。它能够计算多通道路线即使所有涉及网络保持结构和分布式分开。而不是建立一个解决方案限于多式联运系统的统一视图,我们的策略在于找到一种基本网络表示涵盖多通道网络,然后解决了SPP抽象。
转移图方法适应真实世界的交通信息资源的分布式特性,并允许独立更新每个交通网络不需要任何进一步的修改。我们的方法主要分为两个步骤。在第一步中,相关的路径计算在每一个单峰网络。在第二步中,图为减少到一个简单的时间单峰网络,在古典SPP可以解决。
第二部分首先介绍图的基本概念和定义的SPP时间多通道网络。然后,转移图抽象是正式描述,其次是的表示相关的图,一个简化的结构计算转移图。最后,图方法计算SPP转移转移图进行了探讨。
2.1。SPP在离散时间多通道网络
让表示一个有向图或网络,是一组节点,是一组传输模式(如火车、巴士和汽车),然后呢是一组弧形。一个弧可以确定了或,在那里。的意味着从节点的可能性来通过使用传输模式。一个值每个弧有关吗,表明包括弧在解决方案的成本(如距离、时间)。
定义2.1。一个图表据说是多通道如果有至少两种传输模式在哪里,,。如果只有一个交通模式的图,图是单峰。
在一个图路径或路径是一对节点之间的弧序列和,,对所有,,对所有。
定义2.2。给定一个图,一条据说是多通道如果,,。如果只有一个模式参与路径,然后是单峰的路径。
让在一个图形的路径和一个函数代表一个路径的成本。一个小型被认为是多目标映射到一个向量的维度,。每个组件,尽管之前,单目标路径代价函数的定义。
让表示时间的离散集。与nontime-dependent网络弧成本是固定的,在时间依赖网络弧形的成本根据成本函数变化对所有。
定义2.3。给定一个图和一个离散时间集弧,旅行被定义为元组,,在那里起飞时间节点,在节点的到达时间吗。Tr代表旅行的数量。
定义2.4。给定一个图和一个离散时间集,据说如果所有时间依赖网络,在哪里和所有,和。
我们结束本节通过制定的SPP时间多通道图。读者可以找到一个更广泛的描述(SPP的12]。
定义2.5。给定一个时间多通道图,两个节点和时间,SPP定义如下:计算路径从节点来离职的在时间和是最小的。
2.2。转移图
在本节中,我们提出了转移图图形结构,抽象时间多式联运网络。
一个转移图是由一组描述单峰网络和一套弧连接,它被定义为。让是一个叫做和一组单峰网络称为组件,每个,和。本身就是这样和,尽管,。与分区图,给出两个不同的组件和,有不是强制性的;然而必须始终保持。再一次,让我们定义两个不同的组件;一个节点据说是一个转帐的时候吗,也就是说,任何节点属于多个组件。最后,转移弧的连接两个组件转移图:,。
图1说明了这种抽象的一个例子,,,由三个传输组件连接,节点,,是传输点。一个源节点可以观察到和目标节点可能属于多个组件;这是因为他们可以转移点。实际上,时间依赖性和multiobjectivity不被认为是在这个例子中,虽然这种方法能够处理这些限制。
转移图抽象分离所有运输方式在单峰网络。所以,当扰动(如交通堵塞,道路施工)检测到的交通模式,它不影响全球表示,但在本地。在这种情况下,只需要更新这些组件相关的事件。根据这一特征我们可以引理2.6。
引理2.6。转移图抽象是对修改交通网络更健壮的数据比经典的多通道网络表示。
2.3。相关的图
在前面的小节我们有正式的定义转移图。现在我们提出一个简化的结构来自这种抽象,调用相关的图,可以简单计算最短路径问题。
在高级别上,在一个路径转移图可分为两组:intracomponents路径和组件之间的路径。一个组件之间的路径在一个转移图 被认为是弧连接两个节点的顺序吗至少有两个弧属于两个不同的组件。另一方面,一个intracomponent路径在是弧连接两个节点的顺序吗的弧线只属于一个组件。内部组件的路径可分为以下类别:
(我)完整路径():从源节点的最小的路线在目标节点和结束在组件;(2)相关负责人路径():最小的路线,从源头开始和结束在一个组件内的转运站;(3)相关的中间路径():最小的路线,开始和结束在任何组件内的转运站;(iv)有关尾路径():最小的路线开始任何转运站和最终目标在组件。给定一个转移图 和一个叫做副,假设所有组件我们已经计算最佳相关路径设置:,,,(见表1)。有这些相关路径集,它可以减少图来自所有可能的最好的国米组件路径从来可以计算。我们称这个图相关的图和使用来表示它。的节点是,和所有传输点的一个子集转移图。弧的最好的路径相关的内部组件被视为边缘,即路径表示只有最初的和最后的节点。事实上,是油印,但总的来说,其规模应远小于等效油印的底层转移图。这是因为任何节点出现在是一个转运站,除了原点和目标节点。因此,节点的数量直接取决于传输点的数量转移图。图2显示了有关图计算出图1。
为了正式描述,让表示为组件相关节点的集合,让的相关路径计算。从所有和我们可以分别构建对所有对所有组件相关的节点的集合,对所有为所有组件相关路径的设置。的相关的图正式描述的是一对吗。如果我们考虑用不同的离散时间时间依赖网络,然后为了构建相关的图相关,有必要计算最佳路径在任何起飞时间,也就是说,,,,,尽管和所有。
当一个相关的图是由一个转移图为节点和和时间,我们有一个时间单峰油印使用更少的节点,所有传输点之间的最短路径,和,计算。的最短路径的计算来在在减少时间基本上是古典叫做SPP单峰网络。这使我们能够建立以下引理。
引理2.7。让是一个图和转移相关的相关图是一个复杂的结构比最短路径的计算时间。
2.4。转移图方法
一旦转移图和相关的图正式定义,我们现在的分解SPP在这些抽象图形转移的方法。
每次请求履行获得从一个源的最短路径和目的地在起飞时间,我们需要计算最佳路径有关,,对所有,尽管。然而,对所有计算一次,因为它并不取决于什么和。利用这一特性可以分解SPP转移图如下。
(1)最好的路径,尽管,尽管计算和存储。这就是所谓的precalculations。(2)当一个请求完成两个特定的节点和和时间,然后,,对所有可以计算。(3)最后,相关的图 构造和计算最短路径。这个分解降低时间复杂度的问题很大,因为precalculations计算最困难的路径计算时间。Precalculations提供一个重要的优势如果实现多个和频繁的请求(例如,在实际的web服务)。相反,precalculation当检测到一个扰动部分必须重新计算。表2显示了一个示例的重新计算相关的图对图1如果节点之间的弧的成本和为组件从两个增加到四个。可以看出,只有几个路径需要重新计算,而不是考虑所有的交通网络。这是特别有效的转移图与多个组件。
最后,我们目前的转移图方法的算法1。这个过程计算计算最短路径为一个特定的组件和起飞时间。这个步骤为每个组件可以独立计算,由于的特点转移图并在这种抽象SPP的分解。这个过程StoreDataBase保存的数据基础前面的计算最短路径的设置。这个过程计算被称为三次计算所有最短路径的具体设置当用户提交请求。RelevantGraph过程减少初始图更紧凑的结构对应于一个给定的用户请求。最后,程序ShortestPath给出了最小的路由请求的用户。显然所有这些程序可以以不同的方式实现,给不同的复杂性。在这里,我们显示我们的方法的可行性通过Dijsktra算法的一个变体。因此,转移图方法可以应用于场景与分布式传输信息来源。
|
||||||||||||||||||||||||||||||||||||
3所示。仿真结果
到目前为止,我们已经介绍了转移图抽象和转移图的方法。在本节中,我们提出一个计算测试这种方法的几个实例的SPP时间多通道网络。
我们选择十八SPP的实例有三,四,五运输方式和越来越多的节点从50到2000年,命名。一个转移图构建的每个实例变量的弧和传输量,但保持大量的转移和10个可能的随机旅行时间每个弧,以模拟真实的场景。表3对于每个问题实例的描述转移图,的特点相关的图建造的转移图和计算时间。实例分组的节点数量。
迪杰斯特拉算法的变体(13)是用于实现函数转移图的方法(算法1),计算最短路径旅行时间。我们认为在这些模拟测试对所有,尽管都是可用的,即precalculations已经计算。的计算时间precalculation提出了表3。
的转移图方法是测试电脑配备一个英特尔Core2双核T7300 2 GHz, 2 GB RAM。100测试已经完成与随机节点和起飞时间为每个实例,计算的平均和最大CPU时间(见表3)。
在构建的相关的图从转移图,所有实例中的节点数量减少了约70%,尽管弧的数目大大增加(见表3)。自从迪杰斯特拉算法的复杂性取决于节点的数量,这是一个适当的算法来计算最短路径相关的图。
转移图方法已经在十八岁的实例测试问题,提供解决方案在第二个大约平均,即使对实例60.000和2000个节点旅行。Precalculation时间根据网络规模和数量的增加。然而,这precalculations必须一次完成,大大减少了计算时间的要求。
最后,我们的计算成本precalculation年代在中型网络与不同程度的复杂性,根据数量旅行。五转移图构建的实例与变量的数量旅行。图3显示的计算成本precalculation并不显著影响旅行的数量。
4所示。实验验证
在前面部分转移图方法被描述。在本节中,我们首先介绍Carlink平台(http://carlink.lcc.uma.es/)以及其服务和约束。然后,描述了转移图在Carlink验证平台,真实的场景。
Carlink无线交通服务平台旨在提供一个基础广泛的商业和政府交通、安全、和运输服务(参见图4)。平台是一种无线临时通信实体通过基站与骨干网连接。交流平台本身Carlink的关键元素,但创建的各种服务平台有一个重要的角色。三个最重要的服务是当地道路交通气象服务(RWS),交通管理服务(TMS),和多式联运服务(MTS)。
当地的遥控武器站来源于FMI(芬兰气象研究所)道路天气模型(14)和交通安全提供了自动增强操作通过收集从车辆安全相关信息,并提供统一数据,自动而不需要用户启动。经颅磁刺激提供了交通状态使用静态交通信息提供的当局和动态交通信息的Carlink浮动车的应用程序。这个应用程序是由几个汽车收集的车辆密度在不同的位置信息的道路网络和提供信息的交通状态。最后,MTS计算多通道线路根据旅行请求和一组由用户指定的约束。这种服务是建立在转移图方法已广泛部分中描述2。
遥控武器站的平台利用信息和经颅磁刺激,以及其他服务,以生成事故或事件警告交通和天气条件(见图4)。MTS使用这些信息来计算最佳路线避免糟糕的道路条件和偶然的地区减少旅行时间,甚至建议改变运输模式如果检测到阻塞道路(例如,公园的车在火车站附近,坐火车相反)。
4.1。实验环境
无线通信服务平台分为三个不同的部分:交通服务中央单位(TSCU),交通服务基站(tsb)和移动终端用户(并)和临时连接和骨干网络连接(不连续的)。整个平台可以被视为TSCU之间数据交换架构,并同时tsb充当双向数据收发器。描述它们之间的交流在一个特设的方式当遇到,也可以发送关键数据直接TSCU毛评点)通过使用一个低容量的通信方法。服务的核心是外部系统连接到TSCU。
TSCU达到和过程最新的交通信息服务平台核心。TSCU更新定期tsb最近的交通平台信息相关的区域,通过固定网络。tsb传播交通信息平台每并通过接近它通过使用无线临时连接。最后,当遇到(参见图描述传播这些信息5)。
并和tsb配有采集系统收集的信息(速度、gps数据安全气囊爆炸,路温度,等等)定期向TSCU和传输。这TSCU处理的数据,如果检测到一个关键事件在一个区域(如事故,糟糕的道路条件),一条警告消息交付实时直接描述已知警告地区通过GPRS或类似的通信方法。
此体系结构的优点是,用户(并)和传播系统(tsb)定期发送信息TSCU路的条件。这是特别重要的,当事故发生时,由于TSCU实时通知,可以提醒司机在事故的周围地区。此外,因为汽车交流彼此相遇时,所需的tsb数量在公路可以大大减少,同时系统成本。
4.2。实验结果在现实场景
开发系统的验证在实际执行情况(见图6)。Arlon路线起源是比利时城市,目的地是卢森堡市(卢森堡)。数千的上班族每天做这次旅行乘汽车,火车,公共汽车,或者这些运输方式的组合。
一个转移图抽象这个场景是部署在Carlink平台和MTS。可用转移图有73个节点,49个传送点,和226年弧和包含三个组件,相关的培训,汽车,公共汽车。我们认为改变两个运输方式之间是通过步行,这反映在转移成本。
转移图方法实现的MTS Carlink平台。用户通过客户端应用程序请求被发送到MTS为移动设备。在这个应用程序中,用户可以选择旅游偏好(如运输方式、起飞时间、来源、和目的地),MTS发送请求,并得到最优路径从Carlink平台(图7)。
在我们的场景中,所选择的偏好是优化旅行时间从Arlon卢森堡使用任何类型的传输模式,在几点离开。第一个路线推荐的MTS在于直接乘汽车使用高速公路(表4)。当我们驾车出行,经颅磁刺激与扰动报道在6点在当前的行程。因为这个扰动修改道路的交通数据传输,precalculations重新计算组件公交车和汽车,但铁路。这个扰动增加了路线的旅行时间1到80分钟。MTS自动重新计算第二个路线考虑摄动和当前GPS位置的旅行者。这些信息反映给用户通过客户端应用程序。第二路线预计25分钟前到达第一个路线和行程步骤如下:公园在Kleinbettingen未来火车站附近,下一班火车去卢森堡,最后公共汽车到最终目的地,如表示4。
5。相关工作
时间依赖性约束下的多式联运问题不是经常在文学研究。据我们所知有两个工作与时间相关的多式联运问题,现在他们的方法在不同的情况下的性能问题(2,5]。
作者在5)抽象的问题无多通道图并提出若干数据结构和表,之前预先计算的,为了优化计算。问题是简化以及空间通过考虑到两个节点之间的最优路径搜索在任何起飞时间几乎总是拓扑相同。然而,这个约束不能被视为在现实的多通道网络,因为网络的扰动修改条件在不同的时间。Bielli et al。2考虑多式联运城镇之间的问题。问题是地理上划分和抽象层次图:城镇由子图,相互联系的直接链接。之前预先计算的子图内的最短路径,减少了搜索空间。这项工作的主要目的是提出问题的抽象,可部分并行。该方法测试网络由许多小型子图。
表5这些作品和转移图提出了一种比较方法在同一问题的实例。因为在实验中使用不同的机器(Pentium II, III UltraSPARC和T7300),计算时间已经被两个基准(归一化15,16]。根据这些标准,T7300和UltraSPARC三世比奔腾II 13.3和1.32倍,分别。这些比率应用于计算时间和包括在表中5。这些修正后,我们的研究结果仍然越来越有利,即使他们在老奔腾II。总体结果显示转移图方法性能更好的规范化计算时间。的可能的原因是由于性能precalculations,SPP的分解转移图简化了问题。
6。结论和未来的工作
本研究的主要贡献是多式联运问题处理的方法真正的分布式特性传输信息提供者。
的转移图可以抽象的场景与分布式传输信息的来源,因为它分开,把所有运输方式在不同的单峰网络。除此之外,每个单峰网络可以很容易地检测到意想不到的扰动时更新。这一特点非常重要,因为遥控武器站和经颅磁刺激提供实时天气和交通状况的信息,如果检测到一个事件或延迟,只有那些单峰网络相关预警区域必须重新计算,而不是整个网络。
SPP的分解转移图提供一个适当的解决方案系统接收多个和频繁的请求。尽管如此,precalculations有限的可伸缩性转移图抽象的空间记忆。
的转移图SPP的方法测试了几个实例,计算平均的解决方案,在不到一秒的时间。这种方法提供了更好的性能在计算时间方面比其他相关工作。
转移图方法已经开发成一个Carlink多式联运服务平台和验证在现实条件下使用几种运输方式。此服务将部署,积极将提供几千日常旅客在卢森堡的一个重要的解决方案。
我们的未来的工作是利用固有的并行和分布式结构的展出转移图。为此,相关的路径将被计算在每个组件中使用多目标进化算法分别和同时也将尝试和测试在大型实际多通道网络横跨许多国家,涉及几个运输服务提供商。
确认
这部分工作是由几个机构:欧盟尤里卡集群项目凯尔特标签、卢森堡政府和西班牙的安达卢西亚地区政府合同p07 - tic - 03044 (DIRICOM)。作者要感谢所有伙伴Carlink项目。