蟻群算法在鐵路乘務運用計劃編制中的應用研究

鄭金子，苗建瑞，張君平

（北京交通大學交通運輸學院，北京100044）

現階段我國鐵路現場的乘務運用計劃仍然采用手工編制方法，這種方法不僅效率很低，而且由于受到編制人員的主觀因素影響，所編制計劃的質量很難保證，因此手工編制方法勢必會成為高速發展的鐵路運輸事業的制約因素。如何運用計算機有效、合理地編制乘務運用計劃成為現階段亟待解決的問題。

1 乘務運用計劃

參照既有鐵路機車交路和乘務員工作安排辦法以及國外高速鐵路乘務組織措施，我國鐵路未來的乘務方式將以輪乘制為主，其乘務員運用計劃的手工編制過程主要分為下面幾個階段：

（1）確定乘務員基地（乘務員所屬部門，高速列車始發、終到作業的地區）及可以換乘的車站（或乘務折返地）；確定各乘務員基地的任務；給定乘務工作要執行的列車運行圖。

（2）以乘務員可能換乘的車站為分割點，將運行圖中的運行線分割成乘務區段，例如，將圖1中運行線x、y、z分割成{x1，x2}、{y1，y2}和{z1，z2，z3}等幾個區段。

圖1 運行線分割成乘務區段

（3）按照乘務員一次乘務總時間、乘務折返接續時間等乘務規則，將各乘務區段組合成不同的可行乘務交路，作為最終乘務交路備選方案。例如，圖2中B站為乘務員基地，{1，3，5，7}、{2，4，6，8}、{9，11}分別組成了3個不同的可行乘務交路，而乘務區段{1，3，5，9，11}組成的則是不可行乘務交路（一次乘務時間超過了乘務規則規定的時間），見圖2。

圖2 乘務交路

（4）根據評價標準，選擇比較優化的乘務交路，作為乘務組一次乘務工作內容。所有被選擇的乘務交路集合，必須完全覆蓋全部乘務區段，乘務交路的數量就是每日所需要的乘務組數。乘務組每一次工作就是完成一個乘務交路，在乘務中不能中斷或更換乘務組，這樣就構成可行的乘務交路計劃。由于滿足乘務規則的乘務區段的可能組合方案數量很多，即乘務交路方案數量很多，可以構成不同乘務交路計劃方案，例如，表1所示的以圖2為基礎的4個不同方案，且各方案之間存在著優劣差別，方案1明顯優于方案4；見表1。

表1 乘務員運用計劃案例

在乘務員運用計劃編制中，要檢查大量的乘務規則，需要花費大量的時間，而如何選擇能夠覆蓋所有乘務區段的乘務交路以形成最優運用計劃，是優化編制乘務員運用計劃的關鍵。

將蟻群算法引入乘務運用計劃的編制是一種開新的嘗試。把路網中的乘務區段抽象成帶有權值的點，把每站的接續時間抽象為帶有權值的邊。點和邊相連，構成了乘務工作的網絡，進而抽象成為一個類似K-TSP的問題，即在滿足工作時間的條件下，用最少的接續時間（為了提高時間的利用率，將總接續時間最短作為目標函數），遍歷網絡中所有的點。

2 建立模型

在編制乘務運用計劃時要以列車運行圖為基礎：（1）確定乘務基地和換乘點；（2）以乘務員可能的換乘站為分割點將運行線路分成若干乘務區段；（3）按照乘務規則將這些區段組合成可行的乘務交路，作為備選方案；（4）根據一定的評價標準在若干備選方案中選擇比較優化的交路作為一個乘務組的工作內容，要求所選的交路的集合必須覆蓋所有乘務區段，乘務交路的數量就是每日所需的乘務組數，這樣就構成了可行的乘務交路計劃。鐵路乘務運用計劃編制需要滿足以下約束條件：

（1）同一時間每人最多只能執行一個班次。

（2）每個班次只能由一個乘務組執行，且任務一旦開始被執行就不能中斷直至執行完畢。

（3）滿足班次銜接要求，即前一個班次的終止站應該為下一個班次的起始站。

（4）滿足人員工作時間的要求，如總乘務時間、純乘務時間和最大接續時間等要求。

本文采用人員利用率最高，即滿足約束條件下總空閑時間最少為目標構造相應的數學模型，如下所示：

在上述模型中，（1）為目標函數；約束條件（4）和（5）保證每個任務點都只被一個人執行；（6）為總乘務時間的限制；（7）為班次間隔時間約束，保證完成前面的任務才能進行下一任務。

3 算法構造

3.1 解的構造

首先根據列車運行計劃構造圖，圖中的點表示乘務區段，點的權值表示該區段的運行時間；圖中的有向邊對應著兩個區段之間的接續，邊的長度為滿足接續條件的兩個區段之間的接續時間。

在求解乘務運用計劃問題的蟻群算法中，采用k只螞蟻共同構造一個可行解，則這k只螞蟻組成一組；在該算法中，將會有m組螞蟻（即m＊k只螞蟻）共同協作尋找最優解。（1）對于第i（i=1,2,…m）組螞蟻，為該組的第1只螞蟻隨即分配一個點，這只螞蟻從該點出發按照一定的搜索規則訪問其它的點，直到不再滿足約束條件便停止搜索，將該螞蟻所訪問過的點從圖中刪除，同時為該螞蟻分配一個子周游列表（j為螞蟻編號），該表記錄了這只螞蟻訪問過的點。（2）引入另一只螞蟻遵循第1只螞蟻的行為在剩下的點中繼續搜索；直到圖中所有的點都已被刪除，第i組螞蟻的搜索行為停止。所有的子周游列表的集合,……,}（i=1,2,……,m；x為該組中螞蟻的個數）便構成了本問題的一個可行解。（3）在m組螞蟻所構成的m個可行解中根據目標函數選出最優解。

3.2 螞蟻的路徑選擇

τij(t)表示t時刻在點i, j連線上殘留的信息素。初始時刻，各條邊上的信息素相等，設τij(t=0)=C(C為一常數)，螞蟻k在運動過程中根據各條邊上的信息素大小決定轉移方向表示在t時刻螞蟻k由點i轉移到點j的概率：

其中，ηij為啟發式信息，表示螞蟻從點i轉移到點j的期望程度，本文中取ηij=1/dij（dij表示點i到點j的距離），α為在路徑ij上殘留信息的重要程度，β為啟發式信息的重要程度，集合tabuk為禁忌表，tabuk= {H1i, H2i,……,Hxi}。

3.3 信息素的更新

每一組的所有螞蟻都完成周游之后，該組中的螞蟻所經過的徑路上的信息素要根據下式進行調整：

其中， ρ表示信息素的蒸發系數，△τij為本次周游中邊ij上的信息素增加量，如果邊ij沒有被任何一只螞蟻走過則△τij取零；否則令△τij=Q/L ，其中Q為常數，L為該組所有螞蟻所經過的邊長之和。

3.4 該算法的具體步驟

（1）初始化各條邊上的信息素，令τij(t=0)＝C（C為常數）；N＝0（N為迭代次數）。

（2）給第i組的螞蟻k隨即分配一個起點a；如果滿足約束條件則繼續選擇下一點，根據轉移概率公示計算和a點滿足接續關系的所有邊的Pij，找到max(Pij)以得到a的下一點b，并將螞蟻k移動到b點；將點a和點b從圖中刪除并存儲到螞蟻k的周游列表中。

（3）如果螞蟻k找不到符合條件的點，則停止搜索并引入一只螞蟻，即k=k+1,再轉至（2）。

（4）如果tabuk中存放點的個數等于初始圖上的點數，則該組螞蟻搜索停止。

（5）記錄螞蟻個數m=k，計算所有螞蟻走過的邊長之和L和目標值Z。

（6）按照式（9）更新信息素。

（7）迭代次數N＝N+1，如果N小于預定的迭代次數W，轉至（2）。

（8）當N＝W時，所有迭代結束。求min(Z)即可得到最優解并輸出，算法結束。

3.5 算法流程圖

算法流程見圖3。

圖3 算法流程圖

4 試驗結果及分析

4.1 試驗結果

為了檢驗算法的可靠性和效率，用C++語言編寫了程序并在VC的平臺上使該算法得以實現。運用的測試數據是京廣線部分路網的數據，包括149個節點（代表乘務區段）和1 510條邊（代表乘務區段間的接續）。（測試數據和關鍵程序代碼見附錄）程序運行的界面和部分輸出結果如圖5。

圖5 部分輸出結果

4.2 結果分析

通過結果看出，該程序能夠較為合理的求解到最優解或近似最優解，相對于人工編制乘務計劃而言工作效率有了顯著的提高。然而，在程序運行過程中也發現了一些不足。程序運行效率不高，如果螞蟻組的迭代次數為100次，需要平均運算時間為12 s；如果將迭代次數改為200次，則平均需要24 s的運算時間。產生這種現象的原因有：（1）設計的算法的邏輯結構不是很合理，存在一些重復或是無效運算，這是造成算法效率低的最重要原因；（2）由于初次接觸蟻群算法，對算法中所用的參數沒有進行過深入研究，只是運用前人的經驗數值，而這些參數并不一定符合所面臨的問題特征，因此降低了算法的效率。（3）不足點就是由于編程水平有限和時間緊迫，軟件的設計過于簡單，沒有實現最初預想的在輸出界面顯示運算結果這樣一種功能，而只能是在程序運行結束后到“結果.txt”文件中去查詢，在實際運用中很不方便。以上不足都是我們在進一步的學習以及程序設計等工作中需要特別注意并及時改正的。

5 算法收斂性判定

收斂性是評定一個算法質量高低的重要指標之一，因此為了進一步提高該算法的質量，用自制的“乘務計劃編制軟件”做了大量的試驗，用來觀察在這100次迭代中總接續時間的變化情況。通過分析認為，在蟻群算法中信息素起到了非常重要的作用， 它直接決定了螞蟻在搜索路徑中的轉移概率。由公式（8）可知，每條邊上的t＋1時刻的信息素是該邊上t時刻的信息素加上本次循環中增加的信息素△t，而△t是由常數Q和螞蟻在一次循環中所走路徑長之和決定的。可見，每條邊上的初時信息素大小和常數Q的選擇是決定該算法收斂性的兩個重要因素。而初始信息素和Q二者之間又存在著一定的制約關系，因此在本次試驗中將各條邊上的初始信息素賦予一個較小的常數1，通過不斷改變Q值觀察算法的收斂效果以確定最合理的Q值。在一些相關文獻中，Q值被設為10，將取值范圍定為0到100之間的整數， 并通過大量的試驗發現當Q值為10到30之間的整數時算法的收斂效果相對更好一些，并且當Q＝20時算法的收斂性能最好。見圖6。

圖6 算法收斂曲線

6 結束語

本文探討性的研究了蟻群算法在鐵路乘務運用計劃編制中的應用問題，通過編程實現了該算法，并對算法的效率進行了測試，得到了相對理想的結果，在此基礎上還開發了計算機編制乘務計劃的小軟件。運用此軟件能夠根據具體的運營情況制定出符合實際的乘務運用方案，這對于提高鐵路乘務人員調度工作的效率、降低乘務工作的成本起到了一定的作用。

[1] 趙鵬. 高速鐵路動車組和乘務員運用的研究[D] . 北京：北方交通大學，1998.

[2] 趙鵬，胡安洲，楊浩. 機車乘務員運用計劃的優化編制. 鐵道學報，1998. 20（4）：8-11.

[3] 趙鵬，姚鳳金，張洪亮. 綜合調度仿真系統中的機車乘務調度計劃的編制[J] . 鐵道運輸與經濟，2004，27（3）：74-76.

[4] 程巖巖. 我國鐵路乘務調度計劃編制問題的研究[D] . 北京：北京交通大學，2007.

[5] 張利，劉光年，李立宏，劉征宇，張建軍. 混合蟻群算法在有容量約束車輛調度中的研究[J] . 設計與研究，2007（2）：8-11.

[6] 李獻忠，瑞華.于時問耗費的城市軌道交通乘務排班優化. 鐵道學報. 2007，29（1）：21-25.

[7] 李繼玲，盧才武，李金成. 基于蟻群算法的有時間窗車輛調度問題的研究[J] . 信息技術，2006（5）：128-131.

[8] 王芳. 蟻群算法的原理及其應用[J] . 濰坊教育學院學報.2005（2）：70-71.

[9] 黃席樾，胡小兵. 蟻群算法在K-TSP問題中的應用[J] .計算機仿真，2004，21（12）：162-164.

[10] 艾明，王魁生. 蟻群算法在TSP問題中的應用[J] . 電腦知識與技術，2006，96-129.

[11] 王世東，鄭力，張智海. 蟻群算法在調機運用計劃中的應用[J] . 中國鐵道科學，2007，28（3）：204-209.

[12] Alberto Caprara,Matteo Fischetti,Paolo Toth,Daniele Vigo,and Pier Luigi Guida.Algorithms for railway crew management[D] . Tichnical report,DEIS,University of Bologna,Italy,DMI,Univers-ity of Udine,Italy,Ferrovie dello Stato SaA,Italy,1997.

[13] Dennis Huisman.A column generation approach for the rail crew re-scheduling problem[J] . European Journal of Operational Research, 2006.