基于大数据集的客户信息系统交通连接研究——列车时刻表放入主存储器

8《理论计算机科学电子札记》66卷第6期（2002）网址：http://www.elsevier.nl/locate/entcs/volume66.html10页将列车时刻表放入主存储器1马蒂亚斯·穆ller（Hannemann和MathiasS.德国波恩大学离散数学研究所2，53113 Bonn，Germany卡斯滕·渭河3号达姆施塔特工业大学，Wilhelminenstr.7，64283达姆施塔特，德国摘要组织数据以广泛避免对后台设备的访问是具有大数据集的应用程序中的主要挑战之一。我们从一个正在进行的项目中提出了有用的经验，在该项目中，我们开发了一个质量保证工具的算法内核，以反检查客户信息系统的准确性，以实现交通连接。1引言我们考虑的问题，设计客户信息系统的交通连接。这意味着售票员、售票机等使用的系统类型。欧洲一家国家铁路公司运营的系统客户信息系统查询引擎设计中的一个关键问题是这些数据的管理。首先，这意味着对后台设备的昂贵访问应该保持在最低限度，而不会牺牲查询算法的效率现代计算机技术提供了在主存储器中方便地存储数百兆字节的机会。然而，根据我们的经验，1 这项研究是与德国法兰克福/美因河畔的DB系统公司合作完成的2 电子邮件：muellerh@or.uni-bonn.de，schnee@or.uni-bonn.de前两名作者得到了德国研究共同体（DFG）的部分资助，资助额为WE 1943/3{1。3 电子邮件：weihe@algo.info rm ati k. tu-d a rm sta dt. dec2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。微米的ller{Hannemann，Schnee，andWeihe9德国或欧洲的列车时刻表仍然是一个挑战。将所有这些数据都放入主存储器并不真正有效，因为加速技术通常需要大量的辅助数据。例如，诸如分层的算法技术可能需要大量的附加数据，其中短路线被压缩为点到点连接（参见附录以获得分层的更详细解释可用的存储空间越多，像这样的加速技术就越有效因此，改进的存储组织也将是未来的迫切需要。在本文中，我们将介绍和讨论一些技术，我们已经应用在我们的一个正在进行的项目。我们相信，像这样的“技术”知识对其他研究和开发小组有潜在的帮助，因此值得交流。在第2节中，我们将更详细地描述算法问题和试验性应用环境（不完全详细，因为这将超出本文的篇幅限制和范围）。然后在第3节中，我们将简要回顾和讨论我们的基本数据模型。最后，第4节专门讨论详细的技术问题。2问题描述和场景问题描述：区分输入的两个部分是合理的，全局数据和客户查询。 基本上，全局数据包括时刻表和辅助信息，例如车站列表和单个列车的附加数据。例如，每个列车与全局数据中的特定列车类别（高速列车，诸如德国ICE和法国TGV; IC和EC; Interregios等;本地列车）相关联。算法内核（“查询引擎”）根据全局数据和客户查询提供可行连接列表。客户查询由出发站、到达站和最早出发时间或最晚到达时间组成。这样的查询还可以包括一些关于个人需求、首选路线或列车等级的可选信息：个 人需求：例如，人们希望随身携带自行车，因此需要连接，以便所有使用的火车都允许自行车运输。对于这种情况，列车与全局数据中的所谓属性例如，“bike transport possible”是一个属性。优 选路线：这意味着所谓的通孔。客户可以指定必须满足的站的序列（以指定的顺序）。客户通常出于两个原因使用过孔：（i）客户想要中途停留以访问城镇;（ii）客户对系统的输出不满意并且使用过孔来操纵系统。排 除的列车等级：可将列车等级限制为所有列车等级的子集。例如，通过排除高速列车，人们可能会发现更便宜的连接。微米的ller{Hannemann，Schnee，andWeihe10基本上，有三个优化标准：旅行时间，机票成本和便利性。首先，方便意味着换乘的次数和延误时间。根据车站的大小和两个相关站台之间的距离，10{20}分钟可能是一个方便的延迟时间。 如果延迟时间与此目标显著不同，被认为是相当不方便的。全局数据中的可行延迟时间也有下限，这取决于列车换乘的具体情况（例如，是否需要更换平台）。据我们所知，算法和应用领域中的科学工作几乎专门涉及旅行时间或旅行距离，并且商业产品通常将旅行时间或地理距离视为（唯一的）第一类目标。这可能是由于几个原因。原因之一是，大多数工作都集中在当地的公共交通和汽车路线。在这些情况下，只有旅行时间或距离是相关的。另一个原因可能是算法的易处理性：如果在车站停留用弧线表示，则总旅行时间是所有弧线的旅行/延迟时间之和。这种弧代价的可加性是所有教科书上的最短路径算法的强制性先决条件。不幸的是，票务和火车换乘规则通常与这种理想情况相去甚远。此外，两个或多个目标的情况是不那么有效和优雅地处理。还有各种各样的并发症。这里我们只提到其中两个，因为它们将在第4节中重新出现：(i) 时间表在一定的时间段内有效，但时间表每天都有很大的变化。在全局数据中，每列火车都与其运行的日期的规格相关联（描述该火车的“运行日期”的位字段）。(ii) 很多时候，几个车站都在步行距离内，例如，火车站前面通常有一个公共汽车站。另一方面，在大城市中，车站通常由用于长途列车的站台和用于有轨电车或地铁的站台（通常在不同的地面上）组成。 把车站的这些不同部分看作是步行距离内的独立车站是有道理的。在全局数据中，每个这样的步行路径被分配估计的最小步行时间。这种连接与火车或公共汽车连接非常不同，因为它可以在任何时候使用，而火车和公共汽车都必须在固定的出发时间。事实上，步行路线更类似于汽车路线规划中的连接。显然，对这种混合模式的需要是一个严重的复杂问题。场景：本文的中心场景是一个客户机服务器系统。例如，客户端可以是售票机、售票处的终端或门户网站。在不久的将来，移动电话也可能成为一个中央可调用服务器服务器不是单机，而是集群微米的ller{Hannemann，Schnee，andWeihe11这些机器必须处理大量的客户查询。4由于每个单独的查询都必须“实时”回答，比如在不到三秒的时间内，与客户可能因长响应时间而烦恼的可能性相比，工作站或PC集群的成本可以忽略不计，因此这种情况非常现实。只有根据一个主服务器的简单模型运行查询引擎才有意义：主服务器接收查询并将每个查询委托给其中一个从服务器;从服务器计算总的响应并将其发送回主服务器。53基本数据模型基本上，我们采用[4]中使用的数据模型，该模型也用于[1]和[5]作为起点。Brodal和Jacob称这种方法为时空模型[2]。主要的数据结构是一个有向图。 该图的节点是所有列车的出发和到达事件。我们所说的“火车”是指一列具体的火车时刻表。例如，如果一列火车在铁路连接上每小时有规律地运行，那么这列火车的每一次出现都是我们意义上的“一列火车”。直达列车连接则是列车从一个站移动到下一个站。在直接连接期间，列车可能会经过许多中间站，但不会在任何一个中间站停靠。对于每个直达列车连接，存在从出发事件到到达事件的弧。此外，对于在一个台站的两个连续事件，存在从较早事件到较晚事件的弧（"停留弧”）。如果两个事件出现在同一时间和同一车站，则它们被任意排序（由于列车换乘的最小延迟时间被假设为严格正的，因此时间的顺序（相同的事件不会产生差异））。因此，列车连接以一对一的方式对应于该图中的路径。因此，乘坐火车是一条完全由直达列车连接组成的路径，而在车站换车是一条完全由停留弧组成的路径由于时间表的有效期通常很长（我们在本文件中提到的2001/2002年现有时间表的数据集有效期略多于一年，即371天），因此显然不允许使用全时扩展。相反，在我们的模型中，时间是以一天为模的（这是时间表高度重复的自然间隔）：出站/进站列车弧对应于列车的事件，这些列车在除了行车日之外的所有方面都是相同的，由单个节点表示，我们只保留一个节点。4 在高峰时段，德国铁路公司的中央服务器必须回答高达30万个查询每小时5 在Del项目（www.del.de）中，查询被分解为子查询，每个子查询被委托给另一台计算机。然而，这与我们的情况并不相反。首先，Del项目的基本原理是，来自各个运输公司的数据的整合是一个永无止境的问题。因此，每个公司都应该计算使用公司火车或公共汽车的连接部分。每个公司可以使用上述主从模型来处理其子查询。微米的ller{Hannemann，Schnee，andWeihe12车次行车天数位字段列车属性IR4711...00000100000010...FB、FR、BT18点站A站C16点17点IC 501...11111111111111...BR十六16点B站RE0815...11111001111100...FB边缘信息：Fig. 1.我们的训练图模型的示意图。注意，在该示例中，列车IC 501每天运行（其行车日的所有位被设置为1），其在16：00离开车站A并且在16：15在车站B具有其下一站，该列车仅具有一个属性BR（BR表示“请预订”）;列车RE 0815仅在工作日运行，而列车IR 4711仅在星期六运行。每个节点都有一个train arc，但是每个节点都配备了一个指定有效traindays的bit eld。更确切地说，由于只有几千个不同的位eld，但有数百万个弧，我们只存储一个指向相应位eld的指针。为了从一个交通日继续到下一个交通日，我们在图表中插入每个车站的停留弧，将午夜前的最后一个事件连接到第二天的第一个事件。因此，在这个图中，每个站都被表示为通过其所有事件的循环。见图1.一、讨论：基本上，我们的基本数据模型只有一个可行的替代方案。 这种替代模型在[2]中被称为时间依赖网络模型。该模型适用于一个简单的场景：唯一的目标是找到最快的列车连接，没有列车换乘规则，没有必需或排除的属性，也没有列车类别要区分。我们将在下文中采用[2]在时变网络模型中，每个站点只有一个节点。另一方面，从s1站开始有一条弧线 前往s2站 如果（s1;s2）是至少一列火车的直接连接。给弧a分配一个延迟函数fa，使弧a得到一个时间值作为唯一的参数，并返回微米的ller{Hannemann，Schnee，andWeihe1311另一个时间价值。更具体地说，考虑从s1到s2的直达列车连接，并设t1为s1的出发时间，t2为s2的到达时间。设t为

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