基于Dijkstra算法的鐵路應(yīng)急物資調(diào)配方案研究

王華梅，王 璞，劉興奇

（1.太原鐵路局集團(tuán)有限公司，太原 030013；2.中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司，北京 100081；3.成都鐵路局集團(tuán)有限公司，成都 610081）

隨著鐵路的高速發(fā)展，鐵路安全問題越來(lái)越受到學(xué)者的密切關(guān)注。由于鐵路應(yīng)急物資來(lái)源分散，若幾個(gè)應(yīng)急點(diǎn)同時(shí)發(fā)生事故，應(yīng)急優(yōu)先級(jí)又存在區(qū)別，鐵路應(yīng)急物資調(diào)配工作則會(huì)面臨嚴(yán)峻考驗(yàn)[1]。胡耀民，劉春年[2-3]等人在突發(fā)事件響應(yīng)過(guò)程中根據(jù)鐵路應(yīng)急物資需求，提出應(yīng)急物流快速響應(yīng)調(diào)配策略。李聰[4]等人通過(guò)使用排隊(duì)論GI/M/1模型，推導(dǎo)出應(yīng)急救災(zāi)車輛的平均等待時(shí)間和隊(duì)長(zhǎng)的表達(dá)式，為物資裝載服務(wù)臺(tái)的數(shù)量增減問題和應(yīng)急救災(zāi)車輛等決策提供依據(jù)。徐翠翠[5]分析了應(yīng)急物資管理系統(tǒng)和應(yīng)急物資管理信息系統(tǒng)的構(gòu)建及其中涉及的布局問題。曾敏剛等人[6]在可以準(zhǔn)確地獲取各需求點(diǎn)受災(zāi)數(shù)據(jù)的前提下，集成研究災(zāi)后應(yīng)急服務(wù)設(shè)施中心選址和運(yùn)輸路徑選擇問題，建立以設(shè)施點(diǎn)建設(shè)成本、運(yùn)輸成本和災(zāi)害損失成本之和最小為目標(biāo)的LRP模型。

現(xiàn)有文獻(xiàn)主要關(guān)注的是應(yīng)急物流響應(yīng)、應(yīng)急車輛調(diào)度和配送路徑等方面的問題。借助現(xiàn)有研究基礎(chǔ)，旨在從鐵路應(yīng)急物資調(diào)配環(huán)節(jié)的特殊性出發(fā)，基于Dijkstra（狄克斯特拉）算法，在從儲(chǔ)備點(diǎn)到應(yīng)急點(diǎn)的最優(yōu)路徑?jīng)Q策中，以最短時(shí)間和最小損失為根本目標(biāo)，依據(jù)應(yīng)急點(diǎn)的不同緊急程度，建立鐵路應(yīng)急物資調(diào)配方案，以其通過(guò)充分利用有限資源，提高應(yīng)急管理效率。

1 鐵路應(yīng)急物資調(diào)配方案建立

1.1 Dijkstra算法概述

最優(yōu)路徑選擇問題[7]屬于運(yùn)籌學(xué)理論的一部分，實(shí)質(zhì)是在固定起始點(diǎn)的條件下，得出兩個(gè)或多個(gè)已知點(diǎn)間的最優(yōu)路徑選擇。路徑優(yōu)劣的評(píng)價(jià)指標(biāo)可用長(zhǎng)短、時(shí)間、費(fèi)用等方式表示，基于應(yīng)急物資的特殊性，本文將選取時(shí)間作為評(píng)價(jià)指標(biāo)。由求解每項(xiàng)活動(dòng)的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間而確定最優(yōu)路徑， 若一項(xiàng)活動(dòng)的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間相同，說(shuō)明該活動(dòng)是關(guān)鍵活動(dòng)，所經(jīng)過(guò)的路徑即是所要求解的最優(yōu)路徑。假設(shè)圖G，V為圖G中的某一點(diǎn)，E為圖G中各點(diǎn)的邊。其最優(yōu)路徑的數(shù)學(xué)表示如下：

若圖G中的邊是有權(quán)的，設(shè)W(e)≥0為連接兩個(gè)點(diǎn)Pi、Pj的線u(Pi,Pj)的權(quán)值，定義W(u)為路徑u的長(zhǎng)度。路徑u(Pi,Pj)的最小值就是其最短路徑，為：

Dijkstra算法主要思路為：設(shè)G=G(V,E)是賦權(quán)有向圖，將頂點(diǎn)集合分成兩組，一組是已求出的到達(dá)源點(diǎn)的最短路徑的集合（初始只包含源點(diǎn)）稱為已優(yōu)化路徑集合，用集合S表示；另一組是還未求出的到達(dá)源點(diǎn)的最短路徑的集合，稱為未優(yōu)化路徑集合，用集合U表示。開始求取最短路徑時(shí)，目標(biāo)是從起始點(diǎn)出發(fā)到達(dá)目標(biāo)點(diǎn)的路徑上的頂點(diǎn)。計(jì)算過(guò)程中，每得到一個(gè)最短路徑就把源點(diǎn)通過(guò)該路徑連接的頂點(diǎn)加到集合S中，將集合U中的頂點(diǎn)加到集合S的過(guò)程中，應(yīng)按最短路徑長(zhǎng)度的遞增次序依次添加，并且要始終確保源點(diǎn)到集合S中任意頂點(diǎn)的距離都要≤源點(diǎn)與集合U中任意頂點(diǎn)的距離。該算法就是按照上述步驟，將集合U中的點(diǎn)全部加入到集合S中，直至集合U中沒有點(diǎn)，完成一個(gè)計(jì)算循環(huán)。值得注意的是Dijkstra（狄克斯特拉）算法只適用于W(e)≥0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí)，則算法失效。如圖1所示的賦權(quán)有向圖中，如果用Dijkstra（狄克斯特拉）算法，可得出v1到v2最短路的權(quán)是1，但這顯然是不對(duì)的，因?yàn)閺膙1到v2的最短路是（v1，v3，v2），權(quán)是 -1。

圖1 賦權(quán)有向圖

在計(jì)算從v到k的最短路徑的過(guò)程時(shí)，潘開靈等人采用以下步驟[9]：

設(shè)圖G=G(V,E,W)中有n個(gè)頂點(diǎn)，W(u)是從源點(diǎn)到每個(gè)終點(diǎn)的當(dāng)前最短路徑u的長(zhǎng)度，集合S包含所有已求出的到達(dá)v最短路徑的點(diǎn)。集合U為V-S，在起始狀態(tài)下包含除源點(diǎn)外的所有點(diǎn)。

（1）根據(jù)距離最小原則找到U中到源點(diǎn)v距離最小的一個(gè)點(diǎn)，設(shè)為k，并將k放入S中。

（2）將步驟（1）中頂點(diǎn)k作為新參照點(diǎn)，再將U中所有點(diǎn)通過(guò)k到達(dá)v的距離與不通過(guò)k到達(dá)v的距離對(duì)比，若前者小于后者，這個(gè)點(diǎn)的距離要修改為k到達(dá)v的距離和上一個(gè)頂點(diǎn)到這個(gè)k的距離之和。

（3）重復(fù)上述步驟，直到U中的所有點(diǎn)都被放入S中時(shí)結(jié)束。

本文基于Dijkstra算法，從鐵路應(yīng)急物資量和應(yīng)急物資調(diào)配時(shí)間兩個(gè)維度，建立鐵路應(yīng)急物資調(diào)配方案。

1.2 鐵路應(yīng)急物資量

鐵路應(yīng)急救援工作主要關(guān)注的問題：（1）高效開展搶險(xiǎn)救援工作；（2）全力減少各方面損失。

有序開展鐵路應(yīng)急物資的調(diào)配工作是鐵路系統(tǒng)恢復(fù)運(yùn)行的關(guān)鍵，而確定應(yīng)急物資的供需量則是開展物資調(diào)配工作的前提[8]。因此首先分析鐵路應(yīng)急物資的儲(chǔ)存量和需求量。

當(dāng)一個(gè)區(qū)域發(fā)生突發(fā)事件，需要開展應(yīng)急響應(yīng)工作時(shí)，要考慮的即為該區(qū)域內(nèi)應(yīng)急物資儲(chǔ)備點(diǎn)和突發(fā)事件應(yīng)急點(diǎn)的個(gè)數(shù)。要及時(shí)掌握每個(gè)儲(chǔ)備點(diǎn)的各類物資儲(chǔ)存量，并對(duì)每個(gè)應(yīng)急點(diǎn)的物資需求量進(jìn)行合理預(yù)推，為高效率開展應(yīng)急工作奠定基礎(chǔ)。假設(shè)：鐵路網(wǎng)絡(luò)的某一部分含有S1，S2，…，Sn，共n個(gè)物資儲(chǔ)備點(diǎn)；D1,D2,…,Dm，共m個(gè)應(yīng)急點(diǎn)，Si與Dj之間通過(guò)路徑rij連接。Si內(nèi)含有xik個(gè)Tk種類的物資，鐵路應(yīng)急指揮中心預(yù)測(cè)每個(gè)應(yīng)急點(diǎn)Dj需求物資Tk的量是yjk。本文同時(shí)考慮到儲(chǔ)備點(diǎn)儲(chǔ)存量和應(yīng)急點(diǎn)需求量?jī)蓚€(gè)要素，確定科學(xué)合理的鐵路應(yīng)急物資調(diào)配方案。

1.3 鐵路應(yīng)急物資調(diào)配時(shí)間

在任何行業(yè)或情況的應(yīng)急物資調(diào)配工作中，時(shí)間都是決策者考慮的問題，關(guān)鍵是如何迅速地將各類應(yīng)急物資調(diào)配到突發(fā)事件應(yīng)急點(diǎn)。所以，在應(yīng)急響應(yīng)工作中，需要通過(guò)確定最優(yōu)路徑來(lái)將應(yīng)急物資及時(shí)送達(dá)各應(yīng)急點(diǎn)。

1.4 鐵路應(yīng)急物資調(diào)配方案的確定

由于鐵路應(yīng)急物資有限的儲(chǔ)存量這一約束條件存在，在確定鐵路應(yīng)急物資調(diào)配方案時(shí)，要確保優(yōu)先救援優(yōu)先級(jí)較高的突發(fā)事件應(yīng)急點(diǎn)和選擇最優(yōu)配送路徑。同時(shí)，還要兼顧各類鐵路應(yīng)急物資的儲(chǔ)存量能否滿足應(yīng)急需求[9]。假設(shè)某線路發(fā)生突發(fā)事件，需要調(diào)配物資進(jìn)行搶險(xiǎn)，該區(qū)域內(nèi)有S={Si|i=1，2，…，n}共n個(gè)物資儲(chǔ)備點(diǎn)，有D={Dj|j=1，2，…，m}共m個(gè)應(yīng)急點(diǎn)，每個(gè)儲(chǔ)備點(diǎn)內(nèi)有T={Tk|k=1，2，…，q}共q種物資。

為建立應(yīng)急物資調(diào)配方案，給出以下說(shuō)明：

(1)應(yīng)急點(diǎn)j對(duì)物資h的需求量為物資可以從應(yīng)急點(diǎn)j周邊的儲(chǔ)備點(diǎn)獲得，如式（3）所示。

(3)當(dāng)儲(chǔ)備點(diǎn)i內(nèi)儲(chǔ)備的物資h無(wú)法全部滿足多個(gè)應(yīng)急點(diǎn)的需求時(shí)，首先滿足優(yōu)先級(jí)或重要度高的應(yīng)急點(diǎn)的需求，優(yōu)先級(jí)或重要度較低的應(yīng)急點(diǎn)對(duì)物資h的需求可以從配送時(shí)間較長(zhǎng)的其他鐵路應(yīng)急物資儲(chǔ)備點(diǎn)滿足。

(4)當(dāng)應(yīng)急物資需求點(diǎn)j對(duì)物資h在其最佳供應(yīng)點(diǎn)無(wú)法全部得到滿足時(shí)，剩余部分從其次優(yōu)物資儲(chǔ)備點(diǎn)進(jìn)行調(diào)配。

2 算例分析

2.1 應(yīng)急物資調(diào)配路徑

本文應(yīng)用MATLAB軟件進(jìn)行仿真求解。假設(shè)突發(fā)事件應(yīng)急點(diǎn)就近范圍內(nèi)有兩個(gè)應(yīng)急物資儲(chǔ)備點(diǎn)，分別用紅色圓圈1和2表示；在該區(qū)域中有3個(gè)應(yīng)急點(diǎn)，分別用綠色圓圈12、13和14表示。將每個(gè)儲(chǔ)備點(diǎn)和應(yīng)急點(diǎn)都放在圖中，建立一個(gè)交通網(wǎng)絡(luò)系統(tǒng)，鐵路應(yīng)急物資調(diào)配交通網(wǎng)絡(luò)圖，如圖2所示。

對(duì)圖2的儲(chǔ)備點(diǎn)和應(yīng)急點(diǎn)進(jìn)行節(jié)點(diǎn)編號(hào)，具體編號(hào)，如表1所示。

同時(shí)，結(jié)合當(dāng)?shù)氐缆沸畔⒐浪阃茰y(cè)應(yīng)急物資配送過(guò)程中通過(guò)每段路徑所需要的時(shí)間結(jié)算結(jié)果，如表2所示。

圖2 該區(qū)域鐵路交通網(wǎng)絡(luò)圖

表1 應(yīng)急點(diǎn)編號(hào)表

突發(fā)事件發(fā)生后，根據(jù)Dijkstra最優(yōu)路徑?jīng)Q策方法，可以求得各物資儲(chǔ)備點(diǎn)到各應(yīng)急點(diǎn)的最優(yōu)路徑，如表3所示。

通過(guò)表3，可以清楚的看出每個(gè)儲(chǔ)備點(diǎn)到每個(gè)應(yīng)急點(diǎn)的路徑編號(hào)，迅速的確定最優(yōu)調(diào)配路徑。

2.2 應(yīng)急物資調(diào)配方案確定

鐵路系統(tǒng)中的設(shè)備設(shè)施種類繁多，在突發(fā)事件發(fā)生時(shí)，各個(gè)應(yīng)急點(diǎn)對(duì)應(yīng)急物資的需求種類和數(shù)量也存在多樣性。在建立鐵路應(yīng)急物資調(diào)配方案時(shí)，必須考慮各類物資的需求量和供應(yīng)量，將二者結(jié)合在一起進(jìn)行綜合分析。由于不同應(yīng)急點(diǎn)緊急程度不同，在此假設(shè)應(yīng)急點(diǎn)調(diào)配物資優(yōu)先級(jí)為D2>D1>D3，即優(yōu)先配送D2，然后配送D1，D3。在突發(fā)事件發(fā)生時(shí)，鐵路局可以通過(guò)物資部門或信息系統(tǒng)獲取各儲(chǔ)備點(diǎn)的各類應(yīng)急物資儲(chǔ)備量信息，如表4所示。

表2 應(yīng)急物資運(yùn)輸時(shí)間估算表

表3 儲(chǔ)備點(diǎn)到各應(yīng)急點(diǎn)的路徑編號(hào)及所用時(shí)間

表4 儲(chǔ)備點(diǎn)的各類物資儲(chǔ)存量 單位：個(gè)

根據(jù)歷史經(jīng)驗(yàn)和現(xiàn)場(chǎng)實(shí)際情況，應(yīng)急指揮中心可以對(duì)每個(gè)應(yīng)急點(diǎn)的各類應(yīng)急物資需求量做出預(yù)估，如表5所示。

表5 應(yīng)急點(diǎn)的各類物資需求量 單位：個(gè)

根據(jù)應(yīng)急物資調(diào)配方案，對(duì)上述應(yīng)急物資進(jìn)行合理分配，最后得到一個(gè)包含應(yīng)急物資儲(chǔ)備點(diǎn)到應(yīng)急點(diǎn)間的最優(yōu)路徑、各類物資需求量和供給量及調(diào)配方案的綜合鐵路應(yīng)急物資調(diào)配方案表，如表6所示。

表6 突發(fā)事件應(yīng)急物資調(diào)配方案表

從表6中可以看出突發(fā)事件發(fā)生后各應(yīng)急點(diǎn)的各類應(yīng)急物資需求情況以及運(yùn)輸路徑選擇方案，綜合確定調(diào)配應(yīng)急物資的儲(chǔ)備點(diǎn)、選擇合理的配送路線、確定各類物資數(shù)量的供給情況，從而可以迅速開展鐵路應(yīng)急物資調(diào)配工作。

通過(guò)對(duì)鐵路應(yīng)急點(diǎn)的分析，開展一次實(shí)際的鐵路應(yīng)急物資調(diào)配方案建立工作，驗(yàn)證本文提出的調(diào)配方案。本次驗(yàn)證可得到每個(gè)應(yīng)急點(diǎn)調(diào)取需求物資的儲(chǔ)備點(diǎn)，并且確定相應(yīng)的最優(yōu)運(yùn)輸路徑方案。值得注意的是，在匹配應(yīng)急點(diǎn)和供給點(diǎn)時(shí)，要考慮供給點(diǎn)的物資儲(chǔ)備量能否完全滿足應(yīng)急點(diǎn)對(duì)各類物資的需求。

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

對(duì)于鐵路應(yīng)急物資調(diào)配問題，以最優(yōu)應(yīng)急物資配送路徑和確保優(yōu)先救援優(yōu)先級(jí)或重要度較高的應(yīng)急點(diǎn)為前提，兼顧各類應(yīng)急物資儲(chǔ)備點(diǎn)的供給能力和各應(yīng)急點(diǎn)的需求狀況，通過(guò)Dijkstra（狄克斯特拉）算法確定調(diào)配最優(yōu)路徑，從而確定整體應(yīng)急物資調(diào)配方案。本文假設(shè)物資需求可以完全得到保障，不存在供給無(wú)法滿足需求的情況。沒有充分考慮鐵路應(yīng)急儲(chǔ)備點(diǎn)物資供應(yīng)量無(wú)法滿足所有事故災(zāi)害點(diǎn)物資需求量的情況，后續(xù)研究可以考慮供應(yīng)量不足時(shí)的調(diào)配方案問題。

最后通過(guò)算例分析，表明這種算法和方案是有效的，并且對(duì)最大限度地發(fā)揮資源的效益及保證鐵路安全和社會(huì)穩(wěn)定有一定價(jià)值和意義。