铁路车辆段的列车调车问题的图论方法及算法解决方案

理论计算机科学电子札记92（2004）16-33www.elsevier.com/locate/entcs分流问题的图论方法GabrieleDiStefano和MagnusLoveKoZurciDipartimentodiIngg neriaElettrica，Universit`adegliStudidell摘要在本文中，我们提出了一个图论的方法来解决铁路车辆段的列车调车问题。特别是在夜间，列车必须停在调车场，以便第二天早上的运营能够尽可能顺利地开始。 的社会总问题 是非常困难的，包括许多子问题。我们集中在以下子问题：如何安排列车在一个“正确”的顺序可用的轨道上，避免调车作业的出发列车的早晨。我们讨论了不同的情况下的问题，我们提出了算法解决方案和启发式方法。关键词：分流问题，置换图，3-一致超图，单峰序列1介绍铁路运营商必须解决许多复杂的决策问题，以便以合理的成本实现高质量的服务。其中之一是调车问题：在高峰时间以外，机车车辆过剩，特别是在夜间，旅客列车不得不停在调车场。一个主要的复杂问题是列车的运行受到车辆段铁路基础设施的限制。车辆段由一组轨道组成，根据轨道的类型，车辆段被称为调车场或编组场。在第一种情况下，所有轨道只能从一侧接近，在编组场，每条轨道可以从*根据合同号HPRN-CT-1999-00104（AMORE项目），1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2003.12.020G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）1617两边我们假设火车可以在两个方向上自行移动（例如，这是荷兰火车组的情况），并且我们不处理机车运动。火车的到达和出发是由时刻表来规定的：我们将讨论到达和出发在时间上混合的情况，以及第一次出发发生在最后一次到达之后的情况。关于调车问题的文献包括Winter和Zimmerman [14]以及Blasum等人[1]关于调度有轨电车的工作在这两篇论文中，所有的到达都发生在第一次离开之前。Gallo和Di Miele [4]讨论了他们在考虑混合到达和离开的车辆段中的公交车调度工作的扩展。在文献[10]中，旅客列车组面临调车问题，并讨论了该问题的几个方面以及一些数学模型。其他文件[9，8]处理的问题，重新安排列车车厢在一个火车站。几乎所有关于分流问题的文献都假定或证明该问题是困难的。本文的主要目标是调查的限制，使分流问题很难。为此，我们不考虑列车的大小和轨道长度，但我们主要关注由于车辆段类型和时间表导致的到达和离开顺序的限制。本文的组织如下：在一节符号和基本概念之后，在第3节中，我们讨论了最后一列火车在第一列火车出发之前到达的情况我们展示了一些结果有关的四个子问题所产生的施加一些约束的到达和离开direc- tions。在第4节中，讨论了调车场和编组场在最后一班车到达前发车的情况。最后一节涉及一些开放的问题。2基本符号和概念在下文中，我们假设列车根据车辆段区域的发车时间编号。特别地，第一列离开车辆段的列车编号为1，第二列为2，依此类推。然后，n列列车在车辆段到达的顺序是一个迭代π=[π1，π2， . . ，πn]的输出序列[1，2，.，n]。例如，序列[2，3，1]意味着共三列列车，第一列进站列车第二列出站，第二列进站列车第三列出站，最后一列最先出站。 注意，（π−1）i是列车i在一个传入序列中。它将被表示为πi−1，在上面的例子中，π2−1=1 ， π3−1=2 ， π1−1=3 。 Moreoverπρ 表示π 的 逆 序 列 ， 即 π ρ= [π n， πn−1，.，π1]。18G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）16∈≤≤H| |\E ∈ EE PEEP我们的目标是：| |⊆}⊆∈在序列S=[s1 ， s2 ， . . ， Sn]，则 S 的 子 序列是序列 SI= [Si1， Si2，.，Sin]。，s im]，使得1ij ikn对于每个jk。S=[s1，s2， . . ，Sn]称为单峰的，如果存在St，1≤t≤n，使得S1<，S2<，.< s t和s t> s t+1> s t+2>. > s n.一个单峰序列在t=n时称为递增序列，在t=1时称为递减序列。设P S={S1，S2，.，Sk}是不同元素序列S的连续集Si，1 ≤i≤k。PS称为S的一个划分，如果每个元素的序列只属于PS中的一个子序列。如果两个序列没有共同的元素，则它们是不相交的定义序列上的某些运算是有用的。 我们写s如果是S，则为S是序列S的元素，并且S的元素的数目由S表示。如果SJ是S的子序列，则S SJ表示从S除去SJ中的所有元素而得到的序列。 如果S和T是两个序列s.|= n和|不|= m，则由S和T的级联给出的序列，记为S · T，是具有S作为前n个元素的子序列和T作为后m个元素的子序列的序列，并且|T·S |= m+n。|= m +n. IfS=[s1，s2， . . ，Sn]是n个整数的序列，k是整数，则S+k表示序列e[s1+k，s2+k， . . . ，sn+k]。设V为顶点的有限集合。 让 （V）表示幂集，集合V，即， V的所有子集的集合。 对H=（V，）是一个超图，如果（V）. 是超图的超边集。 一个超图H =（V， ）称为k-均匀的，如果每个e正好有k个元素。 A 2-一致超图称为图，在这种情况下，超边称为边。一个超图H =（V，E）的k -染色是映射f：V−→ {1，.，k}，使得（除了单例）具有相同颜色的所有顶点H的色数，记为χ（H），是最小k，其中H允许k-着色。设G=（V，E）是一个图. VJV是G中的团，如果（u，v）对于所有的u，v，v，J，u=v。 w（G）= maxVJ：VJV和V'是G中的团 称为G的团数。3夜间仓库对于本节的问题，我们通常假设车辆段拓扑是编组拓扑，即每条轨道都可以从两侧接近。我们不考虑火车和轨道的长度。也就是说，我们假设每条轨道都有足够的长度来容纳分配给它的列车，我们还假设第一次发车发生在最后一次到达之后：这可能是夜间使用的车辆段的情况。下一节G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）1619讨论到达和离开在时间上混合的情况。以下所有问题的共同目标是使用最少的轨道数来容纳所有列车，而无需在输入或输出操作期间进行额外的调车通过对接近轨道的方式进行一些限制，我们定义了四个主要问题：SISO问题：单输入，单输出。在这种情况下，我们假设每个轨道可以从一侧接近，从另一侧离开，也就是说，轨道被用作队列。我们还讨论了在这种情况下，轨道被用作堆栈（即列车的输入和输出从一侧完成，另一侧不可访问）。这是调车场的情况。DISO问题：双输入，单输出。在这种情况下，每个轨道可以从两侧接收列车，但输出是从一侧完成的。在夜间，一般调车问题的一个主要目标是以这样一种方式停放列车，即第二天早上的运营可以顺利越好.因此，在站的方向上的单个输出侧是期望的要求。SIDO问题：单输入，双输出。这件事与前一件相反。即使没有实际的理由考虑这种情况，这个问题的研究也比DISO问题更容易，因为顺序存储在轨道中的列车的顺序将遵循输入序列中的顺序。很容易证明SIDO和DISO问题是等价的：我们将在3.2节给出证据。DIDO问题：双输入，双输出。在这种情况下，不施加任何限制。3.1单输入单输出（SISO）由于轨道被用作队列，因此每个轨道的列车分配必须以这样的方式进行，即轨道中的列车形成递增序列，也就是说，第一列出发的列车必须具有分配给轨道中存储的列车的最小这避免了在输出操作期间需要分流。定义3.1SISO问题：给定一个由n列进站列车组成的序列S，求S的一个分区，其中递增的列车数最少。给定一个序列S，我们可以用以下方式构造一个无向图G[S] =（V，E）：20G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）16≤≤- V ={s|s∈ S}-E={（si，sj）|[si，sj]是S的一个递减量}一个无向图G称为置换图，如果存在一个序列S使得G∈G[S]. 注意，在G[S]中存在一个dge（si，sj）如果si和sj的顺序不对，也就是说，相应的列车不能放在同一轨道上。此外，S的一个递减子序列对应于G[S]中的一个团。如果序列S被颠倒，则在S中形成递增子序列的每对列车现在是递减顺序的，反之亦然。因此G[Sρ] =G[S]，这表明置换图的补图也是置换图。定理3.2[7]给定一个由n列进站列车组成的序列S，解决SISO问题的最小轨道数为k当且仅当χ（G [S]）= k。证据 设kJ是序列S，并且令k_J=x（G[S]）。我们必须证明kJ=kJJ。解决SISO问题的最小轨道数必须大于S中最长的递减子序列SJ，因为SJ中没有一对列车可以放在同一轨道上由于递减序列SJ对应于对于G[S]中的一个团，则KJ≥ω（G[S]）.现在，让我们假设有一个G[S]的着色然后我们可以找到一个可行的解决SISO问题的方法是将所有颜色相同的列车放在一条轨道上。事实上，如果两个火车si和sj被着色为相同的颜色，则它们必须形成递增子序列，否则（si，sj）是G[S]的边，并且两个火车不能被着色为相同的颜色。作为结论，KJ≤χ（G[S]）。则ω（G[S]）王空军χ（G[S]）。 但置换图是完美图(see[7]），并且这些图的色数与团数相等。 因此，ω（G[S]）=χ（G[S]），这意味着KJ=χ（G[S]）=KJJ。Q我们报告了一个算法（见算法1），根据相应的算法来分配轨道上的列车着色置换图[2，7]。算法1使用向量LAST，LAST[i]保存第i条轨道上的最后一列火车.该算法需要O（nlogn）的时间来分配一个序列S的每一列火车与一个适当的轨道。实际上，循环2-请注意，在只能从一侧接近轨道的情况下（即调车场的SISO问题），如果[si，sj]是递增的，则两列列车si，sj∈S（其中S是输入序列）不能在相同的列车中运行S的子序列。在G[S]中，边（si，sj）是存在的，对于所有G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）1621←2←←联系我们←←←算法1编组站在线SISOR等式：A等式eπ=[π1，π2， . . ，πn]的n个进站列车num从1到n被记录确保：使用最小轨道数k为每列列车分配轨道1：k 02：对于j= 1到n，3：i←F indtrack（πj）4：将列车πj放在轨道Ti5： LAST[i]πj6：k maxk，i7：结束算法2程序Findtrack1：i 1; t k+12：whilei=tdo3： r← [i+t]4： 如果πj>LAST[r]，则5：t r6：其他7：i r+18：如果结束9：结束时第十章： 回报我在S中按递增顺序排列的列车对，并且在按递减顺序排列的两个列车之间没有边。由于G[S] =G[Sρ]，则由定理3.2，色数χ（G[Sρ]）给出调车场存放入站序列S的列车的最小股道数。因此，轨道数可以在O（nlogn）时间内找到。通过观察算法1，我们可以注意到第i列火车的轨道选择不依赖于稍后到达的火车。这意味着相同的过程Findtrack可以用于SISO问题的在线版本，其中我们必须在不知道整个输入序列的情况下，在给定出发时间的情况下3.2DISO和SIDO问题编组场的DISO问题意味着进站列车可以从两侧接近每条轨道，但在早上，它们只能从一侧在SIDO问题中，轨道的使用是相反的，22G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）16E∈也就是进站列车可以从单侧接近轨道，但是出站可以从两侧进行。在下文中，我们将研究SIDO问题，因为存储在轨道中的列车序列必须是进入列车序列的子序列。这对于DISO问题来说是不正确的。 另一方面，很容易证明这两个问题是等价的（见定理3.13）。在SIDO情况下，序列S=[s1，s2， . . 如果列车在轨道上运行，事实上，设R为进站列车使用的轨道一侧，L为相反一侧。 序列SS=SL·SR， 其中SL=[s1 ， s2 ， . . . . ，st]是从L侧出 去 的 trins 的 能 量 ， 且SR=[st+1，st+2， . . . . 这是一个很好的例子trins从R边出去。SL中的火车必须形成一个递增的序列s1s2<<. st+2>.. > s m，作为第一列离开轨道的火车，这边这两个序列的级联是单峰序列。然后SIDO问题可以正式表述如下：定义3.3SIDO问题：给定一个由n列进站列车组成的序列S，求S的一个具有最小数量单峰连续性的划分。值得注意的是，两列火车的每个序列都可以存储在一条轨道中：在SISO情况下并非如此。另一方面，仅三列火车的序列可以要求两列火车。设[t1，t2，t3]是三列进站列车的序列如果t1>t2和t2t3，列车t2必须在其他两列之前离开车辆段：不可能没有调车操作。<因此，我们可以在一个单一的轨道上存储最多两个三列火车。为了保持这种约束，我们引入了谷超图的概念。公式3.4Givena序列S=[s1，s2， . . 对于n个不同的范畴，S诱导的谷超图是H S=（V，E），其中V={s，n|s∈S}和{si，sj，sk} ∈ E当且仅当si> sj，sj>|B| ≥ 1，则存在1f（a1）=f（a2）.a2∈A使得引理3.7在任何k（k−1）+1个不同整数的序列中，存在一个uni-k个整数的模态序列我的律师。 LetS=[s1，s2， . . ， s k（k-1）+1]是一个具有不同特征的序列。矛盾的是，S的每个含有k个或更多元素的子序列不是单峰的。我们将一对整数（xi，yi）赋给S的每个元素si，xi≥1是S中以si结尾的最长递增子序列的长度，而yi≥1是S中以si开头的最长递减子序列的长度。则xi+yi−1是最长单峰子序列的长度S的最大元素是si根据矛盾假设，不平等依然存在。xi+yi− 1>|B|，那么，通过鸽子洞原理，存在s i和s j，使得|, then, by using thePigeonhole Principle, there exist s iand s jsuchf（si）=f（sj）对于某个i j，即，（xi，yi）=（xj，yj）. 不失一般性地，让我们假设i j。然后，要么si sj，要么si> sj。如果si sj，则xixj通过定义（xi，yi）和（xj，yj），矛盾。如果si>sj，则yi>yj，矛盾。 Q24G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）16nk（k+1）.222−2222222≥定理3.8设H S是一个谷超图，|S|= n. 若χ（HS）≥k则n≥k（k+1）.证据 我们证明这个定理的归纳色数k。情形k= 1：如果χ（HS）≥1，我们必须证明n≥1，但这是显而易见的。情形k > 1：通过归纳，我们假设如果χ（H S）≥k−1，则n≥k（k−1）。 我们用矛盾的方法证明了归纳步骤，即假设χ（HS）≥ k，2从归纳和矛盾假设，我们得到k（k−1）≤n222+ 1=n2矛盾Q推论3.9给出了解决n列火车上的SIDO问题所需轨道数的上限下面的定理表明这个界是紧的。G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）16258n+1 12Fig. 1. SIDO问题中需要四条轨道的列车序列S4= [10，8，9，5，6，7，1，2，3，4]理论m3.10Letm e是一个任意的规则在tege。，但他总是，你的存在，谷超图H S，使得|S|> m且X（H S）=8|S|+1 12证据 我们证明这个定理，当|S|= n = k（k+1），其中k是任意的2正整数，使得n> m。在这种特殊情况i≥1是以下列方式定义的序列：，2、=k。 设Si，Si=0[1]如果i= 1（S i−1+ i）·[1，2，. ，i]否则图1显示了序列S4.我们证明了谷超图HSk具有|S K|= k（k+1）个元素，需要k种颜色着色。 通过感应在k上，我们假设HSk−1 有k（k−1）2元素，需要k-1种颜色，是有色人种。 归纳的基本步骤是显而易见的。很容易看出，k种颜色对于颜色HSk是足够的。事实上，Sk是由k个递增（然后是单峰）连续性的级联形成的。为每个子序列使用不同的颜色是足够的通过矛盾，让我们假设k−1种颜色足以使HSk着色。设x和y是3-一致超图H =（V，E）的两个顶点，T xy={z| {x，y，z}∈ E}是所有与x和y形成超边的顶点的集合。 设H（Txy）是H的顶点诱导在Txy中。如果χ（H）=χ（H（Txy）），则x和y必须用两种不同的颜色着色，否则H中存在一个超边，其中三个节点（x，y和Txy中的一个节点）用相同的颜色着色上述性质可以应用于HSk。设x和y是子序列[1，2，.]中的两个顶点。，k]的S k.则所有使得{x，y，z}是HSk中的超边的节点z都是子序列Sk−1+k的节点。让.26G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）16−/\8n+1 1−−T是这些节点的集合，令H（T）<$HSk−1+k是由T中的节点导出的HSk的子超图。注意由H（T）导出的谷超图与由Sk−1导出的谷超图同构，即HSk−1。然后，通过归纳假设，χ（H（T））=χ（HSk−1）=k− 1，并且x和y必须用不同的颜色着色，因为χ（HSk）=k1，假说.因此，子序列[1，2，...，k]必须用两种不同的颜色着色。但这意味着需要k种颜色，与假设k−1种颜色足以着色HSk.Q相矛盾算法3SIDO问题的航迹分配要求：n列进站列车的序列S确保：每列列车的轨道分配最多1：设置t= 12：当S= []do时3：SJ=最长单峰（S）4：将SJ中的每个元素分配给第t个轨道。5： 设置S=S6： 设置t=t+17：结束时，2、轨道根据目前的调查结果，我们可以看出，一个贪婪算法，108n+1 12跟踪. 给定一个序列算法3求S中最长的单峰序列SJ并将SJ中的每个列车分配到第一个可用轨道。 然后，迭代地， 它对剩余列车的序列重复操作。在算法4中示出的过程LongestUnimodal遵循与在算法4中使用的相同的技术。引理3.7：它将一对整数（xi，yi）与S的每个元素si相关联，使得xi≥1是S中以si结尾的最长递增子序列的长度，而yi≥1是S中以si结尾的最长递减子序列的长度从si开始（见第1然后它发现了最大的元素，最长的子序列SJ（第10-11行定理3.11算法3解决了n列车最多使用108n+1 12跟踪.证据算法3所使用的轨道数等于循环（第2-7行）重复的次数。接下来我们计算这个数字。G. Di Stefano，M.L.《理论计算机科学电子笔记》92（2004）1627≥−−··−{|∈}−- -{1}|∈}∈ ≥···2算法4程序最长单峰R等式：A等式S=[s1，s2， . . ，sn]，n1确保：S的最长单峰子序列SJ将（xi，yi）设置为（1， 1），对于每个i= 1， 2，···，n对于i= 2， 3，···，n，设t Xi=xjsj[s1，s2， . . . ，si−1]和sjsi如果Xi为空，则设置xi= max（Xi）+1/* max（Xi）= 0*/5：结束对于i=n1，n 2，， 1，Set Yi=yjsj[si+1，si+2. ，sn]和sjsi如果Yi为空，则设置yi= max（Yi）+1/* max（Yi）= 0*/端10：令st S，使得xt+yt xi+yi，对于每个i= 1， 2，.，n集合SJ= [st];x=xt;y=yt对于i=t−1，t− 2，···，1，如果xi =x1，则设SJ= [si]SJ15：设置x=x1如果结束，则结束对于i=t+ 1，t + 2，···，n，如果yi=y 1，则20：设置SJ=SJ[si]设y=y1如果结束，则结束设t i=i（i+1）.我们想证明，如果n

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