救援車(chē)輛多目標(biāo)實(shí)時(shí)路徑規(guī)劃模型

王曉剛 韓印

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

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

中圖分類(lèi)號(hào)：F506文獻(xiàn)標(biāo)識(shí)碼：A

0引言

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

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

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

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

2案例分析

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

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

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

3結(jié)論

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