求選編鉤計(jì)劃最優(yōu)下落方案的一種最短路算法

孫 焰，牟世斌，張俊杰，張方華

（同濟(jì)大學(xué) 交通運(yùn)輸工程學(xué)院，上海 201804）

調(diào)車作業(yè)是鐵路運(yùn)輸生產(chǎn)過程的重要組成部分，也是行車組織的一項(xiàng)重要而復(fù)雜的工作。調(diào)車作業(yè)計(jì)劃編制的要求是盡量提高調(diào)車作業(yè)效率，減少調(diào)車作業(yè)時(shí)間。而調(diào)車作業(yè)效率主要是由作業(yè)中發(fā)生的連掛鉤數(shù)、溜放鉤數(shù)和帶動(dòng)的車輛數(shù)等因素決定的。機(jī)車進(jìn)入股道將車輛牽出稱為一個(gè)連掛鉤；用溜放的方法分解車列時(shí)，每分解一組稱為一個(gè)溜放鉤。由于在技術(shù)站連掛鉤的效率一般遠(yuǎn)低于溜放鉤，因此有關(guān)選編鉤計(jì)劃優(yōu)化編制的研究目標(biāo)大多是使連掛鉤數(shù)最少。傳統(tǒng)的下落列及合并方法可保證總連掛鉤數(shù)最少，但由于車列的下落方案不惟一，而且不同的下落方案直接影響溜放鉤的數(shù)目。本文的研究主要是從大量的下落方案中尋找最優(yōu)方案的定量模型及有效算法 (最優(yōu)方案為最優(yōu)調(diào)車后車組的排列順序在對(duì)應(yīng)線路不受限時(shí)的下落方案）。

1 傳統(tǒng)車組下落方法存在的問題

在編制調(diào)車作業(yè)計(jì)劃時(shí)，首先要進(jìn)行的是“車組下落”，即為了調(diào)整車組順序，把待編車列中的反順序車組分解到不同線路上[1]。而后根據(jù)車組下落的情況進(jìn)行“合并下落列”等作業(yè)來(lái)得到調(diào)車方案，不同的車組下落方案對(duì)應(yīng)著不同的調(diào)車方案。因此，車組下落情況對(duì)調(diào)車方案的優(yōu)劣有重要影響。

例如，待編車列中車組排列順序?yàn)?1 2 1 3 4 2 3，要求按站順選編。采用傳統(tǒng)方法下落后的車組情況如圖1所示。則用3條線的選編鉤計(jì)劃為(待編車列停留在①線)：1＋6，2－1，1－1，2－1，3－1，1－1，2－1，3＋1，2＋3，1－4，共用了 3 個(gè)連掛鉤和7個(gè)溜放鉤。但若按圖2所示方案分組，則同樣使用3條線的選編鉤計(jì)劃為(待編車列停留在②線)：2＋5，1－1，3－2，2－2，3＋2，2＋4，1－6，共用了3個(gè)連掛鉤和4個(gè)溜放鉤。

圖1 傳統(tǒng)方法的車組下落情況

圖2 較優(yōu)方案的車組下落情況

由此可見，在其他條件不變的情況下，僅改變車組的下落方案，就可使調(diào)車作業(yè)量發(fā)生明顯變化。不同車組下落方案對(duì)選編鉤計(jì)劃的優(yōu)劣有著決定性影響，主要是因?yàn)榇嬖凇翱烧{(diào)車組”，即下落位置可以在相鄰列之間調(diào)整而仍然符合連接正順序的車組。而可調(diào)車組又分為必可調(diào)車組和傳遞可調(diào)車組。根據(jù)傳遞可調(diào)車組對(duì)其他可調(diào)車組的依賴程度，可以分為一次傳遞可調(diào)車組、二次傳遞可調(diào)車組……[2]。

雖然有學(xué)者對(duì)有關(guān)問題進(jìn)行了研究，如使用“分析計(jì)算法[3]”計(jì)算各方案下車組的合列系數(shù)，并給出了一些判別條件和調(diào)整方法[2，4]。但是，由于各車組下落的組合情況太多，仍無(wú)完善的定量判別準(zhǔn)則和方法。有關(guān)研究都是基于統(tǒng)籌對(duì)口調(diào)車法，在保證連掛鉤最少條件下對(duì)溜放鉤進(jìn)行優(yōu)化，并尋找各車組的有利下落位置，但是其“篩選—優(yōu)化—計(jì)算”仍不能完全由計(jì)算機(jī)來(lái)實(shí)現(xiàn)[1-4]；也有研究提出了“消逆法”保證了“牽推鉤”最少，并能夠發(fā)揮“箭翎線”的技術(shù)優(yōu)勢(shì)，但是其“真逆組號(hào)”的判定與傳統(tǒng)下落列的方法是相似的，并未有明顯改進(jìn)[5]；有的研究運(yùn)用了基數(shù)排序的思想進(jìn)行調(diào)車，但是其優(yōu)化的方法尚不完善[6]。

可調(diào)車組下落位置的不同其實(shí)質(zhì)是同一到站的車組在其最終按站順選編完成后的車列中的排列順序不同。因此，只要求得待編車列調(diào)車后各車組的最優(yōu)排列順序，其對(duì)應(yīng)的下落方案就是最優(yōu)下落方案。本研究將調(diào)車后車組的最優(yōu)排列順序的求解轉(zhuǎn)化為圖論模型來(lái)進(jìn)行求解。

2 求最優(yōu)車組排列順序的一種圖論模型

求按站順調(diào)車后的車組最優(yōu)排列順序可以轉(zhuǎn)化為求一個(gè)有向圖的最小 Hamilton 路問題。一個(gè)圖或有向圖中的 Hamilton 路 (回路) 是通過圖中每個(gè)頂點(diǎn)一次且恰好一次的路 (回路)。

2.1 根據(jù)車列特性將問題轉(zhuǎn)化為有向圖模型

觀察站順后的車列可以發(fā)現(xiàn)，從首組到尾組，各車組是一個(gè)有序的排列。除首組和尾組外，每個(gè)車組都有一個(gè)與其相鄰的前序和后繼車組。在待編車列中，若按照調(diào)車后的站順，用有向弧依次將其相連，則從首組到尾組是一條 Hamilton 路，各種不同可行的調(diào)車后的排列順序?qū)?yīng)著不同的 Hamilton路，其中最小的 Hamilton 路則對(duì)應(yīng)著調(diào)車后車組的最優(yōu)排列順序。由于首站和尾站可能含有多個(gè)車組，均可相應(yīng)作為首組和尾組，因此需要增加兩個(gè)虛擬車組：一個(gè)虛擬起點(diǎn)車組與首組有向相連；一個(gè)虛擬終點(diǎn)車組與尾組有向相連。則調(diào)車后的車列在原待編車列中對(duì)應(yīng)著一個(gè)從虛擬起點(diǎn)到虛擬終點(diǎn)的有向路徑，而這個(gè)路徑經(jīng)過每個(gè)車組一次且恰好一次，即一個(gè) Hamilton 路。

設(shè)有一列由 n 個(gè)車組 m 個(gè)到達(dá)站組成的車列，其原始排列順序?yàn)?i1,i2,…,in，其中ij是{1,2,…,m}中的一個(gè)元素，表示其到達(dá)站的序號(hào)，j 表示車組在車列中的位置，如上例中 i1＝1，i2＝2，i3＝1，i4＝3……。按以下方法轉(zhuǎn)化為一個(gè) n＋2 個(gè)點(diǎn)的有向圖 G (V,E )。

（1）點(diǎn)集 V＝{0,i1,i2,…，in，m＋1}，將每個(gè)車組設(shè)為一個(gè)點(diǎn)，并虛增兩個(gè)點(diǎn) i0和 in+1，且 i0＝0，in+1＝m＋1。

（2）弧集 E＝{ejk| 節(jié)點(diǎn) ij到節(jié)點(diǎn) ik有有向弧相連，當(dāng)且僅當(dāng) ij＝ik或 ij＝ik－1}；即某個(gè)車組只與相同車站或緊后車站的車組有弧相連。

（3）弧長(zhǎng)C＝{cjk}，若節(jié)點(diǎn) ij到節(jié)點(diǎn) ik有弧相連，則弧上的權(quán)為：

弧長(zhǎng)為二維向量，第一個(gè)分量為連掛鉤權(quán)，第二個(gè)分量為溜放鉤權(quán)。j＝k－1 表示正向弧 (調(diào)車前后車組相對(duì)順序不變)且相鄰，調(diào)車時(shí)兩車組不再拆分，可作為一個(gè)車組看待，因此弧長(zhǎng)為 (0,0)；j＜k－1 表示正向弧但不相鄰，需多增加一個(gè)溜放鉤使其相鄰，因此弧長(zhǎng)為 (0,1)；j＝0 表示調(diào)車作業(yè)必定從連掛鉤開始，因此弧長(zhǎng)為 (1,0)。j＞k 表示反向弧 (調(diào)車前后車組相對(duì)順序相反) 需多增加一個(gè)連掛鉤和一個(gè)溜放鉤來(lái)調(diào)整順序并使其相鄰，因此弧長(zhǎng)為 (1,1)。

若已確定連掛鉤與溜放鉤的費(fèi)用比重，則易將弧長(zhǎng) (相應(yīng)的權(quán)) 轉(zhuǎn)化為實(shí)數(shù)。為了討論選編鉤計(jì)劃中的連掛鉤和溜放鉤數(shù)，研究保留權(quán)重為二維向量。為了便于分析和討論，特定義如下。

定義1：設(shè)一個(gè)車列 L 的車組排列為 i1,i2,…,in，G(V，E) 是根據(jù)上述方法轉(zhuǎn)化得到的有向圖，則稱 G 為車列 L 生成的有向圖。

定義2：設(shè) G 是 i1,i2,…,in生成的有向圖，ejk是G 中從點(diǎn) ij到點(diǎn) ik的一條有向弧，若 j＜k，則稱 ejk為正向弧，若 j＞k，則稱 ejk為反向弧。

2.2 最優(yōu)下落方案問題等同于最小 Hamilton 路問題

觀察由車列 L 生成的有向圖 G (V，E)，可得到以下結(jié)論。

定理1：設(shè)G (V，E) 是由原車列 L：i1，i2，…，in生成的有向圖，0，I1，I2，…，In，m＋1 是 G 的一條從 0 到 m＋1 的 Hamilton 路，則 I1，I2，…，In對(duì)應(yīng)了調(diào)車后的一個(gè)可行的車組排列順序，I1，I2，…，In中的 t 個(gè)反向弧將車列分成了 t＋1 節(jié)子車列，每個(gè)子車列的車組相對(duì)順序在 i1，i2，…，in和 I1，I2，…，In中保持相同。其證明如下。

（1）根據(jù)站順的要求，可行的車組排列順序?yàn)镮1，I2，…，In中任意的兩點(diǎn) Ij和 Ik(0＜j＜k＜n＋1)，有 Ij≤Ik。假設(shè)存在一條 Hamilton 路對(duì)應(yīng)的調(diào)車后的車組排列順序是不可行的，則必存在一條有向弧 ejk，其中ij＞ik，這與轉(zhuǎn)化條件(2)矛盾，所以Hamilton 路對(duì)應(yīng)的車組排列順序一定是可行的。

（2）由反向弧的定義可知0和 m＋1 不可能是反向弧的起點(diǎn)，可設(shè) t 個(gè)反向弧的起點(diǎn)分別是 Ij1，Ij2，…，Ijt，則車列被分成的 t＋1 個(gè)子車列為：0，…，Ij1；Ij1+1，…，Ij2；…；Ijt+1，…，m＋1。每個(gè)子車列中只包含正向弧，對(duì)任意正向弧在原車列中為 ejk( j＜k)，在編成的車列中為 ej'k'(k '＝j(luò)'＋1，j'＜k ' )，顯然相對(duì)順序保持不變。

定理 2：設(shè)G (V，E，C )是由 i1，i2，…，in生成的有向圖，0，I1，I2，…，In，m＋1 是 G 的一條從 0 到 m＋1 的 Hamilton 路，總長(zhǎng)為 (a,b)，則存在a 個(gè)連掛鉤和 b個(gè)溜放鉤的選編鉤計(jì)劃，將i1，i2，…，in調(diào)整為 I1，I2，…，In。其證明如下。

根據(jù) G (V，E，C) 的生成條件可知正向弧0→j1的弧長(zhǎng) C0j1＝(1，0)，其余正向弧長(zhǎng)為 (0,1)或 (0，0)；反向弧長(zhǎng)為 (1，1)，由此可得反向弧的個(gè)數(shù)為 a－1，其將車列分成的子車列數(shù)目為 a，弧長(zhǎng)為 (0，1) 的弧的數(shù)目為 b－a，除 (0，0) 弧外的正向弧的數(shù)目為 b－a＋1。因此，可按以下方法進(jìn)行調(diào)車。

為每一個(gè)反向弧分成的子車列分配一條線路，將待編車列所在線路分配給 i1所在子車列。

將車列遷出 (i1及其 (0，0) 弧連接的車組坐底)，將各車組溜放到相應(yīng)子車列的線路內(nèi)，其中(0，0) 弧的終點(diǎn)車組隨其起點(diǎn)車組一起溜放，這樣每個(gè)除 (0，0) 弧外的正向弧和反向弧的端點(diǎn)車組各發(fā)生1個(gè)溜放鉤，由于 i1不可能是 (0，0) 弧的端點(diǎn)車組，因此 i1由于坐底節(jié)省1個(gè)溜放鉤，此過程共發(fā)生1個(gè)連掛鉤和 b－a＋1＋(a－1)－1＝b－1個(gè)溜放鉤。

依次連掛除 j1所在子車列外的所有車組，并將其溜放到 j1所在線路即完成調(diào)車作業(yè)，此過程共發(fā)生 a－1 個(gè)連掛鉤和一個(gè)溜放鉤。

整個(gè)調(diào)車作業(yè)共發(fā)生 a 個(gè)連掛鉤和 b 個(gè)溜放鉤。需要注意的是，在線路不受限的情況下存在通過 a 個(gè)連掛鉤和 b 個(gè)溜放鉤完成調(diào)車任務(wù)，但其不一定是最優(yōu)的調(diào)車方案。

定理 3：求原始車列為 i1，i2，…，in的最優(yōu)調(diào)車后的車組排列順序等價(jià)于求有向圖 G (V，E，C)的0到 m＋1 的最小 Hamilton 路。其證明如下。

由定理1可知，每條從0到 m＋1 的 Hamilton 路對(duì)應(yīng)著一個(gè)可行的車組排列順序，由定理2可知，可以通過該 Hamilton 路長(zhǎng) (對(duì)應(yīng)的連掛鉤和溜放鉤)完成調(diào)車作業(yè)，因此有定理 3。

3 模型的轉(zhuǎn)換與求解

求一個(gè)有向圖的最小 Hamilton 路是一個(gè) NP 困難問題，當(dāng)車組數(shù)較大時(shí)，一般很難求最優(yōu)解。但是，待編車列生成的有向圖具有一定的特性，利用該特性可將求有向圖 G 的最小 Hamilton 路問題轉(zhuǎn)化為求 一個(gè)有向圖的最短路問題。

由于編組有站順要求，因此所求的 Hamilton 路具有以下特性：只有當(dāng)同一個(gè)到達(dá)站的車組節(jié)點(diǎn)全部經(jīng)過后，才能進(jìn)入下一個(gè)到達(dá)站的車組節(jié)點(diǎn)；而當(dāng)同一個(gè)到達(dá)站的車組節(jié)點(diǎn)的進(jìn)入節(jié)點(diǎn)和離開節(jié)點(diǎn)確定后，根據(jù)生成圖的弧長(zhǎng)取值可知，通過所有該到達(dá)站節(jié)點(diǎn)的最小 Hamilton 路的順序必定是第一個(gè)點(diǎn)為進(jìn)入節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)為離開節(jié)點(diǎn)，而其他節(jié)點(diǎn)的順序與在原車列中的排列相同。按照此方法即可將問題轉(zhuǎn)化為最短路問題，而最短路問題則較容易求解。

例如，某到達(dá)站的各車組在原車列的排序?yàn)椋?，3，5，7，9，若已知進(jìn)入節(jié)點(diǎn)為 7，離開節(jié)點(diǎn)為 1，則最小Hamilton 路經(jīng)過該到達(dá)站的各車組節(jié)點(diǎn)順序?yàn)椋?，3，5，9，1。即 3，5，9 的順序與原排列相對(duì)不變。經(jīng)過這些點(diǎn)的總長(zhǎng)為：(1，1)＋(0，1)＋(0，1)＋(1，1)＝(2，4)。

例如，原車組排列為 2 3 2 1 2 1 3，即第一站車組的順序?yàn)?4、6，第二站車組的順序?yàn)?1、3、5，第三站的車組的順序?yàn)?2、7。則構(gòu)造最短路圖，如圖3所示。其中，第2站只標(biāo)出兩個(gè)點(diǎn)，中間點(diǎn)未標(biāo)出。如 1→3 表示 1→5→3，其長(zhǎng)為 (0,1)＋(1,1)＝(1,2)。

為反映連掛鉤與溜放鉤的區(qū)別，使用二維向量作為路長(zhǎng)，在求最短路時(shí)需將二維向量轉(zhuǎn)化為實(shí)數(shù)進(jìn)行計(jì)算，如定義轉(zhuǎn)化向量為 (5，1)T，表示一個(gè)連掛鉤的費(fèi)用是溜放鉤的5倍，則路長(zhǎng) (2，1)→(2，1)×(5，1)T＝11。容易求得從節(jié)點(diǎn) 0 到節(jié)點(diǎn)8的最短路為 0，4，6，3，5，1，2，7，8，總路長(zhǎng)為(3,5)。調(diào)車步驟 (原車列在③線)：3＋5，2－1，1－1，2－1，1－1，3＋2，2＋2，1－5 或 3＋4，1－1，3－1，1－1，3＋2，1－2，3＋2，1－3。

4 案例分析

用圖論模型分析前述例子，原待編車列的車組排列為 1 2 1 3 4 2 3，其生成的有向圖 G (節(jié)點(diǎn)數(shù)字表示到站序號(hào)) 如圖 4 所示。

轉(zhuǎn)化所得最短路圖 (節(jié)點(diǎn)數(shù)字表示在原車列中的位置序號(hào)，粗線表示最短路徑)如圖5所示。

從站點(diǎn)0到站點(diǎn)5的最小 Hamilton 路 (節(jié)點(diǎn)數(shù)字表示到站序號(hào))如圖6所示。

路長(zhǎng)為 (1，0)＋(1，1)＋(0，0)＋(0，1)＋(0，0)＋(1，1)＋(0，0)＋(0，1)＝(3，4)。則調(diào)車后最終的子車列及車組排列順序?yàn)椋篿3；i1，i2，i6，i7；i4，i5。即相當(dāng)于原車組的排序?yàn)?2 3 1 6 7 4 5，對(duì)該車列進(jìn)行下落，調(diào)車步驟為 (原車列在②線)：2＋5，1－1，3－2，2－2，3＋2，2＋4，1－6 或 2＋5，1－1，3－2，2＋2，1－4，3＋2，1－2。如圖7所示，為3個(gè)連掛鉤和4個(gè)溜放鉤。

圖7 車組下落情況

用傳統(tǒng)的下落列方法最終的車組排列為 i1，i3，i6，i2，i4，i7，i5，對(duì)應(yīng)于所求的 Hamilton 路如圖8所示。

路長(zhǎng)為(1,0)＋(0,1)＋(0,1)＋(1,1)＋(0,1)＋(0,1)＋(1,1)＋(0,1)＝(3,7) 需3個(gè)連掛鉤和7個(gè)溜放鉤。

5 結(jié)束語(yǔ)

傳統(tǒng)的下落列方法其算法比較直觀、簡(jiǎn)單，適合手工操作，研究論述的方法雖然較為復(fù)雜，但能得到一個(gè)確定的最終車組的排列順序，即一個(gè)確定的下落方案，不存在“可調(diào)車組”的問題，從而可以簡(jiǎn)化后續(xù)鉤計(jì)劃選優(yōu)的算法。

該方法轉(zhuǎn)化為計(jì)算機(jī)程序并不困難，主要面臨3個(gè)問題：首先，將待編車列轉(zhuǎn)化為有向圖，這可以根據(jù)有關(guān)轉(zhuǎn)換規(guī)則較易得到有向圖；其次，將同站車組之間的 Hamilton 路簡(jiǎn)化，根據(jù)此 Hamilton 路的特性，也很容易計(jì)算和簡(jiǎn)化有向圖；最后，有向圖最短路問題的求解已經(jīng)是個(gè)比較成熟的問題，算法和計(jì)算機(jī)程序并不需要重新設(shè)計(jì)。因此，研究的方法看似復(fù)雜，但是轉(zhuǎn)化為計(jì)算機(jī)算法的每一步都很簡(jiǎn)單，很容易實(shí)現(xiàn)，同時(shí)又可以大大簡(jiǎn)化后續(xù)鉤計(jì)劃選優(yōu)的算法，提高程序整體的計(jì)算效率。

編制選編鉤計(jì)劃時(shí)車組的不同下落方案，其實(shí)質(zhì)反映的是調(diào)車后同到站車組的不同排列順序。通過構(gòu)建圖論模型，將求調(diào)車后車組的最優(yōu)排列順序，轉(zhuǎn)化為求一個(gè)有向圖的最小 Hamilton 路問題，并利用同一到站的車組經(jīng)過之后才能進(jìn)入下一到站這一特性，將求解最小 Hamilton 路問題轉(zhuǎn)化為求一個(gè)有向圖的最短路問題，從而得到求該問題最優(yōu)解的有效算法。

研究求得的最小 Hamilton 路的路長(zhǎng)，反映的是待編車列中車組排列的規(guī)律，并非對(duì)應(yīng)最優(yōu)選編鉤計(jì)劃中所需的最少連掛鉤數(shù)和溜放鉤數(shù)。為求得最優(yōu)的選編鉤計(jì)劃仍需對(duì)由反向弧分成的子車列進(jìn)行合并等操作。最小 Hamilton 路反映了調(diào)車作業(yè)車組位置調(diào)整的實(shí)質(zhì)，如何通過 Hamilton 路及其正向弧和反向弧的關(guān)系來(lái)求得最優(yōu)的選編鉤計(jì)劃，還有待進(jìn)一步地深入研究。

[1] 徐瑞華，張國(guó)寶，徐行方. 軌道交通系統(tǒng)行車組織[M]. 北京：中國(guó)鐵道出版社，2005.

[2] 曹書波. 調(diào)車作業(yè)計(jì)劃優(yōu)化方法研究[D]. 蘭州：蘭州交通大學(xué)，2003.

[3] 宋建業(yè). 優(yōu)化篩選摘掛列車編組調(diào)車方案的分析計(jì)算法[J].鐵道學(xué)報(bào)，1999，21(3)：11-17.

[4] 劉彥虎，周磊山，劉桐飛. 編制摘掛列車調(diào)車作業(yè)計(jì)劃的優(yōu)化計(jì)算方法[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2008，30(3)：78-81.

[5] 高四維，張殿業(yè). 一種新的調(diào)車作業(yè)原理——“消逆法”[J]. 鐵道學(xué)報(bào)，2003，25(5)：1-7.

[6] 李 緯. 摘掛列車調(diào)車計(jì)劃的算法研究及實(shí)現(xiàn)[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2007，29(3)：79-81，84.

[7] 李鳳義. 提高調(diào)車作業(yè)效率的對(duì)策[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2009，31(5)：89-90.