救援車輛多目標實時路徑規劃模型

王曉剛 韓印

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

關鍵詞：多目標;路徑選擇模型;加權求和法;A*算法

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

0引言

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

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

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

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

2案例分析

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

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

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

3結論

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