基于Web的波兰铁路和航空交通信息系统的转变与经验总结

电子笔记理论计算机科学50号1（2001）。ATMOS 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html11页基于Web的铁路与航空公司克日什托夫·戈奇莱1波兰格但斯克格但斯克技术大学应用信息学系摘要本文介绍了波兰铁路和航空运输系统的交通信息系统KRJ给出了该系统的基本算法基础该系统以前被设计为独立程序。最近，它已被转移到互联网上，并作为一项名为Ekspres的服务在一个商业网站上提供。介绍了向Internet服务迁移的过程和遇到的本文最后总结了一年来在业务工作量下进行开发所取得的经验1引言本文介绍了为波兰铁路公司（PKP）和波兰航空公司（LOT）开发的时刻表信息系统该系统在波兰称为KRJ。该系统以前（即在1992年）打算只在DOS和Windows操作环境中的O-line模式2000年，一项联合努力将该系统移至互联网。实现这一想法需要一系列复杂的编程和组织任务。在本文中，我们描述了这种实现和结果{一个名为Ekspres的在线系统，该系统已在一个名为“Wirtualna Polska”（英语：“VirtualPoland”）的最大的波兰网站上运行[1]。为了使介绍更清楚，在第2节中，我们介绍了KRJ的主要算法基础。KRJ的o-line版本的理论和一些实现问题已经提出（见[3]，[4]，[5]，[6]，[7]，[8]）;在这里，我们专注于集成问题，使系统能够包括不同的交通工具，其特点，在一个搜索引擎。在第3节中，我们提出了必须执行的实现任务，以便将系统从o-线环境移动到在线环境，1电子邮件：kris@pg.gda.plc 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。ATMOS 2001 { K. 戈奇莱2该系统的Web版本的最终架构第4节讨论了与这类信息系统相关的一些用户界面问题。部分5最后总结了迄今为止在商业网站上开发该系统所获得的经验。2一个交通网络在KRJ搜索引擎中应用的模型中，我们认为每种交通工具属于两类之一。第一类是有固定时间表的交通工具（如火车、飞机或公共汽车）。第二类是由没有这样一个时间表的手段（即你可以开始你的旅行几乎在任何时候）。私家车、自行车或脚踏车都是这种交通工具的例子你也可以把一些周期性的交通工具包括在这个类别中，这些交通工具循环频率很高，比如高峰时间的地铁让我们注意到，步行的短途步行通常是旅行中非常重要的组成部分它们要么是“隐性的”（当你必须在火车站换站台时），要么是“显性的”，当你必须在火车站换站台后换一种交通工具到达一个离车站很近的公共汽车站时。乘火车旅行很愉快。我们将交通网络建模为一个加权有向多重图。这种方法背后的思想是应用图论中已知的最短路径算法。在我们的模型中，有两种类型的弧，根据两类运输工具。离散的弧线对应于具有时刻表的交通工具所覆盖的通道。自由弧段对应于没有固定时刻表的交通工具所覆盖的通道以及交通工具的变化（例如，换乘火车或从火车换乘公共汽车）。让我们更精确地说定义2.1离散弧是有向多重图的弧，对于该有向多重图，给定极限时间TD。对于给定的开始时间t，离散弧wij的权重被定义为：（一）wij=8w，如果tT D1，如果t > T D：其中w是一个常数实值，w 2 R+。定义2.2自由弧是有向多重图的弧，它没有给定任何极限时间。自由弧的权是t的连续函数，t是离开弧的起始节点的时间。功能取决于运输工具。定义2.3乘车是指一辆车根据其时刻表（如有）行驶的一段行程图1描绘了图模型的一个片段，其中Xi为具有时间表的交通工具建模车站，Xm为具有时间表的交通工具建模车站。ATMOS 2001 { K. 戈奇莱3i;1i;mi;1;1i;n;mi;ji;1;jvd1，1，2XLXJva v1，1，1Dl和1Xivdj，3，1vaj，5va一，1va我2vdi，1，1vdvdi，4，2i，1，2vdi，4，1vdi，5，1vdvi，3，2DXKX MvD一、二、二i，5，2 vi，2，1Dvdi，3，1vak，2vavdk，1m，1，2vdm，1，1vak，3，1vak，3，2没有时间表的交通工具。假设在这两个站之间步行是必要的。xi内的弧：直接连接;权重= 0有变化的连接;权重=pxi和其他站之间的弧一个离散的弧;它的重量取决于出发和到达时间和运输工具一个自由弧;它的重量取决于通过的持续时间和运输Fig. 1.一个交通网络模型V是具有以下属性的节点的集合对于单个乘车中的每个到达，创建图形的单独节点，并且对于单个乘车中的每个出发，创建图形的一组节点。graph. 换句话说，每个站点X i由节点v a建模，ai;2;：; va对应于车辆的到达，并且通过节点vdD一、二、一;：：：; vdM对应于车辆的离开（我们使用以下符号：如果到达节点是v a ，则该到达节点是vdDi;2;j等）。对于没有时间表的车辆所覆盖的游乐设施，有两组节点：到达和离开。;v;v;vATMOS 2001 { K. 戈奇莱4;vi;5;1;v;vm;1;1;vDD一一该模型是一个多重图G（V; E;W）。E是具有以下属性的弧的集合：在单个车站内，从代表单个乘车的到达的节点到代表同一乘车的任何出发的每个节点有一个自由弧。该弧线对应于在车站处的变化或通过车站而没有变化。对于每个乘坐，存在从出发节点指向公共到达节点（即，具有相同的结束节点）。对于站点之间的漫游，有自由弧。单弧可以取代这种类型的弧簇。 在图1中，这些弧是：（vdm;1;1）D一、五、二m;1;2）。对于没有时间表的车辆覆盖的游乐设施，有免费的弧线（再次，单个弧可以代替簇）。在图1中，这些弧是：（vdk;3;1）Dm;1;2k;3;2）。W是取决于时间的权重函数，并且具有以下特性：对应于一个行程的离散弧的权重由到达结束节点的时间确定（或者，如果我们正在使用最晚的出发时间而不是最早的到达时间，则由从开始节点出发的时间确定）。权重还可以包括一些其他的非时间特性。与单个车辆所通过的通道相对应的自由弧的权重等于零。对应于车辆变化的自由弧的权重等于p，它被称为相当于一次变化的时间本文将无固定时刻表的车辆通过的自由弧的重量指定为一个函数，它取决于出发时间和运输工具的类型。该功能在弧之间可能不同。为了找到一个最佳的连接，有必要考虑到许多不同的变量到达所有的中间节点的连接。而使用例如基于Dijkstra算法或其众多变体之一的算法（[2]，[10]）从源到目的地发送连接，在每个节点中评估两个值：进入节点的当前时间和连接的当前权重。由于上述模型，路径的权重在访问的节点中进行了适当的比较。 还可以将以下因素包括到路径的权重中：到达时间、变化次数和离开时间（尽可能晚）。在从给定的源节点向给定的目的节点发送连接的过程中，该算法同时从所有节点（v）（v）ATMOS 2001 { K. 戈奇莱5;vp;m;1k;1k;m;vDp;1;Dp;2;1;：：：;vd该模型从源节点出发，通过到达对到达目的地节点进行建模的任何节点（即，节点vaak;2;：; va）. 然而，在处理上有显著的不同，有时间表的和没有时间表的。对于一个固定时间表的单次骑行，只有一个公共的结束节点。我们可以证明，结束连接的算法只能存储一次这样的旅程。因为对于这样的乘车，有一个固定的出发时间和一个固定的到达时间，所以这些时间可以直接用于评估当前时间和连接的权重。没有固定时刻表的交通工具所经过的每一段路程，都有一条弧，弧的起点和终点是分开的。 这是由于到达结束节点的时间是不同的。如果在到达节点X k之后，旅行将使用具有固定时间表的交通工具进一步延长，则延长旅行的可能性和获得的权重将取决于到达节点X k的时间。在这样一个加权有向图中找到最小代价路径的算法的正确选择取决于图密度（每个节点的平均弧数，例如参见[10]，第二章中的讨论）。3）。在研究了铁路网络的图形属性并进行了测试之后，我们决定采用Moore-Bellman-d 'Escopo-Pape算法的变体[10]。我们对该算法进行了改进，通过适当的数据预处理提高了算法的效率.实际上，由于数据的静态性质，可以在线完成许多必要的工作，使得可以在算法运行之前将数据转换为最合适的形式在确定路由时，我们没有采用启发式方法。在这种情况下，我们以类似于[9]中描述的方式进行。KRJ引擎总是试图找到最佳连接，即与最早到达时间（给定出发时间）的连接，或者，通过对称，与最晚出发时间（给定到达时间）的连接。最优性准则考虑了与一个更改（如上所述的p参数）相关联的权重或成本然而，我们不同于[9]中的工作，在如何创建图形的在线和区分自由弧和离散弧。结果表明，该模型在KRJ搜索引擎中的应用具有一定的通用性，可以适用于不同的、异构的交通网络，如公交网络、公交网络、公交网络等。道路交通c。在大多数情况下，我们可以假设自由弧的权重是固定的，它由通过对应于该弧的距离所需的时间决定。在更复杂的情况下，可能会发生这个时间（和权重）将取决于一天中的时间，因此它将是开始时间的函数。显然，这对于在道路上行驶是正确的（例如，汽车）。汽车交通网络的建模涉及到道路的地形和道路的实际状况等多个方面这些条件，以及由此产生的旅行时间，可能在很大程度上取决于一天中的时间、一周中的日子和季节（回想一下节假日高速公路上的拥堵尽管如此，整个道路网可以由自由弧建模，除了一些特殊的vATMOS 2001 { K. 戈奇莱6网络部分，如渡轮通道、吊桥或边境口岸，可能只在某些时候才能运作。后者应采用离散弧线的模式。3Ekspres的建筑将KRJ的O-线版本迁移到Internet环境需要执行多个分析、设计和实现任务。下面我们列出了Ekspres开发人员团队执行的主要任务设计系统的架构，考虑到性能问题，这是非常重要的Web服务的类型。定义Web服务器和KRJ之间的接口。对KRJ搜索引擎进行必要的更改（将交互模式更改为批处理模式，更改磁盘支持，重新编译为Linux环境的共享库等）。开 发一个站名搜索引擎（KRJ的O -line版本不需要这样的引擎，因为站名是交互式指定的精确字符串）。在繁重的工作量下进行配置的微调。图二. Ekspres的总体架构Ekspres的最终架构如图2所示。位于服务器上的系统由四个主要组件组成：Web服务器，WAP服务器、PHP解释器和用于Web的KRJ。该系统由其客户通过标准Web浏览器（或通过WAP浏览器，如果客户是移动电话）访问。用户以标准的方式将某些信息输入到显示在Web页面上的在线表单中（见第5节），ATMOS 2001 { K. 戈奇莱7查询系统。用户查询通过Web服务器和PHP解释器传输到KRJ，以便Web模块做出适当的响应一个用户交互可能需要在客户端制定并在Ekspres服务器上处理多个查询，因为用户可能无法一次制定精确的查询，或者可能对不同细节级别的不同连接感兴趣Web模块的KRJ由几个组件组成（参见图3）。主要组件是搜索引擎（在第2节中描述），它负责根据接口模块建立的参数发送连接。接口模块还负责为PHP解释器生成输出数据，作为PHP变量集或XML数据集。接口模块与负责解析作为用户查询参数给出的站点名称的站点模块合作。站点模块有独立于搜索引擎数据库的站点数据库。图三. KRJ for the Web的主要组成部分下面给出了PHP解释器和KRJ for Web之间通信的主要步骤整个通信都在PHP解释器创建的单个Linux进程中执行(i) PHP解释器使用用户在Ekspres主输入页面上指定的参数（通过客户端的浏览器和服务器上的Web服务器传输到PHP解释器）创建和调用KRJ进程。(ii) 接口模块将站的名称作为字符串传递给站模块，并向站模块询问站的标识符(iii) 在完全匹配的情况下，对于每个站名称，Stations Module返回适当的站标识符。在不匹配的情况下，Station Module返回一个听起来像”给定字符串“的车站名称的标识符列表。然后将此列表转换为字符串列表ATMOS 2001 { K. 戈奇莱8并返回到PHP以呈现给用户，以便重新选择。(iv) 从站点模块获得的两个站点标识符和其他参数被传递到搜索引擎。(v) 搜索引擎结束连接并将结果返回给接口模块。结果是在所需的详细程度上产生的。Interface Module将结果格式化为一组字符串（PHP变量或XML文本），并将它们传递给调用者（调用KRJ进程的PHP解释器）。(vi) KRJ进程终止。4用户界面下面是该系统的静态和动态Web页面的示例。第一个静态页面（参见图4）是输入页面，用户在其中制定查询。见图4。Ekspres的主输入页面用户需要输入的数据包括：出 发站和到达站（在页面顶部的两个文本ELD;用户可以从站列表中选择或者可以输入任何近似站名的字符串），要求的出发或到达日期和时间（ATMOS 2001 { K. 戈奇莱9站名ELD），是否允许更改（日期和时间下方的复选框），用于计算旅行成本的tari类型（接下来的两个单选按钮和一个复选框），他希望有多少时间（至少）来改变（下一个文本eld），要找到的连接数（下一个文本eld），使用的列车种类以及是否允许使用轻型列车（页面底部的一系列复选框）。用户查询的结果以清晰的方式呈现在不同细节级别的动态Web在第一个详细级别上显示用户查询的参数，对于找到的每个连接起飞时间抵达时间旅行总时间和总长度用于更改的铁路票价连接中使用的运输工具。每个文本行都伴随一个复选框，其中包含有关连接的数据。如果选中了给定连接的复选框，则有关此连接的数据将显示在显示第二详细信息级别的页面上。图5给出了这样一个页面的示例。本页显示查询如何从Sochaczew（波兰首都华沙附近的波兰小镇）到苏黎世的详细结果2001年3月17日上午，利用一切可能的交通工具，抵达中央银行。图五. Ekspres的详细输出页面示例ATMOS 2001 { K. 戈奇莱10页面上显示的数据指示用户：(i) 首先，他应该在7：27乘坐火车前往华沙中央火车站（火车的详细信息在行程表的脚注中给出，由适当的上标标识;火车的设备在表中以图标的形式可视化）。(ii) 然后，他应该采取城市交通到华沙Okecie机场（距离：10公里;约。持续时间：50分钟，从8：20到9：10）。(iii) 旅行的下一个部分是在机场办理登机手续（大约10分钟）。持续时间：1小时，从9：35到10：35）。(iv) 上午10点35分，ri chFlughafenKloten开始（同样，细节在脚注中）。(v) 八点半结束(vi) 下一部分是在机场办理退房手续（护照检查，领取行李等），用约持续时间40分钟，从12：35到13：15。(vii) 最后，用户应该乘坐城市交通工具到达目的地（距离：12公里;约。持续时间：1小时）。此外，Ekspres还生成一些其他静态和动态页面。其中包括：在初始不匹配的情况下用于振铃站名称的页面，一个关于电台的描述性信息的页面，带有图标和其他图形元素解释的页面，帮助页面5结论在撰写本文时，Ekspres已经在工作环境中运行了9个月。它被证明是一个非常高效和可靠的系统。它的可用性几乎是100%高，响应时间，在繁重的工作量，是令人满意的用户。这证明了搜索引擎和系统架构的设计是正确的。该系统根据时间表的变化定期更新，最后一次更新的日期明确显示在Ekspres的主页上。预计该系统将进一步扩展，以涵盖在线版本中仍然缺少的在线KRJ（例如，旅行地图，按需提供不同的详细程度确认将KRJ转移到互联网的项目涉及来自大学和工业界的一些专业人士。主要贡献者（除作者外）是：令人遗憾的Janusz Cielatkowski（格但斯克技术大学），ATMOS 2001 { K. 戈奇莱11Michal Wilde（\MiWil）和Jacek Kujawa及其团队（\Wirtualna Pol-ska”SA）。引用[1] http://ekspres.wp.pl{Ekspres网站的URL。[2] Deo ， N. ， 和 C. Y. Pang ， Shortest-path algorithms ： taxonomy andannotation，Networks14（1984），275{323.[3] Goczyla，K.，和J.Cielatkowski，Finding Optimal Route in a Railway Network，ProceedingsofInternationalConference\OperationsResearch1994，”Program Abstracts，Berlin，Aug.30{Sept. 2，1994，115.[4] Goczyla，K.，和J.Cielatkowski，波兰铁路网行程规划程序，国际会议论文集\运营研究1994，”程序摘要，柏林，8月。30日2（1994），269.[5] Goczyla，K.，和J. Cielatkowski，Journey Planning in a Public TransportationNetwork ， Proceedings of 17th International Conference on InformationTechnologies Interfaces ITI'95，Pula（Croatia），June 13-16，1995，425-430。[6] Goczyla ， K. ， 和 J. Cielatkowski ， Optimal Routing in a TransportationNetwork， European Journal of Operational Research87 No.2（ 1995） ，214-222.[7] Goczyla，K.，和J. Cielatkowski，Integrating Dierent Means of Transport intoan On-Line Journey Planning System ， Proceedings of 18th InternationalConferenceonInformationTechnologiesInterfacesITI'96 ， Pula（Croatia），June18-21，1996， 365-370.[8] Goczyla ， K. ， 和 J. Cielatkowski ， AnObject-OrientedModelof aHeterogeneousTransportationNetworkforJourneyPlanningSystems ，Proceedingsof8thIFAC/IFIP/IFORSSymposiumonTransportationSystems，Chania（Greece），June 16-18，1997，265-269。[9] Schulz，F.，D. Wagner和K. Weihe，Dijkstra的在线算法：公共铁路运输的经验案例研究，第三届算法工程研讨会论文集，计算机科学讲义1668（1999），110-123.[10] Sylvia，M. M.，N. Deo和J.S.王志荣，离散最佳化演算法，硕士论文，国立成功大学，1993。