电子笔记理论计算机科学50号1（2001）。ATMOS 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html11页在铁路网络中定位新站点？霍斯特·W Hamachera;1，Annegret Liebersb;2，AnitaSchobela;3，多萝西娅·瓦格纳b;4，弗兰克·瓦格纳c;5a德国凯泽尔登大学数学系和弗劳恩霍夫研究所ITWM，67653凯泽尔登b康斯坦茨大学，计算机与信息科学系，78457康斯坦茨，德国cDeutsche Bahn AG，Konzernentwicklung GSV，Potsdamer Platz2，10785 Berlin，Germany摘要在有了铁路网络，以及有关人口和他们使用铁路基建的数据后，我们正考虑在现有的铁路网络内增设新一个方面涉及铁路基础设施对人口的可达性，衡量的标准是人们居住的地方离最近的火车站有多远第二个方面，我们研究的是旅行时间的变化，为铁路客户所诱导的新的列车停靠站。基于这两个模型，我们引入了两个组合优化问题，并给出了它们的NP-困难我们提出了一种基于旅行时间的模型的算法方法，并提出了一个实际的应用程序，其第一个实验结果。1引言本文所研究问题的动机是以不太昂贵的方式增加现有铁路网络中火车旅行对当地交通的吸引力，例如体育和休闲活动或日常通勤上班。因此，假设我们有一个现有的铁路网络以及（潜在的）使用这个网络的人的信息。一个相对便宜的增加火车旅行吸引力的方法是开放？这项工作得到了欧洲联盟人类潜力方案的部分支助，合同号为HPRN-CT-1999-00104（AMORE）。1 @ mathe mat ik. 乌尼克湖de2 Angret. uni-konstanz.de，由DFG资助Wa 654/10-2支持3 schoebel@mathematik.uni-kl.de4 多萝西娅，我是瓦格纳. De5 Frank.H. bku.db.dec 2001年由Elsevier Science B出版。诉在CC BY-NC-ND许可下开放访问。2ATMOS 2001 { H. Hamacher等人沿着现有的铁路线新建火车站，其中新建火车站意味着是建造成本低的小站，并且通常仅由当地通勤列车服务。我们将考虑这种新火车站的两个方面。第一个是关于铁路网络的可达性：假设住在离火车站更近的地方会增加铁路网络的吸引力（并最终增加使用火车而不是其他交通工具的倾向），我们研究了定位（少数）新火车站的问题，以便（许多）人住在离火车站不远的地方。 这个可达性模型将在第2节中更精确地说明，相应的优化问题将被证明是NP完全的。我们将研究的新火车站的第二个影响涉及已经使用铁路网络的客户的旅行时间。一方面，乘客坐在一列现在停在新开放的火车站的火车上，会因为额外的车站而放慢速度。另一方面，居住在新开放的火车站附近的乘客比任何以前存在的火车站需要更少的时间到达最近的火车站。将这两个相反的效应中的每一个对所有铁路客户求和并减去总和，我们获得一组新的火车站对现有铁路客户的总旅行时间的效应的测量。第3节将详细说明这个旅行时间模型，并给出相应的优化问题的NP完全性结果。第4节将提出一种基于遗传算法的优化问题的算法方法，第5节将给出德国铁路公司第二章可访问性模型设P表示坐标点的集合，每个坐标点代表一个定居点，设L是铁路公司轨道上可行点的集合。我们假设轨迹集是分段线性的，即，它被给出为有限个线段的并集Si2 IR2，i = 1;：; L：L= fx 2IR2： x 2 Si对于某些 i= 1;：; Lg：该问题的解X由平面上的一组点给出，代表应该安装的止动件。X是可行的，如果X L，即，如果每个x 2 X满足x 2 L。为了评估一个可行解X，我们感兴趣的是X覆盖了多少个沉降。一个结算点p2P被一个点x2L覆盖，如果l2（p; x） 休息;其中l2是指欧几里得距离（或任何其他范数），r是某个3ATMOS 2001 { H. Hamacher等人给定半径。一个结算点p被一个集合XL覆盖，如果l2（p; x）r对于某个x 2 X：对于集合X，我们de necover（X）：= fp 2 P：l2（p; X） rg;其中，对于jXj，l 2（p; X）= min x2X l 2（x; p），l 2（p; x）= 1。 图1和2 说明了不同的火车站集合如何覆盖不同的定居点集合使用半径r = 2 km。此外，我们对新站点的数量感兴趣：我们希望用尽可能少的站点覆盖尽可能多的定居点。 这一目标导致了以下优化问题的定义，不幸的是，这是NP完全的：定义2.1[沿直线覆盖]给定平面中整数坐标点的集合P，作为平面中有限个线段的并集的连通集L，以及正整数d和K jPj，P的点可以被至多K个直径为d的圆盘覆盖，所有圆盘的中心点都在L中吗？定理2.2直线覆盖是NP-完全的。证据我们把圆盘几何覆盖问题归结为上述问题。圆盘的几何覆盖已被证明是NP-完全的[3]，并且可以表述如下：给定平面上整数坐标点的集合P和正整数d和K jPj，P的点能被至多K个直径为d的圆盘覆盖吗？给定一个圆盘几何覆盖的实例，使用相同的点集P和相同的数d和K，并如下定义集合L，以构造一个直线覆盖的实例：对于来自P的每对无序点p1和p2(i) 将形成p1和p2之间的线段的点添加到L，(ii) 把p1和p2的平分线上足够大的点加到L上。声明：P可以被至多K个直径为d的圆覆盖，当且仅当P可以被至多K个直径为d的圆覆盖，且这些圆的中心点都在L中。为了说明这一点，首先假设P可以被某个集合C覆盖，该集合C由至多K个直径为d的圆盘组成。然后，对于每个盘c 2 C：如果c不包含P的点，则忽略c。如果c只包含P的一个点p，那么用圆心为p（p在L中，因为从p到任何其他点的所有线段都在L中）和直径为d的圆盘代替c。4ATMOS 2001 { H. Hamacher等人如果c包含P的一组点A，其中jAj为2（即，c包含P的多个点），则用一个圆心为q、直径为d的圆代替c，其中q是A的最小封闭圆的圆心由于c覆盖了A，所以最小的封闭圆的直径较小或等于d，因此半径为d且中心点为q的圆盘也覆盖A。注意，nding q是位置理论的一个众所周知的问题，可以在线性时间内完成[4]。此外，还知道q总是位于A [2]中至少一个点的平分线上，使得q满足q2L.总之，P可以被最多K个直径为d的圆盘覆盖，所有圆盘的中心点都在L中。另一个方向是直接的。2注意，在L中只有一条线段的特殊情况下，沿直线覆盖变成了一个约束矩阵为区间矩阵的集合覆盖问题。因此，在这种情况下，问题是多项式可解的线性规划。如果不同线段的两个停靠点不能覆盖任何沉降，则3旅行时间模型需要更多的符号来说明旅行时间模型。我们假设L被给定为嵌入平面中的网络G =（V; E）。请注意，所有现有的列车停靠站都包含在V中。对于点x2 L，设e（x）2 E表示G中x所在的边.此外，对于每个边e，沿着e行进的客户的数量由we表示。然后对于新的停止点的集合X，td（X）=Xs we（x）X2 X给出了乘客的额外旅行时间量，这是由列车的额外停车活动引起的。(We假设恒定的时间延迟s是由列车的任何附加停止引起的另一方面，一些乘客将节省旅行时间，因为新的在我们的模型中，点p 2 P的距离的减少由下式计算：l2（p; S）l2（p; S[ X]）;其中SV表示已经存在的火车站的集合，并且l2（p; Y）是从p到Y中的任何点的最近欧几里得距离，因为它已经在可达性模型中使用过。为了将距离的可能减少转化为节省的访问时间量，我们引入分段线性函数g：IR IR！IR在两个变量中，为距离的每次减少分配节省的时间量5<>f（X）：= Xv pg（l 2（p; S）; l 2（p; S [X]）ATMOS 2001 { H. Hamacher等人给定为一对，由定居点到最近火车站的新旧距离组成。例如，g可以定义为：g（x; y）：=（x y）=5;假设平均速度为5 km/h，或8x y 如果x1（客户步行）4>g（x; y）=xy7X y如果1 x5（客户使用自行车）如果5倍（客户使用公共汽车或汽车）：20请注意，此定义将假定客户使用的是用于距离x的运输。对于每个p2p，表示通过vp进行相应结算的客户数量，通过节省的访问时间对旅行时间的正效应可以通过下式计算：ta（X）=Xvp g（l2（p; S）; l2（p; S[ X））：p2P旅行时间模型现在可以总结为：使得max ta（X）td（X）x 2 L，所有x 2 X：请注意，我们忽略了由于在不同的火车站开始或结束旅行而引起的火车乘坐时间的变化，假设这些火车乘坐时间的增加和损失大致相等。我们现在可以定义相应的问题Saved Travel Time，并证明它的NP完全性：定义3.1 [节省的旅行时间]给定平面中整数坐标点的集合P，每个点具有非负权重v p，平面中的嵌入网络G =（V; E），其每个弧具有非负权重we，子集SV，正数s和实数K，并给定两个变量g的分段线性函数：IRIR！IR，在G的边上是否有一组点X，使得p2Px2X定理3.2节省的旅行时间是NP完全的。证据我们减少沿线覆盖以节省旅行时间。以定义2.1中的沿P，L，d和K的直线覆盖为例，用自然界中L中的线段构造一个网络G =（V; E）。6ATMOS 2001 { H. Hamacher等人方法（即，V是线段的端点和交点，E是通过用它们的交点细分它们而获得的线段的部分），使用相同的点集P，并定义r：=d=2; S：=;;对于所有p 2 P，vp：= M，其中M > jPj;对于所有e 2 E，we：= 1;以及s：= 1：此外，g（x; y）：=1 如果y R有了这些定义，我们就知道：0，否则f（X）=Mjcver（X）j jX j其中覆盖是相对于集合P来定义的。声明：存在关于f（X）MjPj K的节省旅行时间的解X当且仅当存在关于不超过K个圆盘的沿线覆盖的解。要看到这一点，假设rst X是节省旅行时间的解，f（X）Mj P jK。则cover（X）=P，否则jcover（X）jjP j1并且因此f（X）=Mjcver（X）j jX jM jcover（X）jMjPjMta（fcg）的每个候选者c来减少候选者的集合。参见图2的右侧的图示。利用用于行进时间模型的候选者C的该缩减集合，遗传算法的自然应用与长度为jCj的位向量一起工作，其中每个位代表恰好一个候选者。所以11... 1描述了整个集合C，00... 0描述空集，并且每隔一个长度为jCj的位向量描述由C的一些成员组成的一组新的列车停靠点。为了生成用于遗传算法的i个个体的起始群体，我们或者使用固定概率p来确定i个Cj位中的每一个是否被设置为1，或者对于每个位b，我们首先随机地确定一个数字pb2f0：001;0：002; ： ：;0：999 g，然后使用pb作为概率来确定b是否被设置为1。为了从给定的种群中产生下一代，我们将给定的种群分成两半，其中一半包含具有最高节省旅行时间的个体。然后在这些“较好的”个体中，我们重复地随机选择两个不同的个体进行“交配”。我们首先通过随机地选择一个交叉点j2f1;2; ： ：;jCj1 g来配对两个个体，然后通过交换由jCj j比特组成的尾部来应用交叉。例如，如果jCj = 9的两个个体101100100和110110010在交叉点j= 4处交配，则得到的两个个体是1011 10010和110100100。最后，我们以非常低的概率p m（\mutation”）来ip新个体的一些比特。所以下一代由上一代中较好的那一半，加上交配的结果组成9ATMOS 2001 { H. Hamacher等人Fig. 1. 左图：现有列车停靠站的情况。右图：1000代后的解，如图3所示。黑色圆圈表示现有的火车站，红色（阴影）圆圈表示新的火车站，绿色（阴影）正方形表示覆盖的定居点。图二. 左：原始候选人集。右：候选人的缩减集。从这个更好的一半的人彼此，正如刚才所描述的。5应用及实验结果我们将第4节中描述的遗传算法应用于描述德国情况的一组初步输入数据。现有6 900个停靠点，其多边形边由8 700条线段组成，30 600个居民点及其人口和铁路估计数量的方式客户。图1左侧是德国南部的一小段摘录，描绘了这种现状。用于遗传算法的候选人的集合由6 700个潜在的新停靠点组成。原始的候选集合和缩减的候选集合在图2中示出。假设每个额外停靠站的时间延迟s为2分钟，并且函数g（x; y）：=（xy）=5描述当到最近的列车停靠站的距离从x km减小到y km时访问时间的增益，我们以此开始遗传算法。10ATMOS 2001 { H. Hamacher等人一组候选人和nd，其中对于20的群体大小，每个人三次固定概率p2f0：25;0：5;0：75 g。交叉后比特突变的概率Pm被设置为0.0001。在每代100代之后，我们让迄今为止具有最高节省旅行时间的结果种群再进化900代。图3显示了该种群在1000代中的发展过程。为了进行比较，我们以种群大小为100的每个个体的每个比特b的不同初始概率pb启动遗传算法，结果表明，遗传算法很快地得出正确的解的密度，也就是说，我们实际上并不首先需要确定一个好的概率p来创建初始种群：虽然初始种群具有不同的初始概率pb，其中包含几乎没有候选人的个体以及几乎所有6700个候选人的个体，但第10代个体中最低和最高候选人数量之间的差异已经缩小到不到1000，而100代之后，这种差异仅为22。图1的右侧显示了我们的遗传方法迄今为止找到的具有最高节省旅行时间的解决方案。它显示了图2右侧的几个候选站点实际上成为新的站点，在此摘录中，新列车站点的位置看起来是合理的，并且如图3所示的该解决方案的开发是有希望的。但是，当我们在德国的其他地方更仔细地检查这个解决方案时，我们注意到，在某些地方，解决方案中有许多事实证明，这些影响是由输入数据的不准确性引起的：例如，不切实际的低数量的沿着边缘旅行的客户使得沿着这些边缘放置新的停靠站太“便宜”，导致太多的新火车停靠站。这些和其他问题意味着，由遗传算法找到的解决方案不应被视为用于设置新的列车停靠站以节省旅行时间的最终建议，并且必须谨慎地阅读图3的垂直轴上指示的节省的旅行时间的量。相反，我们提出了一种算法方法，如果克服了输入数据的当前问题，当目标是最大限度地节省旅行时间时，可以为新的火车站的位置产生有用的结果6结论研究在现有铁路网中引入新的火车站的效果，我们考虑了两种模型，一种是基于火车站与人口的接近程度，另一种是基于所有客户的总体节省旅行时间的最大化对于这两个模型，我们已经证明了自然产生的优化问题的NP-硬度。对于旅行时间模型，我们已经应用了遗传算法，我们已经表明，它可以产生有用的解决方案，尽管NP-硬度的结果。然而，对于rst模型，仍然需要开发和应用算法方法在这里，目标11ATMOS 2001 { H. Hamacher等人1211109870 200 400 600 800代1000图3.第三章。目标函数的开发节省了旅行时间超过1000人口规模为20。将是寻找具有目标函数的双标准问题的帕累托最优解，目标函数是由一组新停靠点覆盖的人口的百分比（要最大化）和新停靠点的数量（要最小化）。此外，对于这两个模型，考虑的效应的恢复也是期望的：不是取决于其距火车站的距离至多或大于给定半径r来覆盖或不覆盖定居点，而是可以考虑部分覆盖定居点，其中其覆盖百分比以某种更精确的方式取决于其距火车站的距离。类似地，需要比简单地假设平均速度为5 km/h更现实的函数，用于将从列车停靠站的距离的减少转换为节省的访问时间量。最后，在我们的两个模型中没有考虑的新火车站的其他方面包括建设和运营成本。考虑一个动态模型也是很有意义的，在这个模型中，由于新的列车停靠站而引起的顾客数量的变化也被考虑在内。确认我们要感谢Ste en Mecke为这项工作所需的实现。节省的旅行时间（mm12ATMOS 2001 { H. Hamacher等人引用[1] Drezner，Z.和H. Hamacher，editors，\Location Theory：Applications andTheory，”Springer，2001.[2] Elzinga，J.和D. Hearn，Geometrical solutions for some minimax locationproblems，Transportation Science6（1972），pp. 379{394.[3] 约翰逊，D。 美国，NP-完备性列：一个持续的指南，J.算法3（1982），pp。182{195.[4] Megiddo，N.，IR3中线性规划的线性时间算法及相关问题，SIAM J. onComputing12（1983），pp. 776.[5] 里夫斯角R.，遗传算法，在：C. R. Reeves，editor，Modern HeuristicTechniques for Combinatorial Problems，McGraw Hill，1995 pp. 151{196.
