焦琴琴

?

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

焦琴琴

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

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

一、 引言

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

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

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

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

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

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

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

三、綜合評(píng)述

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

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

參考文獻(xiàn)：

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

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

[3]余鵬,雋志才.混合遺傳算法求解應(yīng)急搶修點(diǎn)選址問(wèn)題[J].計(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)急儲(chǔ)備庫(kù)多目標(biāo)選址決策模型及算法研究[J].運(yùn)籌與管理,2014,23(4):64-69.

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

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

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

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

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

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

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

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

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

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

作者簡(jiǎn)介：焦琴琴(1990-)，女，漢，山西晉城人，重慶工商大學(xué)商務(wù)策劃學(xué)院，研究方向：現(xiàn)代物流與供應(yīng)鏈管理。

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