基于遺傳算法的兩階段應急物流配送中心選址研究

程元棟,閆 俊,楊齊威

(安徽理工大學 經濟與管理學院,安徽 淮南 232000)

近年來,我國地震、旱澇、公共衛生事件等各種自然災害頻頻發生,給社會發展和人民生命財產帶來了巨大損失。而應急事件具有突發性的特性,救援活動環節復雜且物資來源廣泛,因此為避免災害進一步的擴大,在災后及時制定合理有效的物流配送中心選址及配送路徑方案,具有重要理論意義和實踐價值。

目前眾多國內外科學家對應急物流選址問題做了大量研究。Hakimi S. L[1]最先對選址問題進行探討,隨后很多學者對其進行不斷的深入研究,逐漸完善成理論體系。其中郭鵬輝[2]等針對災害發生后資源受限的情況下,建立了以運輸時間最短、各個需求點的綜合滿意度最大以及滿足度差異最小為目標的應急物流選址-路徑-配給優化模型。鄭琰[3]等針對城市應急物流選址問題,建立了考慮覆蓋率、總時間成本的多目標0～1整數模型,并利用深度優先搜索法和模糊神經網絡法進行求解。以上的研究往往直接采用模型進行問題求解,卻忽略了宏觀因素對選址問題的影響,因此,部分學者采用因素評價法與算法相結合進行選址研究。其中Trivedi A、Singh A[4]提出一種綜合運用層次分析法、模糊綜合分析法和目標規劃法的一種混合算法進行物流選址設施問題的研究。姚紅云、牛凱[5]將選址與路徑問題結合研究,構建了基于模糊層次分析法的算法模型,通過案例仿真證明了模型的可靠性。倪衛紅[6]構建了考慮受災地區受災程度、地理坐標、需求量以及成本等多個目標,并采用聚類-重心法求解的應急物流配送中心選址模型。上述文獻在構建模型時,通常只對成本目標進行優化,卻未滿足應急物流中對物資時效性的要求。針對此問題,部分學者在模型中引入時間窗約束以提高整體物資配送效率。趙建有等[7]構建了時間窗、物資需求緊迫度、載重約束下考慮總運輸成本最小化的應急物流選址模型,并采用遺傳算法對模型進行求解。楊鄭[8]根據受災情況構建了需求緊迫度評價體系并以此對配送車輛時間窗進行了調整,結合遺傳算法進行算例求解,驗證了考慮需求緊迫度的車輛路徑規劃模型的正確性和有效性。

目前眾多學者在應急選址問題上已有一定基礎的研究,但使用多階段法進行研究的仍然較少。在選擇綜合因素評價法時,通常采用層次分析法、德爾菲法、模糊綜合評價法等相對較為主觀的評價方法,從而導致評價結果說服力不強;在考慮模型優化目標時,大多忽略了區域災情程度的差異化,使得應急救援方案缺少側重性和公平性[8]。鑒于此,采用兩階段法開展研究,第一個階段構建備選中心優先級評價體系,采用改進的灰色關聯分析和TOPSIS法相結合進行量化評價;第二階段考慮到各受災點不同的物資需求緊迫度,引入時間窗參數作為選址模型的影響因子,以最大限度地滿足救援時間的要求,實現精準救援,為自然災害下的物流選址問題提供新思路。

1 應急物流配送中心優先級評價體系

1.1 指標體系構建

應急物流配送中心是應急管理系統中重要的組成部分,主要負責救援物資的儲備和配送,合理科學化的選址能夠保證需求點及時接收物資并降低綜合救援成本。許多學者在研究中常忽略了選址問題還受運輸環境、道路地質、物資需求量和歷史災害風險等多種宏觀因素的影響[7]。2009年,民政部發布《救災物資儲備庫建設標準》,指出救災物資儲備庫的規劃應考慮地形、交通、地質等因素,不得選擇對地質有直接危害的地區作為庫址。同時根據已有的應急災害救援經驗和現有文獻的研究結果,將以經濟能力、物流運輸能力、醫療供給能力、應急環境四個方面構建應急物流儲備中心優先級的評價指標層[8],將其綜合應急能力進行量化評價,對選址地點進行初步篩選,具體應急物流配送中心評價指標體系模型如圖1所示。

圖1 物流配送中心優先級評價體系

具體指標選取原因為:

(1)經濟能力:主要包括地區的人均GDP指標,備選中心的經濟發展水平越高,在一定程度上其相應的物資籌備速度以及儲備中心的建設速度越快。

(2)物流運輸能力:主要包括公路總里程和公路貨物周轉量。公路總里程越大,反映地區物流建設能力越強;公路貨物周轉量是運輸業生產總成果的指標之一,一定程度反映了地區的物流規模與運輸能力。

(3)醫療供給能力:包括衛生機構數和衛生床位數,它能夠反映地區的衛生醫療水平。在災害發生后,地區醫療水平越高,應急醫療保障工作開展越快,能最大程度減少災害死傷人數。

(4)應急環境:主要指地區道路地形等級,分為平原、盆地、高原三種地形情況,其中最理想的是平坦開闊的地形環境,可提高車輛運輸物資速度。地形一般給定系數為:平原為1,盆地為0.5,高原為0.4[9]。

1.2 基于灰色關聯分析-TOPSIS法的優先級評價模型構建

將灰色關聯分析法與TOPSIS法相結合,從正負理想解和曲線相似性兩個角度對指標進行雙重評價,構造新的貼近度計算方法,確定最接近理想方案的物流備選配送中心點。具體步驟如下[10]:

(1)假設有m個受災點樣本,有n個評價指標,第i個樣本的第j個指標值用Sij表示,可構建評價優先級指標矩陣Z表示為:

Z=(Sij)m×n(i=1,2,…,m;j=1,2,…,n)

(1)

(2)為消除指標間類型和維數不同的影響,使用向量度換法標準化處理,可得到一個標準化矩陣H表示為:

H=(xij)m×n(i=1,2,…,m;j=1,2,…,n)

(2)

式(2)中,

(3)

(3)熵權法確定各個指標的權重W=(w1,w2,w3,…,wn)。

(4)

(5)

(6)

(5)計算歐式距離。

(7)

(6)計算灰色關聯系數,式(8)-式(9)中p為分辨率,在這里值取0.5。

(8)

(9)

(7)計算灰色關聯度。

(10)

(11)

(8)對歐式距離和灰色關聯度進行無綱量標準化處理。

(12)

(13)

(14)

(15)

(9)根據歐氏距離和灰色關聯度的定義,對單一評價模型進行加權合并,式(16)-(17)中λ1+λ2=1,λ表示決策者偏好程度。

(16)

(17)

(10)計算綜合評價相對貼近度Mi。這里Mi的值越大,說明物流配送中心點的綜合物流能力越高。

(18)

2 模型建立

2.1 問題描述

常規物流問題的經濟屬性較重,通常以總系統成本最小為優化目標。通常算法模型的時間窗設置為最早開始時間和最晚滿意時間,若是車輛超出規定的時間窗范圍,會相應地產生等待和懲罰成本。但是應急物流具有不確定性和時效性的特點,其首要目標是對災區的快速反應,經濟屬性相對較弱,因此將結合應急物流的特性對模型進行合理的調整。首先,依然將總選址成本最小化作為首要優化目標,但為了進一步提高救援效率,將增加時間窗約束。其次,將取消時間窗的最早開始時間和等待時間懲罰成本,只設置最晚滿意時間約束,根據受災點物資需求量和綜合災情需求緊迫指數進行災情分級,災情越嚴重的需求點災情需求緊迫指數越高對應的時間窗約束越短,以保障重災區域優先救援目標的實現[11]。

2.2 基本假設

應急物流配送中心選址是一個非確定性問題,因此為簡化問題需要作出以下假設:

(1)備選配送中心和需求點的位置已知,需求點之間距離采用歐式距離計算得出;

(2)備選配送中心的最大儲存量和需求點的物資需求量已知;

(3)物資運輸方式采用公路運輸,不考慮道路損壞程度對車輛速度的影響;

(4)每個需求點只能由一個配送中心滿足物資需求;

(5)配送中心點由足夠的車輛數目可滿足需求,所有車輛類型與速度一樣。

2.3 考慮需求緊迫度選址模型構建

根據模型描述,物流選址網絡中假設有M個備選物流配送中心,備選物流配送中心集合M={i/i=1,2,3,…,m},物資需求點有N個,需求點集合為N={j/j=1,2,3,…,n},配送中心選址總費用設定包括選址建設成本、物資儲備成本和物流配送成本。這時的物流選址問題屬于多目標優化問題,將目標函數進行整合優化后,以下為構建的考慮需求緊迫度的應急物流配送中心選址模型為:

(19)

式(19)為總目標優化函數表達式。式(19)中ci為備選物流配送中心i的固定建設成本;wij表示為備選物流配送中心i至需求點j的物資運輸量;Ri表示為備選物流配送中心i的單位儲備成本;h表示為運輸物資的單位距離成本;dij表示為備選物流配送中心i到需求點j的距離;xi表示當xi=1時,表示備選物流配送中心i被選中,當xi=0時,則表示備選點未被選中;yij表示為當yij=1時,表示物流配送中心i將為需求點j提供服務,yij=0時,則表示不提供服務。

(20)

式(20)為需求點物資響應時間計算公式,式(20)中tij表示為救援物資到達需求點j的響應時間;v表示為車輛行駛速度。

約束條件如下:

tij≤Tj,?i∈M,?j∈N

(21)

式(21)表示為各需求點的響應時間不得超過其時間約束,Tj表示為需求點j可接受的最晚響應時間約束。

(22)

式(22)表示為備選配送中心至需求點的運輸物資量等于后者的需求量,sj表示為需求點j的物資需求量。

(23)

式(23)表示為配送中心對應需求點的物資需求量之和不得超過其最大儲備量,ki表示為備選配送中心i的最大儲備量。

(24)

式(24)表示受災點有一個備選中心提供服務。

yij≤xi

(25)

式(25)表示備選配送中心只有在被選中時,才能對受災點進行物資配送服務。

(26)

式(26)表示為備選物流配送中心數量限制,p表示為備選物流配送中心i被選中的數量。

2.4 算法設計

2.4.1 算法描述

應急物流選址問題是屬于NP-hard問題。遺傳算法是一種通過模擬自然進化過程尋找最優解的啟發式算法,與其他算法相比,在求解這一類問題上具有很好的穩定性和全局搜索能力,求解算法設計過程如圖2所示。

圖2 遺傳算法運算流程圖

2.4.2 遺傳算法運算流程

(1)編碼和解碼

遺傳算法的首要過程是對染色體的編碼和解碼。二進制編碼方式與其他編碼方式相比,不僅具有廣泛性,操作簡單,并且更加符合生物進化規律,所以選擇二進制方式進行編碼。根據一定規律性,將選址的信息編碼成由若干個三位二進制組成的“染色體”,編碼的染色體長度和數量是由所要求的精確度決定的[11]。

(2)構造適應度函數

所構造的目標函數是為了使成本最小化,因此目標函數值最小的解就是最優解。由于是二進制編碼方式,因此通常會選擇線性函數作為目標函數。但是選擇不當時,就會出現局部最優解,導致無法得到整體最優解的情況[12]。式(27)表示為適應度函數表達式。

(27)

(3)遺傳算子的選取、交叉和變異

選擇算子的目的是為了篩選出適應性較好的個體,作為親代參與子代的繁衍,從而得到最優解。這里將使用輪盤賭法作為選擇算子的方法,輪盤賭選擇是根據個體適應度值與種群中所有個體適應值的比值來決定能否進入子代,從中選擇出適應度大的個體。由于部分匹配交叉會進一步提高算法的收斂速度,因此遺傳算子的交叉部分將選擇對部分匹配交叉。變異算子是模仿染色體基因突變的現象,主要通過控制變異概率達到改變個體染色體的基因鏈[13]。

3 案例仿真

3.1 配送中心優先級

案例仿真對象選取地質災害中較為典型的汶川地震。選取震中附近的10個城市作為備選應急配送中心,根據上述所建立的優先級物流配送中心評價指標體系,可對每個選址中心進行數據搜集。表1中C1為人均生產總值(元)、C2為公路總里程(km)、C3為公路貨物周轉量(萬噸公里)、C4為衛生機構數、C5為衛生機構床位數、C6為地形系數,其信息數據來源于《2008年四川省統計年鑒》。通過計算可得到各個指標的權重為C1=0.0737、C2=0.1111、C3=0.2456、C4=0.2168、C5=0.2941、C6=0.0588,其中GDP和地形系數兩個指標占比最重,其他指標占比較為接近,基本符合應急物流中對選址中心的評價要求。根據建立的優先級評價模型,可得到備選中心綜合評價排序如表2所示。德陽市和眉山市綜合指數較低,將這兩個物流配送中心點進行篩除,得到初步的物流配送中心點。

表1 物流中心點數據

表2 備選中心優先級綜合排序表

3.2 應急物流配送中心選址

在物流配送中心選址模型中,將在8個備選中心中選出6個作為最終的應急物流儲備中心,各類選址成本參數設置如表3所示。選取《汶川地震災害綜合分析與評估》[14]中綜合災情指數較高的20個城市作為物資需求點,《救災物資儲備庫建設標準》中儲備庫內倉庫堆垛高度建議為3米;我國救災物資儲備規模分類表中市級的物流配送中心建設總建筑面積要求在2900～4100m2[15];因此,將案例中各市級物流備選中心分為兩個等級,一類等級城市儲備中心建筑面積為4100m2,二類等級城市儲備中心建筑面積為3900m2,可計算出案例儲備中心體積范圍為11700～12300m3,其各個選址中心最大儲備量和固定建設成本參數如表4所示[14]。根據楊洋[15]的研究,對于特別重大突發事件通常選取常住人口的0.04作為受災群體,假設每個受災人口需要一個單位的救援物資,其中包括生活物品(0.06m3)、醫用物品(0.03m3)、防汛物品(0.04m3)、其他物品(0.05m3)組成,所以一個單位的物資體積合計為0.18m3;依據需求點的綜合災情等級設定時間窗參數,將災情指數前五名的需求點設為重災區域,其時間窗參數設置為4小時,其余的需求點時間窗設置為5小時;則各個需求點的物資需求量及時間窗參數如表5所示。從高德地圖獲取每個需求點的經緯度坐標,采用歐式距離法將經緯度坐標轉化得到兩點的距離矩陣如表6所示[16]。

表3 各類成本參數

表4 各配送中心建設成本及儲備量

表5 各需求點需求量及時間限制

表6 各需求點到各配送中心距離矩陣 km

3.3 仿真結果分析

模型求解運行環境在1.80Ghz的Intel(R)Core(TM)i5-8250U CPU、內存為4.00GB的Windows10系統的計算機中進行[17]。遺傳算法各參數設置如下:交叉概率Pc=0.8,變異概率Pm=0.05,初始化種群大小為150,最大迭代次數為200代。根據上述數據及相關參數,對模型進行求解[18]。

考慮需求點緊迫度的選址方案如表7所示,算法運行時間為7.03秒,可得到物流儲備中心為成都市、自貢市、綿陽市、遂寧市、內江市、樂山市六個城市,其中南充市和資陽市將不再考慮。圖3為算法迭代200次后的適應度進化曲線圖,從100代后算法開始收斂,可見算法尋優能力較強。具體分配方案描述如下:成都市負責綿竹市、什邡市、理縣、梓潼縣、羅江縣的物資,應儲備超過170萬個單位的物資;自貢市負責彭州市、崇州市的物資,應儲備超過145萬個單位的物資;綿陽市負責青川縣、平武縣、江油市、文縣的物資,應儲備超過156萬個單位的物資;遂寧市負責北川縣、茂縣、安縣、寧強縣、黑水縣的物資,應儲備超過86萬個單位的物資;內江市負責汶川縣、都江堰市、小金縣的物資,應儲備超過80萬的單位物資;樂山市負責劍閣縣的物資,應儲備超過67萬個單位的物資[19]。

表7 考慮需求點緊迫度的應急物流選址方案

圖3 算法迭代運行圖

在求解不考慮需求點緊迫度的選址模型時,將忽略需求點災情程度差異對選址中心的影響,將所有時間窗參數均設置為10小時。算法運行時長為7.88秒,具體分配結果如表8所示。具體分配方案描述如下:成都市負責什邡市、安縣、理縣、崇州市的物資,應儲備超過164萬個單位的物資;自貢市負責都江堰、彭州市、小金縣的物資,應儲備超過147萬個單位的物資;綿陽市負責青川縣、文縣、梓潼縣、寧強縣、劍閣縣的物資,應儲備超過157萬個單位的物資;遂寧市負責北川縣、茂縣、平武縣、黑水縣的物資供應,應儲備超過52萬個單位的物資;內江市負責汶川縣、綿竹縣的物資供應,應儲備超過62萬個單位的物資;樂山市負責江油市、羅江縣的物資,應儲備超過122萬個單位的物資。

表8 不考慮需求點緊迫度的應急物流選址方案

如表9所示,整個選址配送方案中,在被選中的物流配送中心點相同的基礎上,考慮時間窗的物流選址方案在需求點所花費的總物資配送時間相對優化了8.07%;尤其對需求緊迫度較高的汶川縣、北川縣、綿竹市、什邡市和青川縣受災點的物資等待時間相對縮短了16.65%;同時,物流配送過程中所花費的總成本相對減少了222686.80元。這表明在選址問題中增加需求緊迫度的約束,會對產生的目標函數值產生顯著影響,可有效縮短總應急物資配送時間,并確保重災區域優先得到物資保障,使得選址方案更加具有公平性和針對性,最大化程度利用有限資源,表明考慮需求緊迫度選址模型和算法更具效用性。

表9 考慮和不考慮需求急迫度選址方案對比結果

4 結論

綜合研究了應急物流的特性,指出了對備選配送中心進行優先級評價的重要性,構建了以四個因素為主的評價指標體系,運用改進的灰色關聯分析-TOPSIS法對備選配送中心的應急物流綜合能力進行評價。分析了常規物流與應急物流的目標差異化需求,構造了單邊時間窗的約束條件,并根據受災點需求緊迫度對時間窗的設定進行合理調整。構建了由固定建設成本、儲備成本和物資運輸成本組成的總成本函數下帶容量時間窗約束的選址模型,通過實際案例仿真與未考慮需求緊迫度的選址方案進行對比,其結果表明:時間窗約束下的選址方案不僅減少了總選址費用,而且在優化物資配送時間目標上具有明顯的對比效果,能有效實現了重災區域物資優先配送的目標。