金 云，周 苗，黃仁歡，虞乾儷

（通號(hào)萬(wàn)全信號(hào)設(shè)備有限公司，杭州 310000）

工業(yè)鐵路通常由多個(gè)不同功能的站場(chǎng)組成，設(shè)置公司級(jí)調(diào)度和站級(jí)調(diào)度的兩級(jí)調(diào)度模式來(lái)對(duì)公司內(nèi)專用鐵路進(jìn)行調(diào)度指揮。分散的調(diào)度權(quán)將一個(gè)完整的生產(chǎn)作業(yè)過(guò)程分割開來(lái)，影響企業(yè)的生產(chǎn)作業(yè)效率。隨著自動(dòng)化、信息化技術(shù)的進(jìn)步，繁瑣的企業(yè)內(nèi)部鐵路運(yùn)輸可以通過(guò)技術(shù)手段整合。采用集中調(diào)度模式，只在公司級(jí)設(shè)置一級(jí)調(diào)度，同時(shí)提供調(diào)度系統(tǒng)的自動(dòng)化、智能化，減少調(diào)度人員，提高生產(chǎn)效率。

進(jìn)路搜索是工業(yè)鐵路智能調(diào)度管理系統(tǒng)的基本功能，其運(yùn)行效率以及所得目標(biāo)進(jìn)路直接關(guān)系到企業(yè)運(yùn)輸計(jì)劃的高效性和準(zhǔn)確性。本文通過(guò)對(duì)站場(chǎng)數(shù)據(jù)的組織，將站場(chǎng)圖抽象為無(wú)向帶權(quán)連通圖，建立靜態(tài)網(wǎng)絡(luò)拓?fù)鋱D，在此基礎(chǔ)上通過(guò)道岔、區(qū)段的實(shí)時(shí)狀態(tài)，動(dòng)態(tài)調(diào)整無(wú)向網(wǎng)絡(luò)拓?fù)鋱D中各個(gè)邊的權(quán)重，基于圖論中的最短路徑算法模型，完成起始無(wú)岔區(qū)段到目標(biāo)無(wú)岔區(qū)段的路徑規(guī)劃，再與系統(tǒng)中的基本進(jìn)路進(jìn)行進(jìn)路中最多元素的模糊匹配，自動(dòng)生成進(jìn)路列表，以供系統(tǒng)做自動(dòng)進(jìn)路的觸發(fā)。

1 最短路徑算法介紹

對(duì)于帶權(quán)圖G=（V,E），從圖中任意一點(diǎn)vi到圖中任意一點(diǎn)vj的邊的權(quán)值定義為路徑所包含的所有元素權(quán)值的總和，而不是邊所包含的所有元素個(gè)數(shù)的總和。最短路徑求解問(wèn)題可以分成兩個(gè)不同的子問(wèn)題，即單源最短路徑問(wèn)題和所有頂點(diǎn)對(duì)之間的最短路徑問(wèn)題。前者是找出某一頂點(diǎn)出發(fā)到圖中所有其他頂點(diǎn)的最短路徑，主要的算法有迪杰斯特拉（Dijkstra）算法、貝爾曼-福特（Bellman-ford）算法等；后者是求解圖中的每一對(duì)頂點(diǎn)之間的最短路徑，主要算法有弗洛伊德（Floyd）算法?，F(xiàn)有的使用場(chǎng)景為計(jì)算指定的兩個(gè)點(diǎn)之間的最短路徑，故首先選擇單源最短路徑問(wèn)題所對(duì)應(yīng)的算法。

Dijkstra算法是貪心算法的一種，按照路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法，無(wú)法處理帶有負(fù)權(quán)值的圖。但是該算法的穩(wěn)定性很強(qiáng)?；A(chǔ)算法時(shí)間復(fù)雜度為O(V2)，對(duì)于稀疏圖(邊的數(shù)量遠(yuǎn)小于頂點(diǎn)數(shù)的平方)，該算法的時(shí)間復(fù)雜度可以提高至O(ELgV)。Bellman-ford算法能夠處理帶有負(fù)權(quán)值的圖，但是該算法的穩(wěn)定性不如Dijkstra算法，基礎(chǔ)算法的時(shí)間復(fù)雜度為O(V×E)。其中E為圖中的邊數(shù)，V為圖中頂點(diǎn)個(gè)數(shù)。

本文所涉及的靜態(tài)網(wǎng)絡(luò)拓?fù)鋱D中邊的權(quán)值全都是非負(fù)值，而且該圖是一張稀疏圖。故選擇Dijkstra算法作為最短路徑的求解比較適合本應(yīng)用場(chǎng)景。

2 靜態(tài)拓?fù)鋱D生成

系統(tǒng)內(nèi)的道岔全都定義為單動(dòng)道岔，如果是雙動(dòng)道岔，則通過(guò)內(nèi)部邏輯的聚合，按照一個(gè)道岔數(shù)據(jù)對(duì)外提供，但是在系統(tǒng)內(nèi)都按照獨(dú)立運(yùn)算。根據(jù)道岔和無(wú)岔區(qū)段的鏈接關(guān)系數(shù)據(jù)，自動(dòng)創(chuàng)建一張無(wú)向帶權(quán)的網(wǎng)絡(luò)拓?fù)鋱D。生成的靜態(tài)網(wǎng)絡(luò)拓?fù)鋱D則由點(diǎn)的集合V(G)={vi}和邊的集合E(G)={eij(i

點(diǎn)集V(G)中的點(diǎn)ei代表站場(chǎng)圖中的第i個(gè)無(wú)岔區(qū)段。邊集E(G)中的邊eij(i

3 最短路徑生成算法

對(duì)于圖G={V(G),E(G)}，假設(shè)需要求無(wú)岔區(qū)段s到無(wú)岔區(qū)段e的最短路徑。

1）權(quán)值初始化，根據(jù)站場(chǎng)中的道岔、區(qū)段、信號(hào)機(jī)的實(shí)時(shí)狀態(tài)，動(dòng)態(tài)修改該設(shè)備所在邊的權(quán)值。例如道岔封鎖，則設(shè)置包含該道岔的邊的權(quán)值為∞，代表該邊不可達(dá)，道岔單鎖在指定位置，則設(shè)置包含該道岔相反位置的邊為不可達(dá)邊。區(qū)段占?jí)?、封鎖等，則設(shè)置該區(qū)段所在邊的權(quán)值為∞，代表該邊不可達(dá)。信號(hào)機(jī)封鎖、斷絲等，則設(shè)置該信號(hào)機(jī)的防護(hù)區(qū)段所在邊的權(quán)值為∞，代表該邊不可達(dá)。

2）設(shè)頂點(diǎn)集Vc(G)=?和邊集Ec(G)=?，從圖G中的頂點(diǎn)集V(G)中取出開始區(qū)段s所對(duì)應(yīng)的點(diǎn)vs,把vs放入頂點(diǎn)集Vc(G)中。此時(shí)Vc(G)={vs},V(G)=V(G)-Vc(G)。

3）從圖G中的邊集E(G)中取出一個(gè)臨時(shí)邊集Et(G)={eij,…|(vi∈Vc(G)&&vj∈V(G)) ||(vi∈V(G)&&vj∈Vc(G)) }，

即對(duì)于Et(G)集合中的任意邊eij，其中eij的兩個(gè)端點(diǎn)分別屬于兩個(gè)不同的頂點(diǎn)集合V(G)和Vc(G)。

如果Et(G)為空集或者Et(G)中所有邊的權(quán)值都是∞，則無(wú)法找到最短路徑，算法退出。

如果Et(G)中存在可達(dá)邊，設(shè)eij∈Et(G)為集合中權(quán)值最小的邊，則把邊eij添加到集合Ec(G)中。

4）在vj中標(biāo)記父節(jié)點(diǎn)為vi，并且把點(diǎn)vj添加到集合Vc(G)中。

如果vj就是無(wú)岔區(qū)段e所對(duì)應(yīng)的點(diǎn)，則找到該最短路徑。算法退出。

如果vj不是無(wú)岔區(qū)段e所對(duì)應(yīng)的點(diǎn)，則把Et(G)中兩個(gè)頂點(diǎn)都在Vc(G)中的邊從該集合中刪除Et(G)= {eij,…|(vi∈V(G)&&vj∈V(G)} 。把Et(G)中的剩余邊全都放回集合E(G)中。

5）重復(fù)從步驟3）開始執(zhí)行，直到頂點(diǎn)集合V(G)中不再包含任何頂點(diǎn)為止。

4 進(jìn)路轉(zhuǎn)換

按照結(jié)束頂點(diǎn)中包含的父節(jié)點(diǎn)信息以及邊中道岔的先后順序(邊的雙下標(biāo)和點(diǎn)的順序一致，則邊中的道岔按照正序輸出。邊的雙下標(biāo)和點(diǎn)的順序相反，則邊中的道岔按照逆序輸出)，把Dijkstra算法生成的路徑轉(zhuǎn)化為站場(chǎng)中的各個(gè)基本元素。由于站場(chǎng)中的基本進(jìn)路有些只包含一個(gè)道岔區(qū)段，可能會(huì)出現(xiàn)匹配到的進(jìn)路方向和規(guī)劃路徑的方向相反，故針對(duì)進(jìn)路中只有一個(gè)道岔區(qū)段的，則自動(dòng)把該道岔區(qū)段后面的元素臨時(shí)添加到該基本進(jìn)路中。對(duì)于相同始端的進(jìn)路，在進(jìn)路都覆蓋最短路徑元素的前提下，保留進(jìn)路中包含元素多的進(jìn)路作為臨時(shí)候補(bǔ)進(jìn)路，同時(shí)記錄該進(jìn)路匹配開始的元素在最短路徑元素中的位置。當(dāng)所有進(jìn)路匹配完畢后，按照記錄的起始位置進(jìn)路排序，按照進(jìn)路的開始位置和結(jié)束位置，刪除中間有交叉的進(jìn)路。當(dāng)最短路徑中的道岔元素匹配完畢，則最短路徑轉(zhuǎn)化為進(jìn)路成功。

例如按照如圖1所示，假設(shè)列車需要由4G運(yùn)行到3G。

1）按照Dijkstra算法計(jì)算出最短路徑:4G→9/19WG→3G。

2）由路徑轉(zhuǎn)化為基礎(chǔ)元素為: 4G→19→9/19WG → (19) → (21) → 27 → 3G。

3）基本進(jìn)路匹配的臨時(shí)候選進(jìn)路如表1所示(其中S4→D11，D23→S3只包含一個(gè)道岔區(qū)段，故匹配時(shí)增加一個(gè)后續(xù)連接區(qū)段)。

表1 進(jìn)路匹配Tab.1 Route matching

4）臨時(shí)候補(bǔ)進(jìn)路的匹配開始位置和匹配結(jié)束位置沒(méi)有出現(xiàn)交錯(cuò)的情況，全都轉(zhuǎn)化為候補(bǔ)進(jìn)路。如果臨時(shí)候補(bǔ)進(jìn)路的匹配位置出現(xiàn)交錯(cuò)，則把匹配開始位置大的進(jìn)路從臨時(shí)候補(bǔ)進(jìn)路中剔除掉。

5）把路徑基礎(chǔ)元素列表中的元素按照候補(bǔ)進(jìn)路中的道岔區(qū)段元素進(jìn)行比較，去除掉相同元素。進(jìn)路基礎(chǔ)元素列表變?yōu)椋?G、9/19WG，3G。

6）除去道岔區(qū)段后的路徑基礎(chǔ)元素列表中如果不包含道岔區(qū)段，則最短路徑轉(zhuǎn)化為基本進(jìn)路成功。如果包含道岔區(qū)段，那么最短路徑轉(zhuǎn)化為聯(lián)鎖進(jìn)路失敗。

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

工業(yè)鐵路運(yùn)輸調(diào)度的主要任務(wù)就是列車把貨物從一個(gè)股道拉到另一個(gè)股道，并且摻雜著一些裝車、卸車等標(biāo)準(zhǔn)作業(yè)內(nèi)容。而從一個(gè)股道到達(dá)另一個(gè)股道就需要調(diào)度員根據(jù)自己對(duì)站場(chǎng)的認(rèn)識(shí)，一步一步的人工排列聯(lián)鎖進(jìn)路來(lái)指導(dǎo)火車運(yùn)行。基于本算法的進(jìn)路動(dòng)態(tài)規(guī)劃方法，系統(tǒng)只需要輸入目標(biāo)股道信息，即可自動(dòng)計(jì)算、選擇出最優(yōu)的聯(lián)鎖進(jìn)路組合，根據(jù)列車的實(shí)時(shí)位置，自動(dòng)執(zhí)行計(jì)劃進(jìn)路，實(shí)現(xiàn)運(yùn)動(dòng)過(guò)程的自動(dòng)化。而且針對(duì)聯(lián)鎖站場(chǎng)的實(shí)時(shí)變化，自動(dòng)進(jìn)路也不一定百分之百辦理。當(dāng)出現(xiàn)進(jìn)路自動(dòng)觸發(fā)失敗的情況，系統(tǒng)可以通過(guò)列車當(dāng)前位置和目的地信息，自動(dòng)重新規(guī)劃，更新進(jìn)路表，保證列車以最優(yōu)的路線抵達(dá)目標(biāo)股道進(jìn)行標(biāo)準(zhǔn)作業(yè)。Dijkstra算法的實(shí)現(xiàn)，大大減少信號(hào)調(diào)度人員的工作量，保證調(diào)度工作的準(zhǔn)確完成，中間的全自動(dòng)過(guò)程為后期實(shí)現(xiàn)全面無(wú)人駕駛打下了堅(jiān)實(shí)的基礎(chǔ)。