災后帶有時間窗的多目標選址-路徑問題

陳貴景，孟獻青，王振芳

(山西大同大學數(shù)學與統(tǒng)計學院,山西大同037009)

近年來,人為的或自然的災害在不同的地區(qū)和國家頻發(fā)，引起了巨大的人員傷亡和經(jīng)濟損失。災后及時有效并且穩(wěn)定的救援工作非常重要。應急物流管理主要包括兩個方面[1]:一是服務設施點的選址問題(FLP)，二是救援物資從供應點到需求點的車輛路徑問題(VRP)。事實上在應急物流中設施選址和車輛路徑是密切聯(lián)系的，即選址-路徑問題(LRP)。與傳統(tǒng)的運輸物流相比，應急物流中的設施選址問題和車輛路徑問題更具挑戰(zhàn)性和復雜性[2]。文獻[3]最早把設施選址問題和車輛路徑問題結合在一起，到目前為止已有豐富的研究成果[4-5]。

災后情況十分復雜，為了更接近實際的應急情況，多目標的LRP問題成為研究熱點，Rath，Gutjahr[6]研究了在災難救援中有中間配送站的選址路徑問題，為需求點提供必要的物資，目標是最小化設施固定開設成本，這里包括車輛的采集和操作成本，最大化客戶需求覆蓋率;王海軍、馬士華等[7]提出了多目標的需求可分的選址-路徑模型，優(yōu)化地震后的救濟物資分配問題，目標是最小化路徑運輸時間，最小化總成本包括分配中心的固定開設成本和車輛運輸成本，最大化路徑可靠性。?a?r? Ko?，Tolga Bekta?，Ola Jabali，Gilbert Laporte[8]研究了帶有時間窗的LRP問題，車隊是不同性質的，目標是最小化總成本且需求不可分的。

從已有的文獻可以看出，大部分學者都會把成本作為LRP問題的一個目標，事實上災后兩點間的距離和通過時間都會受到不同程度的影響都需要付出一定代價，所以距離和時間都可以理解為成本類型的目標。引入半時間窗約束，即物資到達需求點的時間不能遲于規(guī)定時間，從而提高緊急救援的時效性，另外災后各類物資大量短缺，充足的救濟物資顯得非常重要，故除了成本作為其中一個目標外，物資的滿足率作為第二個目標。突發(fā)事件發(fā)生后，運輸網(wǎng)絡一定會受到不同程度的破環(huán)和影響，為了找到更好的路徑，把路徑的運輸能力作為第三個目標。

1 問題描述

通常情況下災后的物資分布網(wǎng)絡被描述成圖G=(V,E) ，其中V是頂點集合，M={n+1,n+2,…,n+m}是候選分配中心的集合，假設M中的點沒有需求，N={1,2,…,n}是受災點集合。E={(i,j):i,j∈V,i≠j} 是有效弧集合，K={1,2,…,k}是車輛集合?？紤]以下三個目標:(1)最小化總成本，包括分布中心開設的固定成本和車輛運輸成本;(2)最大化需求點的最小物資滿足率;(3)最大化最差路徑的通過能力。其中每個弧上的通過能力用車輛通過的速度表示。

假設受災點和候選分布中心是已知的且候選分配中心的容量是足夠大的;運輸網(wǎng)絡中可用的弧和距離以及弧上車輛通常速度是已知的，比如可以通過先進的監(jiān)測技術獲得或者通過運輸研究團體獲得等;因為多種類型的救災物資以體積計算，所以不同類型的救災物資可以看成一種物資;災后物資緊缺，假設需求點的對救濟物資的需求量大于等于供應量。只考慮能通過車輛運輸救災物資的受災點，忽略需要直升機等特殊運輸手段才能服務的受災點。

m是分配中心候選點數(shù);n是受災點數(shù);k是車輛數(shù);fj?j∈M是開設分配中心j的固定成本;dij?(i,j)∈E是弧(i,j)上的距離;vij?(i,j)∈E是通過弧(i,j) 的運輸速度;是弧 (i,j)上最大的運輸速度;vk是車輛k的通常速度;Di,?i∈N是受災點i需求量;Q是運輸網(wǎng)絡中可用的救濟物資量;ck?k∈K是車輛k的單位運輸成本;Lk?k∈K車輛k的負載能力;si?i∈N受災點i的服務時間;tik?i∈N,k∈K車輛k開始服務受災點i的時間;bi?i∈N服務受災點i的最遲時間。

如果分配中心j開設xj?j∈M為1，否則是0;如果在車輛k的路徑上點i在點j的前面yijk?k∈K,(i,j)∈E是1，否則是0;如果i在車輛k的路徑上zik?k∈K,(i,j)∈E是 1，否則是 0;qik?i∈N,?k∈K是被車輛k運送到i的救災物資量;如果車輛k服務的最后一個點是受災點i，則VFik?i∈N,k∈K是1，否則是0。

2 模型

目標1最小化救濟物資配送總成本minf1。在選址-路徑問題中需要同時決定分配中心的個數(shù)和選址，給分配中心安排受災點的任務，以及相應的車輛配送路徑，所以救濟物資的分配總成本包括分配中心開設的固定成本和車輛運輸成本，

目標2希望災后救濟物資能及時有效的到達需求點，所以要考慮需求點對物資的滿足率問題，希望受災區(qū)域的救濟物資滿意度最大化且考慮到救濟物資分配公平最大化，即優(yōu)化滿足率最差的點maxf2，

目標3最大化可用路徑的通過能力。災后原有的路徑都受到或多或少的影響，此時我們考慮到路徑的通過能力，希望最大化通過能力最差的可用路徑，這里每個可用弧上(i,j)∈E的通過能力用車輛通過的速度vij來表示，則每條路徑的通過能力為每條弧上的速度和。車輛的速度在區(qū)間(0,]上隨機產(chǎn)生。則第三個目標為maxf3，

約束條件:

約束(4)(5)是時間窗約束，這里M是一個較大的正數(shù)，只要求不遲于某個給定的時間。約束(6)說明從分配中心配送到受災地點的救濟物資的總量不能超過相應物資的可用總量。約束(7)保證被車輛k運送到受災區(qū)的所有救濟物資的體積不能超過車輛的負載能力。約束(8)～(9)保證決策變量是0～1變量和非負變量。

車輛路徑中為了避免子回路有相應的子回路消除約束，這里采用Dror等[9]在1994年提出的約束。設di為點i的出次:。約束中k表示車輛的數(shù)量，

3 模型的求解

很多實際問題都需要同時優(yōu)化多個目標，有時這些目標經(jīng)常相互競爭或者相互矛盾，為此介紹帕累托最優(yōu)解的概念。

(1)帕累托占優(yōu)，考慮所有的目標，如果解x1至少與x2相等，且至少有一個目標值比x2好，則稱解x1占優(yōu)解x2，記為x1＞x2。通常情況下對于極小化問題(f1,f2,…,fw)，如果則x1＞x2。

(2)帕累托最優(yōu)解，x1是帕累托最優(yōu)解(或非劣解)當且僅當沒有任何解x2滿足x2＞x1。

(3)帕累托前沿，如果x1是帕累托最優(yōu)解(非劣解)，則f(x1)={f1(x1),…,fw(x1)}稱為非劣向量。所有非劣向量的集合稱為帕累托前沿或成為非劣前沿。

對于多目標的優(yōu)化問題常見的解決方法見[10-13]。引用遺傳算法用文獻[13]來解決提出的帶有半時間窗的多目標路徑選址問題。下面介紹具體過程:

①初始種群。

根據(jù)該LRP問題的特點，假設每個染色體有三個子串

其中g=1,2,...,NP，NP是種群里染色體數(shù)，t是種群的代數(shù)，初始種群t=0，子串是車輛的排列，子串是從m個分布中心中任意選出k個的排列，子串是n個需求點的排列。那么可以看出和在一起就是一個車輛分配決策，中的第一個基因代表的車輛是停在中的第一個基因代表的分布中心，以此類推。和共同決定了在車輛路徑中的物資供應量。每一個都可以計算出相應的目標函數(shù)值。具體見文獻[7]。在運輸過程中根據(jù)點與點之間的距離以及不同車輛的速度計算運輸時間(忽略分布中心的分配時間)加該點的服務時間如果大于等于bi，對該路徑的運輸能力進行懲罰，即運輸能力更新為:bi(運輸能力)/(運輸時間+服務時間)。

② 變異過程。

③交叉過程。

④選擇過程。

采用加權的方法進行排序，隨機選取λ1∈(0.1,0.3],λ3∈[0.3,0.5)。因為滿足率小于1，與總成本和總路徑速度相加時容易丟失，故隨機選取λ'∈[500,1000]，然后設λ2=λ'×N。

(5)遺傳算法的具體步驟。

S1隨機產(chǎn)生規(guī)模為NP的初始種群X0；

S2通過變異過程得到變異種群Vt，通過交叉過程得到實驗種群Ut；

S3混合Xt和Ut得到規(guī)模為2NP的種群Rt；

S4計算Rt中每個染色體的目標函數(shù)值；

S5確定λ1,λ2,λ3的得到F=λ1(-f1)+λ2f2+λ3f3，并進行排序；

S6選取前NP個做為下次迭代的種群。直到T大于規(guī)定的最大迭代次數(shù)。

4 算例

參數(shù)設置:NP=5×(m+n)，變異概率pm=0.7，交叉概率pc=0.7。候選分配中心個數(shù)m和受災點個數(shù)n的組合是

每個點的坐標在平面上隨機產(chǎn)生，且假設從i點到j點的距離和從j點到i點的距離相等。分配中心的固定開設成本(元)在(0，3000]內(nèi)隨機產(chǎn)生。受災點的需求量在區(qū)間(0，80]上隨機產(chǎn)生(m3)。各弧上大、中、小型車輛的通過速度分別在區(qū)間[20,80]上隨機產(chǎn)生,不同個數(shù)的受災點需要大中小型車輛個數(shù)見表1。假設災難發(fā)生的時刻是零時刻,則每個需求點被服務的最遲時間(小時)是在(0,100]內(nèi)隨機產(chǎn)生。表2給出有關車輛的參數(shù),表3是計算結果,圖1(3～10)例子的近似帕累托前沿。

表1 所需車輛數(shù)

表2 車輛的參數(shù)

表3 計算結果

圖1 用遺傳算法得到的近似帕累托前沿(3～10)

5 結論與展望

提出一個帶有半時間窗的多目標非線性選址-路徑模型,即物資到達需求點的時間不能遲于規(guī)定時間來提高緊急救援的時效性,其中受災點可以被訪問多次即需求可分的,另外災后各類物資大量短缺,充足的救濟物資顯得非常重要,故除了成本作為其中一個目標外把物資的滿足率作為第二個目標。突發(fā)事件發(fā)生后,運輸網(wǎng)路一定會受到不同程度的破環(huán)和影響,為了找到更好的路徑,把路徑的運輸能力作為第三個目標。最后采用加權排序的遺傳算法解決隨機產(chǎn)生的若干算例。多次運行結果顯示,對于本文的問題加權排序的遺傳算法表現(xiàn)穩(wěn)定有效。

災后的情況非常復雜,具有高度的不確定性比如需求、運輸時間、路徑通過速度等,因此模型中加入隨機優(yōu)化或者魯棒優(yōu)化的方法是未來研究的一個方向。另外解決該問題的方法還可以嘗試模擬退火或者非劣排序的遺傳算法等。