王曉剛 韓印

摘要：針對救援車輛路徑選擇的多目標屬性，文章從路徑安全性、最小化行程時間、行程時間可靠性的角度出發(fā)，構(gòu)建實時環(huán)境下救援車輛的多目標實時路徑選擇模型。采用加權(quán)求和法對將多維目標聚合為單個目標，提高路徑搜索效率。模型所求得的最優(yōu)路徑為綜合最優(yōu)路徑，反映了救援車輛路徑選擇的多目標屬性，克服了以往路徑規(guī)劃單目標屬性的缺陷。給出算法，通過算例驗證模型的有效性。

關(guān)鍵詞：多目標;路徑選擇模型;加權(quán)求和法;A*算法

中圖分類號：F506文獻標識碼：A

0引言

由于物流供應(yīng)鏈的重要性，對于最短路徑問題，研究者做了大量的研究。然而，作為最短路徑分支的實時最短路徑問題研究的并不是很多。在大多數(shù)的研究中，將路網(wǎng)簡化為簡單圖，兩節(jié)點之間的路阻被認為是不變的或者是完全等同于兩節(jié)點之間的距離。然而，由于事故或交通擁堵，不同節(jié)點間的行程時間往往是不同的。所以，實時路徑規(guī)劃問題比較符合實際。Malan-drak首次提出了實時路徑規(guī)劃問題，他提出了路段行程時間的階躍函數(shù)分布，以量化實時路段行程時間。此后，一些研究者開始研究實時路徑規(guī)劃問題。如Ichoua等提出實時車速模型，符合先進先出原則并且使用禁忌啟發(fā)式搜索算法求解。Hashimoto等提出了帶軟時間窗的實時最短路徑的時間、費用模型。

由于時間資源的限制，救援團隊必須盡可能快的到達事故現(xiàn)場，所以緊急救援實時路徑選擇問題不同于一般車輛成本最小的路徑選擇，必須滿足時效性的要求。緊急救援路徑選擇問題已經(jīng)被廣泛的研究，最初的研究者Rathi等考慮時間窗約束條件下的多物資供應(yīng)線性規(guī)劃模型。陳達強等以出救車輛路徑的通行時間最小化及其對應(yīng)的通行可靠度最大化為目標，建立單出救點單需求點的緊急救援路徑優(yōu)化模型。Qzdamar等提出緊急救援路徑規(guī)劃的數(shù)學模型，他們認為實時環(huán)境下的救援物資供需關(guān)系和救援車隊規(guī)模是動態(tài)促進的關(guān)系。Ukkusuri and Yushimito在運輸網(wǎng)絡(luò)存在中斷的情況下，對設(shè)施位置和救援路徑選擇問題進行建模。Yuan and Wang針對緊急救援路徑選擇問題提出了雙層規(guī)劃模型，他們構(gòu)建的路段行程速度函數(shù)是隨著時間的增加而減少的。魏航等提出了在緊急救援的情況下建立時間隨機變化的隨機規(guī)劃模型，來進行緊急救援車輛的路徑選擇。在緊急救援物流管理中，有許多其它的研究，如Berkoune。

然而，在緊急救援實時路徑選擇中，由于交通擁堵、災(zāi)后交通基礎(chǔ)設(shè)施破壞等情況，救援路徑的可靠性沒有得到研究者的廣泛關(guān)注。Vitoriano等提出了緊急救援中物資分配的數(shù)學模型，綜合考慮了成本、時間、公平性、優(yōu)先級、可靠性和安全性的多準則優(yōu)化模型。Hamedi等考慮在時間依賴網(wǎng)絡(luò)上選擇可靠的路徑來運送救援物資，并采用組合權(quán)重法將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題。Wang等針對救援物資分配問題，將行程時間、費用、路段可靠性作為目標函數(shù)，并利用非線性整數(shù)規(guī)劃模型進行求解。Liberatore等將救援車輛歷史數(shù)據(jù)的分布轉(zhuǎn)化為路徑的安全性、可靠性。王一軍等考慮救援車輛車隊的規(guī)模，并且根據(jù)單出救點多救援點為其安排合理的路徑。

本研究基于救援車輛多目標實時路徑選擇，先對路徑所滿足的先入先出原則進行闡述。然后提出最優(yōu)路徑選擇模型，為提高路徑搜索的效率，本文采用啟發(fā)式A*算法進行模型求解。最后通過實際案例進行仿真，以驗證路徑選擇的有效性。

2案例分析

將某城市道路網(wǎng)絡(luò)簡化，利用vIssIM進行仿真，改變各目標權(quán)值，尋找最優(yōu)路徑。對65個測試路段和28個節(jié)點，車流量、速度等實驗數(shù)據(jù)以文本形式實時讀入。為驗證本模型的有效性，將多目標最短路徑選擇模型分別從路徑安全性、行程時間可靠性、行程時間等三方面與基于幾何最短路徑選擇模型進行對比。

本文以文本形式實時輸入交通量，為驗證本文緊急救援多目標實時路徑選擇模型的有效性，在相同環(huán)境下，時間權(quán)重系數(shù)以0.1為間隔進行取值，在不同的時間權(quán)重進行求解。

最終結(jié)果，隨著時間權(quán)重的增加，時間決策的比例在逐漸增大，同時路徑平均風險值、路徑行程時間可靠度決策變量的所占決策比例在組件變少，所以最優(yōu)路徑的行程時間在逐漸減少，而路徑風險值在漸漸增加，路徑的行程時間可靠度在逐步下降。而當路徑的行程時間權(quán)重大于0.7時，路徑的行程時間基本不再增加，而路徑的風險值卻隨著路徑行程時間權(quán)重的增加而不斷變大，路徑的行程時間可靠度變化不大，這種情況下，由不同的權(quán)重系數(shù)得到差別不大的優(yōu)化結(jié)果，是結(jié)果重合的現(xiàn)象，此時說明最優(yōu)路徑具有唯一性，優(yōu)化結(jié)果更加符合多目標組合優(yōu)化函數(shù)的有效性及合理性。

3結(jié)論

對于緊急救援而言，在突發(fā)事件不是特別緊急的情況下，可以適當增加路徑行程時間可靠度、路徑平均風險值的權(quán)重，以確保進行有效的救援。而發(fā)生重大突發(fā)事件的情況下，必須增加時間權(quán)重，盡可能以最短的時間進行有效的救援，避免重大的人員財產(chǎn)損失。所以基于多目標的緊急救援實時路徑選擇更加能滿足緊急救援路徑選擇的多樣性。