蟻群算法在鐵路乘務(wù)運(yùn)用計劃編制中的應(yīng)用研究

鄭金子，苗建瑞，張君平

（北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044）

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

1 乘務(wù)運(yùn)用計劃

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

（1）確定乘務(wù)員基地（乘務(wù)員所屬部門，高速列車始發(fā)、終到作業(yè)的地區(qū)）及可以換乘的車站（或乘務(wù)折返地）；確定各乘務(wù)員基地的任務(wù)；給定乘務(wù)工作要執(zhí)行的列車運(yùn)行圖。

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

圖1 運(yùn)行線分割成乘務(wù)區(qū)段

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

圖2 乘務(wù)交路

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

表1 乘務(wù)員運(yùn)用計劃案例

在乘務(wù)員運(yùn)用計劃編制中，要檢查大量的乘務(wù)規(guī)則，需要花費(fèi)大量的時間，而如何選擇能夠覆蓋所有乘務(wù)區(qū)段的乘務(wù)交路以形成最優(yōu)運(yùn)用計劃，是優(yōu)化編制乘務(wù)員運(yùn)用計劃的關(guān)鍵。

將蟻群算法引入乘務(wù)運(yùn)用計劃的編制是一種開新的嘗試。把路網(wǎng)中的乘務(wù)區(qū)段抽象成帶有權(quán)值的點(diǎn)，把每站的接續(xù)時間抽象為帶有權(quán)值的邊。點(diǎn)和邊相連，構(gòu)成了乘務(wù)工作的網(wǎng)絡(luò)，進(jìn)而抽象成為一個類似K-TSP的問題，即在滿足工作時間的條件下，用最少的接續(xù)時間（為了提高時間的利用率，將總接續(xù)時間最短作為目標(biāo)函數(shù)），遍歷網(wǎng)絡(luò)中所有的點(diǎn)。

2 建立模型

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

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

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

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

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

本文采用人員利用率最高，即滿足約束條件下總空閑時間最少為目標(biāo)構(gòu)造相應(yīng)的數(shù)學(xué)模型，如下所示：

在上述模型中，（1）為目標(biāo)函數(shù)；約束條件（4）和（5）保證每個任務(wù)點(diǎn)都只被一個人執(zhí)行；（6）為總乘務(wù)時間的限制；（7）為班次間隔時間約束，保證完成前面的任務(wù)才能進(jìn)行下一任務(wù)。

3 算法構(gòu)造

3.1 解的構(gòu)造

首先根據(jù)列車運(yùn)行計劃構(gòu)造圖，圖中的點(diǎn)表示乘務(wù)區(qū)段，點(diǎn)的權(quán)值表示該區(qū)段的運(yùn)行時間；圖中的有向邊對應(yīng)著兩個區(qū)段之間的接續(xù)，邊的長度為滿足接續(xù)條件的兩個區(qū)段之間的接續(xù)時間。

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

3.2 螞蟻的路徑選擇

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

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

3.3 信息素的更新

每一組的所有螞蟻都完成周游之后，該組中的螞蟻所經(jīng)過的徑路上的信息素要根據(jù)下式進(jìn)行調(diào)整：

其中， ρ表示信息素的蒸發(fā)系數(shù)，△τij為本次周游中邊ij上的信息素增加量，如果邊ij沒有被任何一只螞蟻?zhàn)哌^則△τij取零；否則令△τij=Q/L ，其中Q為常數(shù)，L為該組所有螞蟻所經(jīng)過的邊長之和。

3.4 該算法的具體步驟

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

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

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

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

（5）記錄螞蟻個數(shù)m=k，計算所有螞蟻?zhàn)哌^的邊長之和L和目標(biāo)值Z。

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

（7）迭代次數(shù)N＝N+1，如果N小于預(yù)定的迭代次數(shù)W，轉(zhuǎn)至（2）。

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

3.5 算法流程圖

算法流程見圖3。

圖3 算法流程圖

4 試驗結(jié)果及分析

4.1 試驗結(jié)果

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

圖5 部分輸出結(jié)果

4.2 結(jié)果分析

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

5 算法收斂性判定

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

圖6 算法收斂曲線

6 結(jié)束語

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

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

[2] 趙鵬，胡安洲，楊浩. 機(jī)車乘務(wù)員運(yùn)用計劃的優(yōu)化編制. 鐵道學(xué)報，1998. 20（4）：8-11.

[3] 趙鵬，姚鳳金，張洪亮. 綜合調(diào)度仿真系統(tǒng)中的機(jī)車乘務(wù)調(diào)度計劃的編制[J] . 鐵道運(yùn)輸與經(jīng)濟(jì)，2004，27（3）：74-76.

[4] 程巖巖. 我國鐵路乘務(wù)調(diào)度計劃編制問題的研究[D] . 北京：北京交通大學(xué)，2007.

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

[6] 李獻(xiàn)忠，瑞華.于時問耗費(fèi)的城市軌道交通乘務(wù)排班優(yōu)化. 鐵道學(xué)報. 2007，29（1）：21-25.

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

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

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

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

[11] 王世東，鄭力，張智海. 蟻群算法在調(diào)機(jī)運(yùn)用計劃中的應(yīng)用[J] . 中國鐵道科學(xué)，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.