基于遺傳算法的應(yīng)急物資供應(yīng)點定位—分配問題研究綜述

焦琴琴

摘 要：本文總結(jié)、分析了近年來國內(nèi)研究中基于遺傳算法求解的應(yīng)急物資供應(yīng)點定位-分配相關(guān)問題的文獻(xiàn)，主要包括應(yīng)急定位問題、應(yīng)急物資分配問題、應(yīng)急定位-分配集成問題的研究綜述，最后總結(jié)得出研究現(xiàn)狀和未來研究的發(fā)展趨勢。

關(guān)鍵詞：遺傳算法；應(yīng)急物流；定位-分配問題

一、 引言

震后應(yīng)急物流是保障生命安全、減少財產(chǎn)損失的重要環(huán)節(jié)。以往的震后應(yīng)急管理實踐過程中出現(xiàn)了很多諸如應(yīng)急物資供應(yīng)點的定位不合理、應(yīng)急物資分配不公平等一系列降低應(yīng)急物流運(yùn)作效率的問題，這就對我國的應(yīng)急物流組織體系的構(gòu)建和完善提出了迫切要求，因此，研究震后應(yīng)急物資供應(yīng)點的定位-分配問題，具有十分重大的現(xiàn)實意義。而針對應(yīng)急物資供應(yīng)點定位-分配問題的研究一般都屬于NP-hard問題，往往是基于遺傳算法進(jìn)行求解的，下面分別對基于遺傳算法的應(yīng)急物資供應(yīng)點定位-分配問題包含的三個方面進(jìn)行研究綜述。

二、 基于遺傳算法的應(yīng)急物資供應(yīng)點定位-分配問題研究

（一）基于遺傳算法的應(yīng)急定位問題。劉紅娟等（2010）[1]考慮設(shè)施點間距離、流量與安全性等道路特性，將其轉(zhuǎn)換為道路的綜合權(quán)值，建立了應(yīng)急物流多設(shè)施選址模型，并采用遺傳算法求解，最后用實例對模型進(jìn)行了驗證分析。李周清等（2011）[2]考慮震后物資調(diào)度的中轉(zhuǎn)設(shè)施定位，以時間和成本最優(yōu)為目標(biāo)，建立了中轉(zhuǎn)網(wǎng)點的定位模型，并用遺傳算法求解。于鵬等（2012）[3]考慮設(shè)備應(yīng)急搶修的時限要求和整個應(yīng)急搶修系統(tǒng)的服務(wù)質(zhì)量要求，采用0-1整數(shù)規(guī)劃模型描述應(yīng)急搶修點選址定位問題，針對該問題設(shè)計了一種混合遺傳算法，并通過算例計算結(jié)果表明，該算法求得的結(jié)果要優(yōu)于基于罰函數(shù)和采用簡單修復(fù)算法的遺傳算法。張剛紅（2013）[4]考慮大規(guī)模應(yīng)急設(shè)施的選址定位成為應(yīng)急管理系統(tǒng)的關(guān)鍵，構(gòu)建應(yīng)急設(shè)施選址問題的集合覆蓋模型，提出一種改進(jìn)的并行遺傳算法，并在Hadoop平臺上編程實現(xiàn)。付德強(qiáng)等（2014）[5]研究了應(yīng)急物資儲備庫的多目標(biāo)選址決策模型，并設(shè)計了相應(yīng)的多目標(biāo)非支配排序遺傳算法。

（二）基于遺傳算法的應(yīng)急物資分配問題。重大地震災(zāi)害發(fā)生以后，對應(yīng)急物資進(jìn)行科學(xué)合理的分配是震后應(yīng)急物資保障系統(tǒng)的關(guān)鍵。

于振濤（2011）[6]研究應(yīng)急物流系統(tǒng)中多級設(shè)施和多式聯(lián)運(yùn)救災(zāi)情況下的應(yīng)急物資分配與調(diào)運(yùn)問題，建立一個具有主從遞階關(guān)系結(jié)構(gòu)的雙層優(yōu)化模型，并根據(jù)所建立的模型提出了一種改進(jìn)的遺傳算法。王增（2011）[7]考慮連續(xù)軟時間窗限制，構(gòu)建人員物資損失最小化和多點“物資消耗終點時間方差最小化”的雙目標(biāo)物資分配模型，采用遺傳算法進(jìn)行模型求解。趙明等（2012）[8]研究多供應(yīng)點、多需求點的應(yīng)急物資分配特性，構(gòu)建以開始時間最早和出救點數(shù)目最少為目標(biāo)的多目標(biāo)優(yōu)化模型，設(shè)計了遺傳算法對最優(yōu)調(diào)度方案進(jìn)行求解。王旭坪（2013）[9]針對大規(guī)模突發(fā)事件下應(yīng)急物資動態(tài)調(diào)度問題，構(gòu)建以最小化災(zāi)民損失和車輛調(diào)度費用為目標(biāo)的混合整數(shù)規(guī)劃模型，設(shè)計了遺傳算法進(jìn)行求解。李沁鮮（2013）[10]運(yùn)用遺傳算法對所建立的應(yīng)急救助物資配送車輛路徑優(yōu)化模型進(jìn)行了求解和實例驗證。

（三）基于遺傳算法的應(yīng)急定位-分配問題。定位-分配問題（Location-Allocation Problems，簡稱LAP）是根據(jù)需求點的地理分布、物資需求量，確定出某一地理范圍內(nèi)供應(yīng)點的位置、數(shù)量和與需求點的指派方案。

李周清等（2010）[11]考慮增強(qiáng)大規(guī)模區(qū)際救援物資運(yùn)作效率，建立了以運(yùn)輸成本和中轉(zhuǎn)作業(yè)變動費用總和最小化為優(yōu)化目標(biāo)的應(yīng)急物資中轉(zhuǎn)設(shè)施點的定位-配給模型，并設(shè)計了一種運(yùn)用矩陣編碼的遺傳算法。莊艷玲（2011）[12]考慮對于脆弱性高的受災(zāi)點提高覆蓋水平，對脆弱性高的路線減少其運(yùn)送物資的數(shù)量，在此基礎(chǔ)上建立多目標(biāo)優(yōu)化模型，利用多目標(biāo)的模糊處理將多目標(biāo)模型轉(zhuǎn)化成單目標(biāo)模型，并設(shè)計兩個遺傳算法進(jìn)行求解。俞武揚(yáng)（2011）[13]考慮震后應(yīng)急物資需要大規(guī)模協(xié)調(diào)配送的特性，構(gòu)建了兩級應(yīng)急物流網(wǎng)絡(luò)定位-分配模型，設(shè)計了一種基于整數(shù)編碼的遺傳算法并利用嵌入運(yùn)輸問題線性規(guī)劃子算法進(jìn)行求解。宮本東（2011）[14]考慮系統(tǒng)時間、成本和需求點受災(zāi)程度，構(gòu)建沖突性多目標(biāo)應(yīng)急CLRIP模型以解決非常規(guī)突發(fā)事件環(huán)境下物流系統(tǒng)設(shè)施選址、路線選擇和資源分配問題，并設(shè)計了多目標(biāo)遺傳模擬退火算法（GASA）對該模型進(jìn)行求解。艾云飛等（2015）[15]將應(yīng)急物資儲備庫選址定位問題和應(yīng)急需求分配問題集成考慮，基于集合覆蓋理論和引力模型，建立水上應(yīng)急物資儲備庫選址-分配優(yōu)化模型，并針對模型設(shè)計遺傳算法。

三、綜合評述

綜上可以看出，我國對于應(yīng)急救援物流的研究起步較晚，現(xiàn)有研究成果較少，但對于基于遺傳算法求解的應(yīng)急物資供應(yīng)點的定位-分配問題的研究已經(jīng)相對成熟?，F(xiàn)有研究主要總結(jié)為下面幾個方面：首先，以往的應(yīng)急物資分配問題沒有考慮到運(yùn)輸時間帶來的時間延遲，總是將時間延遲和應(yīng)急物資不同時段所帶來的一個應(yīng)急物資分配的多階段問題忽略為單一階段的救援問題；其次，現(xiàn)有研究主要是針對單一需求物資的分配問題，對于多種物資組合的物資分配問題研究是很有限的；再次，以往的震后應(yīng)急定位-分配問題一般將目標(biāo)設(shè)置為最小化期望成本、最大化期望收益、最大化期望滿意度、最小化期望響應(yīng)時間等，以期在突發(fā)事件前做好預(yù)案，使突發(fā)事件發(fā)生后能在最短時間內(nèi)達(dá)到較好應(yīng)急救援效果。

因此，現(xiàn)有研究還沒有考慮到將受災(zāi)點對應(yīng)急物資需求效用最大和以任意兩受災(zāi)點需求效用未滿足率差最小來表示的物資分配公平性最大作為優(yōu)化目標(biāo)。而對于多供應(yīng)點、多受災(zāi)點、多應(yīng)急物資種類、多目標(biāo)、多周期動態(tài)的應(yīng)急物資供應(yīng)點定位-分配問題還有待進(jìn)一步地深入研究。（作者單位：重慶工商大學(xué)商務(wù)策劃學(xué)院）

基金項目：重慶工商大學(xué)研究生“創(chuàng)新型科研項目”，項目編號：yjscxx2015-41-18，項目名稱：震后應(yīng)急物資供應(yīng)點的多目標(biāo)動態(tài)定位-分配問題研究。

參考文獻(xiàn)：

[1] 劉洪娟，羅挺，等.基于遺傳算法的應(yīng)急物流多設(shè)施選址模型研究[J].后勤工程學(xué)院學(xué)報，2010，03：46-50.

[2] 李周清，馬祖軍.基于改進(jìn)GA的救援物資中轉(zhuǎn)網(wǎng)點定位[J].計算機(jī)工程，2011，37（5）：4-6.

[3] 余鵬，雋志才.混合遺傳算法求解應(yīng)急搶修點選址問題[J].計算機(jī)應(yīng)用研究，2012，30（2）：360-363.

[4] 張剛紅.Hadoop下并行遺傳算法研究及在應(yīng)急設(shè)施選址中的應(yīng)用[J].互聯(lián)網(wǎng)天地，2013，5（8）：11-14.

[5] 付德強(qiáng)，王旭，張偉.基于 NSGA-Ⅱ的應(yīng)急儲備庫多目標(biāo)選址決策模型及算法研究[J].運(yùn)籌與管理，2014，23（4）：64-69.

[6] 于振濤.震后應(yīng)急物資分配與調(diào)運(yùn)模型及算法研究[D].西南交通大學(xué)，2011.

[7] 王增.基于連續(xù)軟時間窗限制的應(yīng)急物資分配模型[D].華中科技大學(xué)，2011.

[8] 趙明，宋曉宇.利用遺傳算法求解應(yīng)急物資調(diào)度優(yōu)化問題[J].沈陽建筑大學(xué)學(xué)報，2012，28（5）：944-948.

[9] 王旭坪，馬超，阮俊虎.運(yùn)力受限的應(yīng)急物資動態(tài)調(diào)度模型及算法[J].系統(tǒng)工程理論與實踐，2013，6：1492-1500.

[10] 李沁鮮.基于需求分析的災(zāi)害應(yīng)急物資配送問題研究[D].蘭州交通大學(xué)，2013.

[11] 李周清，馬祖軍.區(qū)際救援物資中轉(zhuǎn)運(yùn)輸網(wǎng)點的定位-配給問題研究[J].計算機(jī)應(yīng)用研究，2010，27（8）：2872-2874.

[12] 莊艷玲.考慮拓?fù)浯嗳跣缘膽?yīng)急儲備點選址與物資分配模型研究[D].東北大學(xué)，2011.

[13] 俞武揚(yáng).大規(guī)模應(yīng)急物資中轉(zhuǎn)運(yùn)輸問題研究[J].計算機(jī)工程與應(yīng)用，2011，47（17）：1-3.

[14] 宮本東.面向非常規(guī)突發(fā)事件的集成定位-路徑-分配模型與算法研究[D].東北大學(xué)，2011.

[15] 艾云飛，呂靖，張麗麗.水上應(yīng)急物資儲備庫選址-分配優(yōu)化模型[J].大連海事大學(xué)學(xué)報，2015，2：62-66.