基于floyd和遺傳算法的應(yīng)急物流LRP優(yōu)化研究

摘 要：災(zāi)難發(fā)生后應(yīng)急物資配送中的選址—路徑問題（LRP）是應(yīng)急管理系統(tǒng)中的重要組成部分，針對該問題，提出了一種以配送中心的選址及運(yùn)輸總成本最小為目標(biāo)的應(yīng)急物流LRP模型，并綜合考慮了災(zāi)后道路的通行狀態(tài)、車輛的行駛速度、受災(zāi)點(diǎn)時(shí)間窗限制等特性，針對模型的特點(diǎn)將floyd算法和遺傳算法結(jié)合，設(shè)計(jì)了一種混合啟發(fā)式算法求解該模型。最后，通過算例驗(yàn)證了模型和算法的可行性。

關(guān)鍵詞：應(yīng)急物流;選址-路徑;遺傳算法

中圖分類號(hào)：F25 文獻(xiàn)標(biāo)識(shí)碼：A doi：10.19311/j.cnki.1672-3198.2019.19.011

1 引言

過去幾十年以來，我國頻繁遭受各類災(zāi)害的侵害而付出了大量人員傷亡和財(cái)產(chǎn)損失的沉重的代價(jià)，這些災(zāi)害嚴(yán)重地威脅著人民的生命財(cái)產(chǎn)安全，對我國經(jīng)濟(jì)發(fā)展和社會(huì)穩(wěn)定產(chǎn)生了巨大的不良影響。為了盡量降低災(zāi)害對人們生命財(cái)產(chǎn)安全的損害，災(zāi)害發(fā)生后一定要竭盡所能，快速地籌備將用于救災(zāi)的應(yīng)急物資（如食品、水、帳篷、被服、醫(yī)療藥品等）并在第一時(shí)間送達(dá)受災(zāi)地區(qū)。一般情況下，應(yīng)急物資首先會(huì)從各級(jí)物資儲(chǔ)備庫集中到受災(zāi)地點(diǎn)附近的配送中心，接著由配送中心將物資分配、送到受災(zāi)點(diǎn)。而如何選擇配送中心建立的地址（location allocation problem，LAP）和怎么樣科學(xué)地規(guī)劃應(yīng)急物資配送路徑（vehicle routing problem，VRP）便成了應(yīng)急物流系統(tǒng)中非常重要的兩個(gè)研究課題。

隨著國內(nèi)外學(xué)者對物流系統(tǒng)中的LAP和VRP研究的不斷深入，不少學(xué)者發(fā)現(xiàn)這它們其實(shí)有著互相影響、互相依存的關(guān)系，如果將它們分別進(jìn)行建模和求解，會(huì)造成顧此失彼的情況，從而難以從系統(tǒng)的角度得到整體的優(yōu)化方案。因此，現(xiàn)在更多的學(xué)者開始將這兩個(gè)問題結(jié)合起來并進(jìn)行整體優(yōu)化，便產(chǎn)生了應(yīng)急物流系統(tǒng)中的選址—路徑問題（location routing problem，LRP）。在應(yīng)急物流LRP領(lǐng)域中，國內(nèi)外不少學(xué)者都對其開展了探索和研究，取得了很多開創(chuàng)性的成果。曾敏剛等將LRP問題拆分為配送中心的選址和應(yīng)急物資的配送路線兩個(gè)子問題，針對這兩個(gè)問題建立了以總成本最小化為目標(biāo)的LRP模型，并設(shè)計(jì)了一種聚類算法結(jié)合蟻群算法的方法對模型進(jìn)行了求解。劉長石等綜合考慮了受災(zāi)點(diǎn)所處的地形、物資需求量的不確定性及應(yīng)急物資配送的時(shí)間緊迫性，建立了以應(yīng)急物資送達(dá)的總時(shí)間最短兼顧成本最小的LRP模型，使用了一種混合免疫遺傳算法予以求解。陳剛等考慮了在不確定信息環(huán)境下的應(yīng)急物流選址分配問題，建立了多種類物資、多周期、多目標(biāo)的應(yīng)急物流選址分配模型，并用epsilon約束法求得此模型的帕累托最優(yōu)解集，給決策者提供了以滿足需求、總時(shí)間和總成本為目標(biāo)的3種優(yōu)化方案，而決策者可以根據(jù)其偏好來進(jìn)行選擇。李雙琳等建立了一個(gè)以應(yīng)急物資配送的總時(shí)間最小和受災(zāi)點(diǎn)需求未滿足率最低為目標(biāo)的應(yīng)急物資配送的多目標(biāo)選址—多式聯(lián)運(yùn)的模型，并設(shè)計(jì)了一種運(yùn)用二維編碼的多目標(biāo)遺傳算法予以求解。NAJAFI等將多目標(biāo)、多種交通工具、多物資類別、多周期予以綜合考慮進(jìn)行建模，該模型闡述了如何運(yùn)輸震后應(yīng)急物資和傷員的問題。Perl和Daskin將車輛的容量和設(shè)施的容量考慮進(jìn)模型中，對多車輛和多配送中心的LRP問題進(jìn)行了探討。王紹仁等綜合考慮了應(yīng)急物資配送中的緊迫性、道路的通達(dá)情況、需求不確定性，構(gòu)建了一種帶有時(shí)間窗約束的模糊LRP模型，并設(shè)計(jì)了一種改進(jìn)的遺傳算法進(jìn)行模型的求解。

已有研究大多都是從靜態(tài)的角度進(jìn)行研究，鮮有考慮道路的通行情況變化。基于上述文獻(xiàn)調(diào)研和分析，本文首先建立了一種以總成本最小為目標(biāo)并有帶時(shí)間窗約束的LRP模型，采用雙層遺傳算法結(jié)合floyd算法進(jìn)行求解，并考慮了在求得最初的應(yīng)急物資選址—路徑方案并且運(yùn)輸車隊(duì)出發(fā)后，由于次生災(zāi)害或突發(fā)情況導(dǎo)致實(shí)時(shí)路況發(fā)生變化及時(shí)快速找到更佳的路徑以保證應(yīng)急物資能夠及時(shí)送往災(zāi)區(qū)。

2 數(shù)學(xué)模型

2.1 問題描述

當(dāng)突發(fā)事件發(fā)生后，決策者迅速收集信息，確定受災(zāi)地點(diǎn)，根據(jù)災(zāi)情獲得各受災(zāi)的物資需求情況;根據(jù)地理位置、物資儲(chǔ)備情況等等方面確定備選建立配送中心的地址;通過無人機(jī)、衛(wèi)星等獲取當(dāng)前路網(wǎng)的路況信息即每條公路上車輛行駛的平均速度。決策者需要在盡可能滿足各受災(zāi)點(diǎn)時(shí)間窗要求的前提下，規(guī)劃一套以總成本最小化為目標(biāo)的選址-路徑方案，其拓?fù)鋱D如圖1所示。

式（1）表示以最小配送成本為目標(biāo)，第一項(xiàng)是配送中心的建設(shè)成本，第二項(xiàng)是總運(yùn)輸成本，第三項(xiàng)為超過運(yùn)送時(shí)間要求的懲罰函數(shù);式（2）表示建設(shè)的配送中心數(shù)量不能超過備選地址數(shù)量;式（3）表示配送中心i對需求點(diǎn)j的物資配送量xij不小于需求量Mj，且Mj大于等于0，式（4）表示配送中心的援助量不能超過其建設(shè)容量。

3 算法設(shè)計(jì)

本文對上述模型采用雙層遺傳算法結(jié)合Floyd算法進(jìn)行求解。

3.1 利用Floyd求最短時(shí)間矩陣

在確定受災(zāi)地點(diǎn)、備選配送中心地點(diǎn)的路網(wǎng)中：

以相鄰節(jié)點(diǎn)之間的實(shí)際距離和該路段當(dāng)前車輛平均行駛速度的商為元素得到相鄰兩個(gè)節(jié)點(diǎn)之間的互相通達(dá)的時(shí)間矩陣，利用Floyd算法得到各個(gè)節(jié)點(diǎn)通達(dá)的最短時(shí)間矩陣。

3.2 雙層遺傳算法

已知有n個(gè)可建設(shè)配送中心的備選地址，生成隨機(jī)種群，種群大小為X，染色體采用實(shí)數(shù)編碼，體表示為[0 1 0……1 0 1 ]，基因的位置表示備選地址的序號(hào)，1表示在該地址建設(shè)配送中心，反之為0;從上述種群中選擇一條染色體，進(jìn)行第二層遺傳算法編碼，將每個(gè)受災(zāi)點(diǎn)分配給各個(gè)配送中心（在本文中每個(gè)受災(zāi)點(diǎn)由一個(gè)配送中心負(fù)責(zé)），如第一層編碼示范所個(gè)體對應(yīng)第二層染色體編碼為[2 2 2 …… 4 6 6]，基因的位置表示受災(zāi)點(diǎn)的序號(hào)，數(shù)字“2”“4”“6”表示將該受災(zāi)點(diǎn)將由配送中心“2”“4”“6”負(fù)責(zé)配送，第二層遺傳算法同樣隨機(jī)產(chǎn)生X個(gè)體進(jìn)行遺傳操作。

（1）計(jì)算適應(yīng)度值。

根據(jù)第二層染色體表示的受災(zāi)點(diǎn)分配給配送中心的方案，讀取最短時(shí)間矩陣中的數(shù)值;再根據(jù)式（1）計(jì)算各條染色體所代表方案的總成本的倒數(shù)即適應(yīng)度值，其值越大越好。

（2）用輪盤賭的方法進(jìn)行“選擇”操作。

（3）交叉。采用單點(diǎn)交叉的方法讓兩兩染色體在交叉概率pc=0.7的條件下進(jìn)行交叉操作。

（4）變異。讓每條染色體的每一基因都以概率pm=0.001進(jìn)行變異，變異范圍由第一層染色體決定，如個(gè)體[2 2 2 2 2 2 4 4 6 6]變異只能在“2”、“4”、“6”中選擇。

（5）求出并記錄適應(yīng)度值的最大值和平均值。

（6）重復(fù)（1）（2）（3）（4）（5）步，直至算法收斂。

至此得到該選址方案下的最優(yōu)分配方案。

再將第一層算法的每條染色體都按照類似步驟（1）（2）（3）（4）（5）的遺傳操作得到全局最優(yōu)解。

3.3 動(dòng)態(tài)規(guī)劃

選取某一時(shí)刻，隨機(jī)改變路網(wǎng)的通行狀況，生成新的相鄰節(jié)點(diǎn)間的通達(dá)時(shí)間矩陣并判斷各個(gè)車隊(duì)的計(jì)劃路線未行駛部分是否還通暢，若否，則車輛以上一個(gè)道路節(jié)點(diǎn)為起點(diǎn)，重新運(yùn)行Floyd算法，得到新的最佳行駛路線。

4 算例分析

算例以計(jì)算機(jī)模擬的方式進(jìn)行，首先以整數(shù)在20-400中隨機(jī)生成30*30的對稱矩陣作為所研究的路網(wǎng)中30個(gè)節(jié)點(diǎn)的實(shí)際相鄰距離，單位為千米;在上述矩陣中隨機(jī)生成若干無窮大的數(shù)，表示這兩個(gè)點(diǎn)之間不能互相通行。接著，用上述同樣的方法生成以整數(shù)20-70中隨機(jī)生成30*30的對稱矩陣作為相鄰節(jié)點(diǎn)間通達(dá)的車輛行駛速度矩陣，單位為千米/小時(shí);最后兩個(gè)矩陣對應(yīng)元素相除得到時(shí)間矩陣，單位換算為分鐘。最終的時(shí)間矩陣數(shù)值為表如附錄A所示。

備選的建立配送中心的節(jié)點(diǎn)序號(hào)為2，3，8，14，16，19，24，27，一共8個(gè);受災(zāi)點(diǎn)設(shè)定為 1，4，5，7，10，11，13，15，17，20，22，23，25，29，30 ，一共15個(gè)。平均單位運(yùn)輸成本為10元/千米*噸。其相關(guān)參數(shù)如表1、表2所示。

其他相關(guān)參數(shù)設(shè)置如下：兩層種群的規(guī)模均為50，最大迭代次數(shù)為50次，交叉概率為0.7，變異概率為0.001。

使用Matlab2016a編程，實(shí)現(xiàn)雙層遺傳算法。

運(yùn)行結(jié)果如圖2所示。

該方案的所有需求點(diǎn)的配送均符合時(shí)間窗要求，其總成本為6323340元，其中配送中心的建設(shè)成本為312000元，運(yùn)輸成本為3203340元。

假設(shè)當(dāng)車隊(duì)出發(fā)80分鐘以后，有突發(fā)事件發(fā)生，導(dǎo)致節(jié)點(diǎn)30到節(jié)點(diǎn)1、節(jié)點(diǎn)20到節(jié)點(diǎn)15之間的道路損壞，無法通行，根據(jù)已掌握的實(shí)時(shí)路況信息，得出行駛于該路線的車隊(duì)所處的位置，將車隊(duì)標(biāo)記于與其距離最近且道路通暢的節(jié)點(diǎn)處，運(yùn)行floyd算法，得到新的路徑方案，因此上述算例中的路徑方案從24-30-1-11更改為24-30-2-11、24-20-15更改為24-20-22-15，即完成對此突發(fā)情況的規(guī)劃。

5 結(jié)束語

應(yīng)急物資的及時(shí)送達(dá)是災(zāi)害發(fā)生后減少損失重要工作。有效實(shí)現(xiàn)應(yīng)急物資供應(yīng)，對盡快搶救災(zāi)區(qū)受災(zāi)群眾，保障其生命與財(cái)產(chǎn)安全，具有重大的現(xiàn)實(shí)意義。為此，本文綜合考慮了受災(zāi)點(diǎn)的時(shí)間窗需求、配送路徑的通行情況、車輛的行駛速度等特性，在滿足受災(zāi)點(diǎn)時(shí)間窗要求的前提下，以總成本最小為目標(biāo)，構(gòu)建了一個(gè)應(yīng)急物流LRP優(yōu)化模型，并針對問題的特點(diǎn)設(shè)計(jì)了一種混合啟發(fā)式算法進(jìn)行求解。算例的結(jié)果分析表明，該模型和算法可以有效解決該類應(yīng)急物流LRP問題。后續(xù)的研究將進(jìn)一步考慮多種物資及多種運(yùn)輸方式的應(yīng)急物流LRP。

參考文獻(xiàn)

[1]代穎，馬祖軍，朱道立，方濤.震后應(yīng)急物資配送的模糊動(dòng)態(tài)定位—路徑問題[J].管理科學(xué)學(xué)報(bào)，2012，15（07）：60-70.

[2]代穎，馬祖軍.應(yīng)急物流系統(tǒng)中的隨機(jī)定位-路徑問題[J].系統(tǒng)管理學(xué)報(bào)，2012，21（02）：212-217+223.

[3]曾敏剛，崔增收，余高輝.基于應(yīng)急物流的減災(zāi)系統(tǒng)LRP研究[J].中國管理科學(xué)，2010，18（02）：75-80.

[4]劉長石，彭怡，寇綱.震后應(yīng)急物資配送的模糊定位-路徑問題研究[J].中國管理科學(xué)，2016，24（05）：111-118.

[5]陳剛，張錦，付江月.不確定環(huán)境中多目標(biāo)應(yīng)急物流選址分配模型[J].中國安全科學(xué)學(xué)報(bào)，2016，26（12）：163-168.

[6]李雙琳，馬祖軍，鄭斌，代穎.震后初期應(yīng)急物資配送的模糊多目標(biāo)選址-多式聯(lián)運(yùn)問題[J].中國管理科學(xué)，2013，21（02）：144-151.

[7]NAJAFI M，ESHGHI K，DULLAERT W.A multi-objective robust optimization model for logistics planning in the earthquake response phase [J].Transportation Research Part E：Logistics and Transportation Review，2013，49（1）：217-249.

[8]J.Perl，M.S.Daskin.A Unified Warehouse Location-Routing Methodology[J].Journal ofBusiness Logistics，1984，5（1）：92-111.

[9]J.Perl，M.S.Daskin.A Unified Warehouse Location-Routing Problem[J].TransportationResearch，1985，19（5）：381-396.

[10]王紹仁，馬祖軍.震后應(yīng)急物流系統(tǒng)中帶時(shí)間窗的模糊動(dòng)態(tài)LRP[J].運(yùn)籌與管理，2011，20（05）：63-72.