两相交线路上的车站选址问题：角度保留算法

理论计算机科学电子笔记92（2004）52-64www.elsevier.com/locate/entcs两相交线路Maria Flavia Mammanaa，1 Ste Escheren Meckea，2 DorotheaWagnerb，3a德国康斯坦茨大学计算机和信息科学系b德国卡尔斯鲁厄大学计算机科学系摘要车站选址问题是指在现有铁路网络的轨道上设置新的车站，以增加用户数量。本文考虑由两条相交线构成的铁路网的问题。 本文提出了一种在多项式时间内求解α很大的角的保留字： 站点位置，圆盘覆盖，设施位置1介绍车站选址问题是指在现有铁路网的轨道上设置新的车站，以增加用户数量研究这一问题的动机主要是为了在现有的铁路网中增加列车旅行对地方交通的吸引力。 但是，新的车站对公司来说是昂贵的，新的车站将导致那些已经使用网络的人的旅行时间更长。因此，我们的目标是尽量减少新车站的数量实际上，这项研究的动机是与德国铁路公司合作，1Ekavia@dmi.unict.itecke@ira.uka.de3dwagner@ira.uka.de4作者感谢欧盟根据HPRN-CT-1999-00104号拨款为RTN AMORE提供的财政支持。1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2003.12.022M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-53问题然而，在本文中，我们考虑了一个稍微简化的场景，例如，我们忽略了建造车站或旅行时间的实际成本交通网络中的站点定位问题已经在几篇论文中进行了研究，分析了公共汽车交通网络以及铁路网络。在[5，3，4]中考虑了在公交网络中定位站点的问题，所有这些都涉及从一组给定的候选站点中打开新站点的问题在文献[ 1 ]中首次提出了车站选址问题并对其进行了建模，但它不是NP完全问题。 Schéobeleta l. [6]描述了从站点定位问题到离散集合覆盖问题的一个简化特别是对覆盖矩阵进行了分析，并对铁路网仅由一条直线组成的特殊情况给出了一种有效的Kranakis等人[2]研究了在[7]中，提出了覆盖人口区域的问题。在以前的论文中，定居点被表示为点，在[7]中，考虑了需求区域，并给出了在铁路网由一条直线组成的情况下寻找最优解的有效算法。虽然一个线段的站点定位问题在多项式时间内是可解的，但一般情况下，对于两个或更多线段，该问题变得NP困难[1]。然而，一个启发式的方法来解决车站选址问题在实践中包括一个铁路网络分解成独立的线段。然后，为了更好地解决问题，需要更详细地考虑线段之间的公共区域。本文中考虑的问题可以被视为朝着这种方法迈出的第一步。本文件的结构如下。在第2节中，车站选址问题被建模为一个最小化问题，并定义了本文研究的问题的变体。在第3节中，我们定义了两条直线的公共区域被圆盘覆盖的问题，并刻画了解的特征这个问题取决于两条线之间的角度。在第四节中，我们研究了两条相交直线上的站址问题，并应用圆盘覆盖问题的结果，得到了两条相交直线夹角α54M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-PPS研发P2问题定义给出了一个铁路网和一个居民点集合P。一个居民点Pi∈P被铁路网覆盖，如果有一个车站距离Pi小于或等于一个固定半径R。 我们假设没有一个定居点目前，一个现有的车站已经覆盖了该地区，每个定居点都可以被一个新的车站覆盖，车站可以沿着轨道放置在任何地方。目标是选择尽可能少的新监测站，以覆盖所有定居点。确切地说，给定平面上的一组点S，定义cover（S）={x∈R2：d（x，S）≤R}作为距离小于或等于从，距离是欧几里得距离。然后，站点定位问题可以被建模为以下最小化问题：给定一个几何图G=（V，E），即平面上的顶点集V和表示为直线段的边集E，平面上的点集P和固定半径R。求边上的顶点数S的最小值，使得P覆盖（S）。[1]通过对几何覆盖问题的变换，证明了站址问题的NP-困难性。几何覆盖由圆盘定义如下：给定平面上的一组点P，找出覆盖P的圆盘D的最小数目，其中平面上的一个点Pi被一个中心在c且半径为R的圆盘D=（c，R）覆盖，如果d（Pi，c）≤R。本文研究了当铁路网由两条直线组成，其公共端点O成夹角α时的车站选址问题， 的公共区域， 两条线更准确地说，对于给定的半径R和两条直线l1、l2，我们把平面上的面积称为l1和l2的公共面积，该面积一方面可以被圆心在l1上的半径为R的圆所覆盖，另一方面可以被圆心在l1上的半径为R的圆所覆盖。 见图1 然后定义：两条相交线上的测站定位（SLTL）：给定一个几何图G=（V，E），它由两条相邻的边组成，表示为直线段，两条线的公共区域中的一组点P，以及固定半径R。在O∈S的边上找到一个最小的顶点数S，使得P∈Cover（S）。M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-55◦L1OL2Fig. 1. 灰色区域是线l1和l2的公共区域。3圆盘覆盖在这一节中，我们研究了圆盘几何覆盖问题的一个变形。给定两条线段l1和l2，它们有一个共同的端点O，我们感兴趣的是用以任意一条线为中心的圆来覆盖线l1和l2准确地说：两线圆盘覆盖法（CDTL）：给定两条直线段，其公共点为O，构成一个角α<180°。确定以任一行为中心的覆盖公共区域的最小磁盘数这两条线。显然，CDTL问题的最优解至少是SLTL问题的可行解。3.1双线圆盘覆盖在本段中，我们讨论了sid e rCDTL，条件是sα≥ 60Ω且41。4◦≤α<六十 让我们介绍一些我们在论文中使用的符号。 图2说明了符号。我们假设R = 1。•l1和l2是CDTL问题的两条线;• O是线l1和l2的公共端点;• α是直线l1和l2形成的角;• −x−O→y是在O中具有vingorig的p通道中的正交坐标system，正x轴在角α的平分线上;•t1和t2分别是在距离l1和l2为1处的两条线，它们在正x轴上彼此相交;56M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-• C是以O为中心的圆盘，半径为1;• O1是直线t1和t2的交点;• C1和C1是通过O1的l1和l2的两个独特的分散的相互独立的光;• O−=（−1，0）和O+=（1， 0）;• A是直线t2和圆盘C的交点;• B是直线t1和圆盘C的交点。−→yBC1JL2O−OO+C一t2O1t1L1C1−→x图二. 符号。引理3.1 CDTL的任何最优解至少包含三个圆盘。证据以O为中心的圆盘C是唯一覆盖O−点的圆盘。只有C1和C1J两个方向将点O1转换为在直线t1和t2上与它无限接近的点。Q因此，不失一般性，我们可以假设圆盘C、C1C1J包含在CDTL问题的任何最优解中。的下一步是调查需要覆盖的光盘数量，公共区域的剩余部分（参见图2。）更确切地说，我们考虑以下问题：给定两条直线段l1和l2，在一个节点O上，盘C、C1和C1J。Findheminimset包括C、C1和C1的盘S的第一次拷贝在一个区域上。引理3.2当60 α ≤ α时，覆盖公共区域的最小圆盘数是3。我的律师。我们提供了光盘C、C1和C1J覆盖公共区域，如果由线sl1和l2形成的角α大于或等于6 0°。ACCOrdingM.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-57211M√−±对于正交坐标system−x−O→y，如果m=tan（α），m>0，则：l1：y= −mxl2：y=mx√t1：y= −mx+1+m2t2：y=mx。1+m21+m2ΣO：（0， 0）O1：。C：x2+y2= 1C1：m，0x−m1+m22002年。Σ2+y+m1+m2= 1。这三张唱片都是我的。如果圆盘C1通过，则会出现异常情况或者包含点A = if。m1+m2，M11+m2 。 C1通过点A，Σ211+ m2 −m1+m2= 11 1这导致m=m3。由于m > 0，唯一可接受的解是m = 103，而相应于α=600。Q注意，当角α等于第6个圆盘C1和C1J时，穿过点O+和线段O+O1的点都包含在两个圆盘中。参见图3。图3.第三章。 当eα=60Ω时，引理3.3当41时，覆盖公共区域的圆盘的最小数目是5。4℃≤ α<60℃。证据 让O。=1−m2Σ，0是C，CJ和2m1+m211x-axis，otherthanO1. 当角度α小于60°时，点A和B不被圆盘C1和C1J覆盖，也不被直线AO1和BO1上与它们无限接近的点以及线段O2O+上的点覆盖。看到图4.C2和C2j是通过O2的圆盘，中心位于l1和l2上。五个问题C、C1、C1J、C2和C2J，如果圆盘C2通过或−58M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-M√−≤≤BO+OO2O1一图 四、这些未覆盖的内容是针对<60位用户和三位用户的。包含点A=。m1+m2，11+m2Σ。 C2通过点A，如果。m122002年。2Σ2−3m−11− 3 m1+m2−m（1+m2）+1+ m2+（1 + m2）1 1 1这导致m= ±0.3，±0.7。 唯一可接受的解是m=107，当α=41时，4英里。更进一步，四个方向C、C1、C1J和C2不覆盖公共区域，因为盘C2不包含点其中T是线t1和盘C2的交点。 见图5Q图 五、 当eα=41时，4英里。3.2CDTL算法在前一节中使用的方法导致了在该截面中由圆盘算法所示的覆盖。就该宗案件而言，α和41。4◦α<60分别为3.2和3.3。第41章<. 4、算法简单，根据引理3.3的证明，在两条线上放置圆盘。然而，在这方面，M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-5912∩∩XXXXXXX1X1X1XX1XXX1X2这产生了不一定是最优的解决方案。总之，当α为Gr e a t erthanorrequalto4 1. 4、其他可行的解决方案。 它可以提供α<41的最佳解决方案。4英里。但这需要一个详细的案例区分。算法1CDTL输入• 两条线l1和l2，其公共点O形成小于180°的角α;• c.圆盘中心在O;• bis，l1和l2的平分线。输出覆盖公共区域的光盘集合D该算法使用以下符号。• cX在两个圆之外，通过点X，其中心在线l1上，即不在D中的那一个;• cX是通过点X的两个圆盘中的一个，其中心在线l2上，该点不在D中;• l11m，X1是通过点X1的上垂线;• Z=dt2是，在圆盘d与直线的两个交点中，t2，更接近A的那个;• Z= d bis是，在圆盘d与直线的两个交点中，bis，与O.1：X：=t1<$t22：计算c1 和c23：D：={c，c1，c2}4：当A不被覆盖时，5： X1：=c1t26： X：=c1双7：X2：=11，X1bis8： 如果d（O，X2）≤d（O，X），则9：计算c1 和c210：D：=D<${c1，c2}X X11：其他12：计算c1和c213：D：=D{c1X1}14：c1 ：=c115：c2 ：=c2，c60M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-+2XX111我我OO+PO+PA一CO+CA第4-15行中的循环 点X和X2，在第6和第7行中，是我们为了找到下一张光盘而参考的那些。该算法在时间上与磁盘数量成线性关系引理3.4如果α小于或等于60 π，则任何以线l1为中心覆盖点A的圆也覆盖点O+。证据 设CA和CO+是半径为1的圆，圆心在A和O分别参见图6。见图6。 圆盘CA和CO+以包含在两个圆盘的交点中的l1上的点为中心的圆盘是唯一覆盖A和O+的圆盘。设PA={CA<$1}\O，PO+={CO+<$1}\O，λ：= λO+OPO+和λ：= λAOPA.这是足够的，显示OPA和OPO+。由于三角形OOPO+和OAPA是等腰的，则OPA<$OPO+当且仅当<$≤ <$。 它是α = α和α =90 <$−α，那么如果α≤ 60 μ m，则α ≤ 10μ m。Q引理3.5若d（O，X2）≤d（O，X）则圆C1包含点I1，如果d（O，I2）> d（O，I），则圆C1包含点X。证据 这可以很容易地证明应用勾股定理。Q定理3.6由算法1产生的圆盘的集合D覆盖两条给定线的整个公共区域。证据 设P是公共区域中的一个点。 如果P与O的距离小于或等于1，则它被圆盘c覆盖。设P是一个点，三角形O1O+A和D1={Di}是圆心在l1由算法产生我们将证明P至少被一个在Dl. 考虑区间Ibis= Dibis和It2= Dit2，令lbis和lt2分别是lbis和lt2中离O1最远的点。注意我我我+M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-6111P我我我我我我l之二l之二我i−1lt2lt2我i−1DiO+O双阿尔巴，阿尔巴t2bist2左点l和l间隔分别沿O1O+和O1A出现，指数。对于i >1，设Poli为顶点为lbis，lbis，lt2，lt2和Pol1二吨i i−1i−1我三角形l101l2参见图7。根据引理3.4和引理3.5，多边形Poli（1 ≤i≤|Dl|）包含三角形OO+A，因此点P包含在至少一个多边形Poli中。因此，P包含在圆盘Di中，因为它是凸的并且覆盖Poli的所有顶点。Q见图7。多边形Poli4车站选址问题如前所述，给定现有的铁路网络和n个集合的集合P，问题是覆盖安置尽可能少的我们代表：(i) 将铁路网作为平面图，其中节点是车站，边是代表车站之间轨道的直线段;(ii) 集合P是平面上的n个本文考虑SLTL问题，其中网络由两条线段组成，l1和l2形成一个角α，并且给定一组点都位于两条线的公共区域定理m4.1当α≥ 60μ m时 ， 时 间 间 隔 将 覆 盖P中 的 所 有 时 间 间 隔。证据根据引理3.2，两个圆盘，加上一个以公共点为中心的圆盘，足以覆盖两条直线之间的公共区域，当两条直线形成的夹角α大于或等于60°时 ， 称 为 公 共 点。Q1162M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-1联系我们2P11P1PP21221112221221定理m4.2如果41，则在P中的所有集合上都有五个元素。4℃≤ α<60℃。证据根据引理3.3，当两条直线形成的角α大于或等于时，四个圆盘加上一个以公共点为中心的圆盘方程41. 4个月和6个月 的 时 间 里，Q我们现在想要在线l1和l2上生成覆盖给定定居点P的最小点集。设Pi∈P.我们称Ci为圆心为Pi半径为R的圆.由于每一个沉降点都可以由轨道沿线的新车站覆盖，因此Ji：=CiL1L2不是空的 让Ji是点Pi在直线l1上引起的间隔，Ji是点Pi在直线l2上引起的间隔。那么，当且仅当在Ji=Ji <$Ji中有一个车站时，沉降Pi被覆盖。设I1={I1}和I2={I1}是由所有分别在直线l1和l2上的点 更准确地说，如果Ji= [ai，bi]和Jj=[aj，bj]是由Pi和Pj在l1上诱导的一个参考值，因此，1 1 1如果ai≤aj，则它们检测子区间：[ai，aj]，[aj，bi]，[bi，bj]ifbi≤bj或[ai，aj]，[aj，bj]，[bj，bi]ifbi≥ bj.这可以扩展到任何数量的间隔。请注意，每条线上的子区间数最多为2n- 1。定理4.3一个O（n）时间算法最优地解决了SLTL问题，如果α≥ 60Ω。证据 设P ={Pi：1 ≤i≤n}. 对于所有的Pi∈ P，计算区间Ji和Ji. 设Ii：=Ii−1<$Ji和Ii：=Ii−1<$Ji。 注意，Ii和Ii是在l1和l2上的区间覆盖了所有点直到Pi。 如果In= In= N，我们需要两个站，除了O，我们只需要一个。 计算时间间隔Ii和Ji对每个i都需要常数时间。QJ J定理4.4一个O（n3）时间算法最优地解决了SLTL问题，如果41。4℃≤α<60℃。证据 对于给定的集合，算法2连续地检查是否可以由两条线路上的两个、三个或四个站的集合覆盖。如果不是所有的点在可以由四个车站覆盖的情况下，结果是用五个车站覆盖两条线路的整个公共区域。因此，时间复杂度为O（n）。QM.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-63PP∈I<$∈I∈I<$∈I∈Pn111122212111222121211122212算法2SLTL输入具有公共点O的两条线l1和l2，在l1和l2的公共区域中的点的集合;输出l1和l2上的一个、两个或三个区间的集合，使得O连同来自该集合的每个区间的一个任意点覆盖;如果不存在这样的集合，则覆盖整个公共区域的五个点1：I0：=l1，I0：=l21 22：对于Pi∈P，3： Ii：=Ii−1<$Ji4： Ii：=Ii−1<$Ji5：如果In/=0或In = 0，则6：分别输出O和In。In1 27：其他8： 对于每个子区间I1 2，9：I0：=l1，I0：=l21 210：对于Pi∈P，11：如果Pi被I覆盖，则12：Ii：=Ii−11 113：Ii：=Ii−12 214：其他15：Ii：=Ii−1<$Ji16：Ii：=Ii−1<$Ji17：如果In/=0或In/=0，则18：分别输出O、I和In。In1 219：如果In=In =In，对于所有I∈I1< $∈I2then20：对于每对子区间I，IJ1 2，21：I0：=l1，I0：=l21 222：ForPido23：如果Pi被I或IJ覆盖，则24：Ii：=Ii−11 125：Ii：=Ii−12 226：其他27：Ii：=Ii−1<$Ji28：Ii：=Ii−1<$Ji29：如果In = 0或I2/=0，则30：分别输出O、I、IJ和In。In1 231：如果对于所有子区间对I，IJ，32：在覆盖整个公共区域的l1和l2上输出五个点如果我们不假设两条线的公共点O上一定有一个站，那么当两条线的公共点O上有一个站时，O（n2）算法解决了问题。64M.F. Mammana et al. / Electronic Notes in Theoretical Computer Science 92（2004）52-≥ O≤角α60磅和一个N（n4）a ltamm解41的问题. 4◦α<60◦使用与定理4.3和定理4.4相同的方法。5结论考虑了两条相交直线段的公共区域的覆盖问题.一般来说，这个问题是NP难的。给出了该问题解的一个依赖于线段夹角的特征。这导致了一种算法，其运行时间与盘的数量成线性关系，以找到覆盖公共区域的小的（尽管通常不是最小的）盘的数量。最后，将所得结果应用于两条相交轨道形成极大夹角的铁路网的车站选址问题从我们与德国铁路公司的合作中，我们知道，在只有一条轨道与新车站有关的大区域，铁路网络在某种程度上是可分解的。对于未来的工作，这将是有趣的应用分解技术的铁路网络，其中我们的结果可以作为一个子程序的区域，轨道满足。6确认作者感谢AnitaScho？bel提出的富有成效的意见，感谢SabineCornelsen和LeonPeeters对论文介绍提出的有益意见引用[1] Hamacher，H. 、杨A. Liebers，A. Schéobel，D. Wagner and F. 王文，张文，等.铁路运输系统中的网络拓扑结构.北京：交通大学出版社，2001.[2] Kranakis，E.，P. Penna，K.Schlude，D. Taylor和P. Widmayer，改善客户对火车站的接近度，技术报告，苏黎世联邦理工学院（2002年）。[3] Murray，A.，提高公共交通系统可达性和扩大可达性的覆盖模型，技术报告，俄亥俄州立大学地理系（2001年）。[4] Murray，A.，公共交通覆盖率战略分析，社会经济规划科学35（2001），pp. 175-188.[5] Murray，A.，R.戴维斯河Stimson和L.费雷拉，公共交通接入，交通研究3（1998），pp。319-328.[6] Schéobel，A.、H.Hamacher，A.LiebersandD.Wagner，Thecontinuosstoplocationproobleminpublictransportation，Technicalreport，UniversitatKaiserslautern（2002），reportinWirtshafts-mathematik Nr 81/2001.[7] Schéobel ， A.和 M.Schréoder ， Coveringopulationareasbyrailwaystops ， Proceeding ingsofOR2002，Klagenetumto appear（2002）.