时间依赖方法在时间表信息系统中的应用

理论计算机科学电子札记92（2004）85-103www.elsevier.com/locate/entcs通过时间依赖方法实现时间表信息的真实建模*Evangelia Pyrgaa，1，Frank Schulzb，2，DorotheaWagnerb，3，Christiane Zaroliagisa，4a计算机技术研究所，邮政编码。Box 1122，26110 Patras，Greece，and Department ofComputer Engineering and Informatics，University of Patras，26500 Patras，Greece.b卡尔斯鲁厄大学计算机科学系，76128 Karlsruhe，Germany。摘要我们考虑最优行程问题的时间表信息系统支持大量的在线查询。我们展示了两个重要的扩展的时间依赖性的方法来模拟现实版本的最早到达和最小数量的转移问题，以及它们的组合，不能模拟的原始版本的时间依赖性的方法。我们还提供了加速实现的算法，并利用真实数据呈现了初步的实验结果。关键词：时刻表信息，时间依赖模型，最短路径，最早到达，最小换乘次数。*这项工作得到了欧盟IST方案的部分支持，合同号为：IST-1999-14186（ALCOM-FT），由欧盟人类潜力方案根据合同号HPRN-CT-1999-00104（AMORE）和DFG根据授权WA 654/1-12。1 pirga@ceid.upatras.gr2 fschulz@ira.uka.de3dwagner@ira.uka.de4 zaro@ceid.upatras.gr1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2003.12.02486E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-1031介绍对时刻表信息进行建模以有效地回答询问最佳路线的查询是公共交通中特别是铁路中相当重要的问题。建模的主要目标是尽可能快地处理大量的在线查询。在本文中，我们关注的是公共铁路运输中出现的特定的查询密集型场景，其中中央服务器可以通过火车站的终端或通过Web界面直接访问任何客户，并且必须回答潜在的无限数量的查询。这种应用程序的主要目标是减少查询的平均响应时间时间表信息通常在两种方法下进行研究：时间扩展方法[3，7，8，9]和时间依赖方法[1，4，5，6]。这两种方法的共同特点是通过将一些最短路径算法应用于适当构造的有向图来回答查询在前一种情况下，构造的有向图明确表示时间表的每个事件（出发或到达车站），因此导致生成非常大的图。在后一种情况下，生成的有向图的大小要小得多（通常与站点的数量成比例），因此预计会加快查询的计算速度因此，在本文中，我们专注于时间依赖的方法，特别是在[1]中最近提出的模型。时间依赖方法[1]构造了时间依赖有向图G=（V，E），其中每个节点表示一个站，如果相应的站通过基本连接（即，由中间不停靠的列车提供服务）。边缘上的成本被“即时”分配，即，边的成本取决于最短路径算法将使用特定边来回答查询的时间。换句话说，如果T是一个表示时间的集合，并且（v，w）是一个图的边，那么它的成本由f（v，w）（t）−t给出，其中t是在v的出发时间，f（v，w）：T→T是一个函数，使得f（v，w）（t）=tJ，tJ≥t是在w中最早可能的到达时间。G中的一条时间（v1，v k，t）-路-对应于我们希望找到的一条路线-是一个序列v 1，v 2，.，vk∈V和序列t1 = t，t2，.，tk∈T使得（vi，vi+1）∈E且ti+1 = f（vi，vi+1）（ti），1≤i k。两个基本的时刻表信息问题是最早到达问题（EAP）和最小换乘次数问题（MNTP）。给定两个站a和b，EAP被定义为找到一个定时（a，b，t）路径的问题，该路径受到b中的到达时间是最早可能的附加约束，而对于MNTP，我们搜索一个定时（a，b，t）路径，该路径受到我们从一个站E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-10387尽可能地去另一个地方。一定的兴趣也是上述问题的组合：在所有答案MNTP选择一个达到最早的到达时间。时间相关模型可以通过将最早到达问题简化为G上的最短路径计算来有效地解决最早到达问题，假设从一辆火车到另一辆火车的转移可以在零时间内执行[1]。然而，这显然不是一个现实的假设。此外，该模型无法解决最小传输次数问题，因为即使我们跟踪何时有传输，并为每条边使用避免传输的事件而不是最早的事件，它也不会为我们提供最佳解决方案。当我们别无选择，只能转会时，就没有办法在所有可能的事件中选择最好的事件在本文中，我们提出了两个扩展的时间相关的方法，可以有效地解决这两个现实版本的EAP（即，每个站具有非零传输时间的一个）和MNTP，以及上述它们的组合。第一个扩展考虑了平台信息的合并第二个扩展考虑了列车路线信息的合并，解决了EAP和MNTP的现实版本，并在不提供站台信息或要求MNTP解决方案的情况下构成了重要的在[1]中也简要讨论了用于合并站台或列车路线信息的类似方法，用于恒定的列车换乘时间的情况，但既没有提供完整的细节除了建模之外，我们还提供了加速实现的算法，并在真实世界的数据上给出了初步的实验结果本文的其余部分组织如下。 在第2节中，我们介绍讨论了具有零传输时间的EAP问题的求解方法。在第3节中，我们提出了我们的建模通过平台和列车路线信息的现实版本的EAP恒定或可变的非零转移时间。第4节给出了MNTP的建模和解决方案，第5节讨论了EAP和MNTP结合的解决方案第6节介绍了几种加速计算边缘成本的算法。在第7节中，我们介绍了我们的初步实验结果，我们在第8节中得出结论。88E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-1032时间依赖模型与零传输时间EAP求解如上所述，时间相关有向图[1]包含每个站一个节点，并且如果存在从A到B的元素连接，则存在从站A到站B的边e。的基本连接集，A到B由C（e）表示。 一个基本联络c∈ C（e）在一天内的出发和到达时间d（c）和a（c）是区间[0，1439]中的整数;时间表的粒度是1分钟，时间值是午夜后的分钟。给定两个时间值t和tJ，t≤tJ，周期差（t，tJ）是最小的非负整数l，使得l<$tJ−t（mod 1440）。基本联络c的长度，用length（c）表示是循环差（d（c），a（c））。设D为出发站，t0为最早出发时间.Dijkstra算法的一个改进The Diesel，w.r.t. Dijkstra边长（以及隐含的时间依赖函数f）计算如下。由于Dijkstra在时间相关模型中，δ（A）表示到达站点A的最早时间。换句话说，无论何时考虑边e=（A，B），我们确实知道在车站A的最早到达时间，并且因此在算法的该阶段，我们知道必须尽可能早地乘坐哪列火车经由A到达车站B：或等于A5处的最早到达时间。设t = δ（A），c∈C（e）是最小化{圈-环|c∈C（e）}。如果基本连接C（e）保持在一个有序数组中，则可以通过二分查找容易地找到特定的连接C e的边长le（t）则定义为le（t）=周期-偏差（tmod1440，d（c））+长度（c）。因此，fe（t）=t+le（t）。上述算法的正确性是基于f是非减的（t≤tJ<$f（t）≤f（tJ））和具有非负延迟（tt，f（t）≥t）。由于所调查的应用程序的性质，我们可以有把握地假设所有的函数都有非负的延迟。5.我们假设列车在边缘不允许超车，并且换车所需的时间可以忽略不计。E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-10389我3具有非零转移时间的最早到达问题在本节中，我们将描述时间相关模型的两个扩展，以解决EAP的现实版本，其中传输时间火车在车站是非零的。 在下文中，我们将用S表示一组节点，使得每个u∈ S对应于一个站，并且用站（u）表示，u∈ S，u代表的实际站点3.1基于站台信息的列车换乘建模为了打破时间依赖模型中的零转移时间假设，我们将时间依赖图扩展为平台变化的形式。我们将研究恒定和可变转移时间两种情况。前一种情况的类似想法是brie-briey在[1]中提到的。我们假设我们有一个时间表，以及到达/离开站台和到达/离开某个车站的每列火车的时间。我们将使用以下假设。假设3.1对于任何给定的车站，没有两列火车离开车站A（从同一站台）并到达车站B（在同一站台），使得第二个离开A的火车首先到达B。3.1.1图模型在下文中，我们将描述通过平台信息对具有非零传输时间的EAP进行建模的图G=（V，E）的构造。设S为代表站点的节点集合对于每个节点u∈ S表示具有Pu>0站台的站，我们构造一组节点Pu={p u，p u，.， p u }，其中p u，0 ≤i< P u，是表示0 1Pu−1iu的第i个p形式。G的节点集定义为V=SP在哪里P=u∈S Pu.边集E=ADG的DR由四种类型的边其定义如下。• A=A，其中A={（p u，u）}。u∈Su u0≤ i Pui• D=u∈S Du，其中Du=0≤i Pu {（u，p u）}。• D=u∈SDu，其中Du=，如果在每个站点，platforms是常数;否则，Du是节点之间的边的集合其以这样的方式表示站台，以便对站台（u）的站台如何连接进行建模。• R={（pu，pv）：至少有一个事件偏离puu，v∈S，0≤i Pu，0≤j P vi j i90E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-103pGGJ我我变化我BGG032A'B'IjpA f（pA，pB）p2002pBpAA 0B110A0BA B0的ggf（pA，pB）B00AfA00（p，pB）pAp A2 3pB0Fig. 1.每个车站的站台变化恒定的站台建模示例。并到达pv}。如果u，v∈ S，0≤i，iJ 0，如果有一些列车从车站（s0）开始其旅程并连续访问车站（s1），...，站（s k−1）依次如果有多列火车遵循相同的时刻表（相对于它们访问上述节点的顺序），那么我们说它们都属于同一条火车路线P。 请注意，它可以是station（si）站（sj），ij，sisj，0≤i，j≤k−1，例如当列车执行循环。对于u∈ S，设u是停靠在车站（u）的不同列车路线的集合，设Pu是对于每个经过车站（u）的P∈u恰好包含一个节点的集合（注意，如果P执行循环，则它贡献多于一个节点到Pu）。 另外，设Pu= |P = u ∈ SPu.|, and P =u∈S Pu. 然后，G的节点集V被定义为V=S P。 对于u∈ S，我们表示为pu，0≤i Pu，表示在u处停靠的第i条列车路线的节点。我边集E=AD DG的R由四种类型的边其定义如下。• A=A，其中A={（p u，u）}。u∈Su u0≤ i Pui• D=u∈S Du，其中Du=0≤i Pu {（u，p u）}。• D=u∈SDu，其中Du=，如果传输所需的时间相同对于所有停靠车站（u）的列车;以及D={（pu，pu）}，否则，请执行以下操作。u0≤i，j Pu，i ji j• R={（pu，pv）：站（u）和站（v）被访问u，v∈S，0≤i Pu，0≤j P vi j连续地通过相同的列车路线，并且pu、pv是相应的路线I j节点}。一条边e被称为一条圆形边或时间表边，如果e∈R，并且它被称为一条如果e∈A D D，则转移边。 列车路线的建模基于两个额外的假设。假设3.2设u，v是S中的任意两个节点，且pu∈Pu，pv∈Pv， I j（p u，p v）∈ R。如果d1，d2是从 p u 出发的时间，a1，a2是i j i分别到达时间为pv，则d1≤d2<$a1≤a2。这一假设指出，不可能有两列火车属于同一条列车路线，这样，第一列离开车站的火车是慢车，而后面的火车是快车，它在第一列之前到达下一个车站。当违反这一假设时，我们可以通过将属于同一列车路线的列车分为两个（或更多个）不同的列车来强制执行这一假设。E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-10393pA'pB'我JT1pA0F（p，一BpB0 （p）22pAGG一B0pB1010G一0一GBG0B一G0GpA（fp）B一B0一3（p三、0pA2pB0T2X我我X我A "我B "J'图三.每个车站换乘时间恒定的直达列车路线建模示例。列车运行时间与以前相同。这种分离可以通过将列车分成不同的速度等级来实现。假设3.3对于任意站节点u∈S和pu∈Pu，使得（x，pu）∈我我R，对于某个 x∈V，令 δui是两个连续从（x，pu）∈R到达pu，τ u是a所需的最大时间在车站（U）换乘。 因此，它必须保持δ ui≥ τ u。假设3.3的目的是确保在车站等候乘坐同一列车路线的下一班列车不会有好处。换句话说，假设3.2成立，从A站到B站乘坐第一列可能的火车不会导致错过从B站到B站的某个连接，如果我们跟随的是比我们所跟随的火车晚出发的某列火车（相同的火车路线），则可以使用该连接稍后将看到假设3.3 仅在考虑同一车站内的可变换乘时间的情况下才需要。在下文中，我们将假设u，v∈ S，0≤i，iJ 0，为实最短路投影依次访问的G中的节点。注意，ui和ui+1之间存在唯一边，0≤i k。设δ（u）和δ（u），其中u∈，分别为u在实际最短路径树和计算最短路径树中的代价。引理4.1对每个u∈ u，δ（u）= δ（u）。证据我们将通过首先证明δ（u）≤δ（u），然后δ（u）≥δ（u），δu∈来证明引理。考虑乘客可能遵循的路线。如果我们把这条路线分解成乘客曾经乘坐过的不同的火车路线，一条接一条，我们可以看到这些路线在G中形成了一条路径。(In为了从一条路线转到另一条路线，乘客必须先到某个车站换车。请注意，G将两条不同列车路线之间的所有变化都记录为一个边e∈D D包括在路径中。唯一不以这种方式包括的是发生在一列火车上的，某列火车从P开往另一列同样属于P的火车。然而，没有最短路径路由将包括这样的转移，因为继续使用同一列火车总是为我们提供较少的转移次数。（回想一下，由于两列火车都属于P，它们将以完全相同的顺序访问完全相同的节点/车站。这意味着所有的传输，一个真正的最短E. Pyrga等/ Electronic Notes in Theoretical Computer Science 92（2004）85-10397JJJJJJJJ路径将通过使用属于D D的边来建模，并且因此δ<$（u）≤δ<$（u），<$u∈<$。现在我们来证明δ（u）≥δ（u）。我们用归纳法来处理n的长度k。基k= 0成立，因为δ（s）=δ（s）= 0。假设它适用于所有小于k的值。设uk<$pv，对某个v∈ S，jPv. 关于uk−1有两种情况：或者uk−1<$pvJ，jJ

下载后可阅读完整内容，剩余1页未读，立即下载