應(yīng)急物流系統(tǒng)LRP的雙層規(guī)劃模型及算法

樓振凱

(北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院，北京 100081)

應(yīng)急物流系統(tǒng)LRP的雙層規(guī)劃模型及算法

樓振凱

(北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院，北京 100081)

針對洪澇、地震等自然災(zāi)害發(fā)生后的應(yīng)急物流配送系統(tǒng)優(yōu)化問題，考慮到政府和企業(yè)共同參與、分散決策的特點(diǎn)，建立了一個設(shè)施定位-運(yùn)輸路線問題(LRP)的雙層規(guī)劃模型，以應(yīng)急物流系統(tǒng)消耗總時間最少為上層目標(biāo)，以配送成本和時間懲罰成本之和最小為下層目標(biāo)。根據(jù)該模型上下層獨(dú)立決策而又相互影響的特點(diǎn)，設(shè)計(jì)了一種帶啟發(fā)式規(guī)則的兩階段混合模擬退火算法，一階段禁忌搜索確定可行應(yīng)急配送中心集合，貪婪就近原則構(gòu)建初始解，交換編碼搜索鄰域可行解，記錄并更新過程最優(yōu)解，累加裝卸和行駛時間并隨最優(yōu)解輸出作為上層決策的依據(jù)。最后給出算例和對比算法，驗(yàn)證了模型的有效性和算法的可行性。

應(yīng)急物流；設(shè)施定位-運(yùn)輸路線；雙層規(guī)劃；禁忌搜索；模擬退火算法

1 引言

我國是世界上受自然災(zāi)害最為嚴(yán)重的國家之一，各類重大自然災(zāi)害如洪澇、地震等時有發(fā)生，受災(zāi)規(guī)模動輒上萬人，給人民生活造成重大影響的同時，也給災(zāi)后應(yīng)急物資的有效配送提出了難題。近年來，應(yīng)急物流已經(jīng)形成政府高度重視，企業(yè)積極參與的特點(diǎn)，給設(shè)施定位-路線安排問題提供了新的解決思路。

應(yīng)急物流系統(tǒng)的優(yōu)化問題是近年來研究熱點(diǎn)之一，主要的研究內(nèi)容有集散中心和配送中心選址問題、物資配送問題、系統(tǒng)魯棒性問題等，每一類問題中又包含若干小問題。Jia Hongzhong等[1]對大規(guī)模突發(fā)事件醫(yī)療用品供應(yīng)的最大覆蓋選址問題進(jìn)行了研究，考慮到需求的不確定性和醫(yī)療用品供應(yīng)不足等因素，給出了結(jié)合拉格朗日松弛和遺傳算法的啟發(fā)式方法。劉波等[3]研究了需求和路網(wǎng)不確定下的應(yīng)急物流系統(tǒng)優(yōu)化問題，采用協(xié)同配送的方式建立了魯棒雙層規(guī)劃模型，通過分散決策將不確定性系數(shù)轉(zhuǎn)化為確定性，并提出混合遺傳算法解決該類模型。Alem等[4]對位置和需求信息模糊的應(yīng)急物流配送問題進(jìn)行了研究，構(gòu)建了基于風(fēng)險偏好值的兩階段隨機(jī)規(guī)劃模型，考慮時效性并結(jié)合實(shí)際案例給出了有效的解決方案。

不少學(xué)者對災(zāi)后應(yīng)急物流系統(tǒng)的設(shè)施定位-運(yùn)輸路線問題進(jìn)行了深入研究，王紹仁等[5]考慮了應(yīng)急物流的動態(tài)性、需求不確定性、道路連通性等因素，將不確定因素表達(dá)為一定置信水平模糊約束，建立了以物流總成本為目標(biāo)函數(shù)的LRP模型，在算法設(shè)計(jì)中用動態(tài)規(guī)劃將多周期轉(zhuǎn)換成單周期模型，運(yùn)用改進(jìn)遺傳算法求解模型。文中提出的大需求點(diǎn)分割策略很有實(shí)際意義，但是以概率方式處理需求長期來看可能效果較好，而應(yīng)急物流配送往往是短期行為。劉長石等[6]借鑒了王紹紅和馬祖軍[5]的大需求點(diǎn)分割處理方式和模糊需求的概率選擇，以總配送時間最短和總配送成本最小為目標(biāo)構(gòu)建多目標(biāo)優(yōu)化模型，并給出免疫遺傳算法。然而文中對多目標(biāo)的處理不合理，并未對時間和成本之間的重要性進(jìn)行比較，僅對比了仿真結(jié)果中幾組非劣解。對帶模糊參數(shù)的選址-路徑問題，張曉楠等[8]給出了另一種建模及求解思路，即預(yù)優(yōu)化-實(shí)時調(diào)整的兩階段策略，并以配送成本和時間懲罰成本為目標(biāo)函數(shù)建立隨機(jī)規(guī)劃模型。王紹仁等[9]在確定性需求下以系統(tǒng)響應(yīng)總時間為目標(biāo)對應(yīng)急物流LRP問題進(jìn)行了分析，給出“三角”啟發(fā)式算法，具有一定借鑒意義，但算法的適用范圍較小，且收斂性有待證明。

應(yīng)急物流是由政府和企業(yè)多方參與的物流活動，僅僅考慮一方的決策目標(biāo)顯然比較片面。鄭斌等[14]考慮在需求不確定的前提下，以應(yīng)急物資送達(dá)時間最短為上層目標(biāo)，物資分配公平性最大為下層目標(biāo)對配送系統(tǒng)建立雙層規(guī)劃模型，并給出兩階段遺傳算法，即上層給出配送任務(wù)的同時下層求出車輛的配送路徑。和其他雙層規(guī)劃算法類似，該算法在上下層規(guī)模較大的情況下收斂速度慢，且對需求以期望的方式處理，并不能滿足特定救援點(diǎn)的需求。Zhang Xiang等[16]、黃正海等[18]分別對雙層規(guī)劃模型分散決策和相互影響的特點(diǎn)，以及不同模型適用的算法進(jìn)行了較有借鑒意義的研究。

綜上所述，研究應(yīng)急物流系統(tǒng)的文獻(xiàn)中，一部分以物流網(wǎng)絡(luò)成本最低、系統(tǒng)耗時最少等為目標(biāo)建立單目標(biāo)模型[5,9]，另一部分雖然考慮多目標(biāo)，如耗費(fèi)時間和配送成本、配送時間和分配公平性等[6,14]，但并未從不同決策者的角度出發(fā)。在政府和企業(yè)共同參與的背景下，政府考慮應(yīng)急系統(tǒng)耗費(fèi)總時間最少，企業(yè)希望系統(tǒng)總成本最小。為此，本文在考慮應(yīng)急物流時效性特點(diǎn)的基礎(chǔ)上，結(jié)合道路連通狀況，在滿足各救援點(diǎn)需求的前提下，構(gòu)建以系統(tǒng)總響應(yīng)時間最短為上層目標(biāo)、以配送成本和時間懲罰成本最小為下層目標(biāo)的雙層規(guī)劃模型，分析雙層規(guī)劃模型上層決策受下層執(zhí)行的影響，考慮需求量和各配送中心容量限制，采用隱枚舉法求得可行配送中心集合，并以啟發(fā)式插值法求得可行初始解，設(shè)計(jì)帶累加記憶的模擬退火算法，以交換編碼搜索領(lǐng)域可行解的方式尋找下層最優(yōu)解，同時累加所得每條配送路線的總時間作為上層規(guī)劃的目標(biāo)值。

2 問題描述

自然災(zāi)害發(fā)生后，為了便于救援，需要從災(zāi)區(qū)周邊選擇幾個合適的配送中心，救援物資先到達(dá)配送中心，然后進(jìn)行集配，根據(jù)各救援點(diǎn)需求量的不同，對其進(jìn)行配送。對需求量大、體積較大的應(yīng)急物資如棉被、糧食、飲用水等，常采用直接配送的方式進(jìn)行；對另一些緊急需求但體積較小的物資如照明設(shè)備、食鹽、藥品等，則采用巡回配送的方式。

本文作如下假設(shè)：

(1)考慮某些需求緊急但體積較小物資的巡回配送；

(2)應(yīng)急物資足夠，且車輛數(shù)足夠；

(3)應(yīng)急配送中心到救援點(diǎn)以及救援點(diǎn)兩兩之間均存在可行路徑；

(4)各救援點(diǎn)的需求必須得到滿足，且只能由一輛車配送；

(5)各救援點(diǎn)都有兩個時間點(diǎn)，即期待在此之前被配送的時間點(diǎn)和最晚被配送的時間點(diǎn)；

(6)配送車輛從某配送中心出發(fā)，配送完后必須回到該配送中心。

3 模型構(gòu)建

3.1 符號說明

D= {p|p=1,2,…,P}、DQp表示應(yīng)急配送中心集合以及配送中心p的容量；

C= {r|r=1,2,…,R}、CQr表示應(yīng)急物資需求點(diǎn)集合以及需求點(diǎn)r的需求量；

U=D∪C表示所有節(jié)點(diǎn)的集合；

V= {k|k=1,2,…,K}、VQk表示配送中心車輛集合以及車輛k的容量；

TDp表示配送中心p投入使用的準(zhǔn)備時間；

TVk表示車輛k單位物資裝卸花費(fèi)的時間；

ETr表示需求點(diǎn)r期待物資到達(dá)的時間點(diǎn)；

LTr表示需求點(diǎn)r要求物資到達(dá)的最晚時間點(diǎn)；

Tr表示需求點(diǎn)r被服務(wù)的時間；

vk表示車輛k的平均行駛速度；

dij表示節(jié)點(diǎn)i到j(luò)的最小行駛距離；

aij表示平面距離與最小行駛距離之間的轉(zhuǎn)換系數(shù)，aij=aji，且aij≥1；

SDp表示配送中心p投入使用前的建設(shè)成本；

SVk表示車輛k的派遣成本，包括配對的人員成本；

SL表示單位物資到達(dá)需求點(diǎn)的裝卸成本；

SU表示配送車輛的單位距離運(yùn)輸成本；

SFr表示需求點(diǎn)被配送時超出ETr下的懲罰成本；

h表示單位物資懲罰成本；

g表示時間窗內(nèi)懲罰成本隨時間的變化系數(shù)決策變量：

uk：車輛k投入使用則取1，否則取0；

xp：備選配送中心p被選中則取1，否則取0；

yrp：應(yīng)急需求點(diǎn)r分配給投入使用的配送中心p時取1，否則取0；

zijk：車輛k從節(jié)點(diǎn)i駛向j則取1，否則取0。

對符號做一點(diǎn)補(bǔ)充說明?？紤]無孤立需求點(diǎn)的應(yīng)急物流配送問題，總是存在一個非無窮大的常數(shù)aij，使得任意點(diǎn)j到某點(diǎn)i的可行路徑存在。顯然這是符合現(xiàn)實(shí)的，任意兩地之間不管曲直，總存在可到達(dá)路徑。

3.2 模型建立

上述應(yīng)急物流系統(tǒng)設(shè)施定位-運(yùn)輸路線問題可以用雙層規(guī)劃模型描述：

上層模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

U=C∪D,xp∈{0,1},yrp∈{0,1},zijk∈{0,1}

(11)

上述模型中，目標(biāo)函數(shù)(1)表示最小化系統(tǒng)響應(yīng)時間，由配送中心準(zhǔn)備時間、物資配送過程中的裝卸時間和車輛運(yùn)輸時間三部分組成；式(2)表示配送中心的容量約束；式(3)表示每個需求點(diǎn)只被一個配送中心服務(wù)；式(4)表示每個需求點(diǎn)被且僅被服務(wù)一次；式(5)表示配送車輛的容量約束；約束式(6)保證配送路線的連續(xù)和閉合，進(jìn)入每個節(jié)點(diǎn)的車輛必須從該節(jié)點(diǎn)離開；式(7)表示每輛車至多只分配給一個配送中心；式(8)表示每個被選中投入使用的配送中心都有可支配車輛；式(9)表示任意兩個配送中心之間無連接；約束(10)表示從某配送中心出發(fā)的車輛最后必須回到該配送中心。

下層模型

(12)

zijk≤uk,?i,j∈U

(13)

(14)

(15)

(16)

除此之外，上層模型的約束同樣也是下層模型的約束。模型中，目標(biāo)函數(shù)(12)由五部分組成，分別是配送中心建設(shè)成本、車輛人員派遣成本、物資裝卸成本、車輛運(yùn)輸成本和時間窗懲罰成本；式(13)表示對配送車輛的約束，車輛k投入使用的情況下才可能存在k的運(yùn)輸服務(wù)；式(14)表示對從配送中心出發(fā)的車輛的時間窗約束；式(15)表示車輛巡回配送過程中的時間窗約束；式(16)表示車輛到達(dá)需求點(diǎn)的時間點(diǎn)。由于上層規(guī)劃中每確定一個最優(yōu)方案，總能確定xijk，yrp的取值，因此下層約束中出現(xiàn)兩者取1的情形。

其中時間懲罰成本函數(shù)表達(dá)如下：

(17)

懲罰函數(shù)的參數(shù)中包含了需求量，這是符合實(shí)際意義的，懲罰成本與需求量之間存在線性正相關(guān)關(guān)系。約束條件中已存在各需求點(diǎn)被服務(wù)時間不超過時間窗上限，故時間懲罰成本自變量的范圍在期待時間點(diǎn)和可容忍時間點(diǎn)之間。

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

上述模型是一個典型的混合整數(shù)雙層規(guī)劃模型，屬于NP-hard問題，不存在精確求解算法，許多文獻(xiàn)對求解雙層規(guī)劃模型的高效算法進(jìn)行了研究。對非線性雙層規(guī)劃問題，下降方向法是較常用的一種；對線性雙層規(guī)劃問題，求解的方法較多，如極點(diǎn)搜索法、互補(bǔ)旋轉(zhuǎn)法、罰函數(shù)法等。然而以上算法在原理上大多要求目標(biāo)函數(shù)在可行域或分塊領(lǐng)域內(nèi)連續(xù)，因此對混合整數(shù)雙層規(guī)劃問題而言，智能優(yōu)化算法的應(yīng)用更為廣泛。

上層決策者設(shè)施定位的目的是使得應(yīng)急物流系統(tǒng)總響應(yīng)時間最短，僅就上層模型而言，在備選配送中心數(shù)量不大的情形下，運(yùn)用優(yōu)化算法可求得最優(yōu)應(yīng)急配送中心集合。考慮到下層決策者在運(yùn)輸路線安排方面有充分的自主權(quán)，因此所選擇的配送中心集合往往不能達(dá)到上層決策者的理想程度，甚至偏差很大，這也是雙層規(guī)劃問題通常不能逐層獨(dú)立求解的原因。對應(yīng)急物流系統(tǒng)而言，備選配送中心和選中配送中心的數(shù)量并不會太多，否則就失去了集中配送的意義，且當(dāng)所選中配送中心的容量足以滿足所有救援點(diǎn)需求的情況下，其余的配送中心不會被投入使用，否則不但增加上層規(guī)劃中配送中心投入使用的準(zhǔn)備時間，而且增加下層規(guī)劃中配送中心的建設(shè)成本。

基于以上模型的特點(diǎn)和實(shí)際問題的意義，設(shè)計(jì)了一種結(jié)合禁忌搜索技術(shù)的兩階段混合模擬退火算法進(jìn)行求解。

階段一：建立禁忌表，以交換編碼方式確定可選配送中心集合。

步驟1對每個備選配送中心進(jìn)行編號；

步驟2從備選配送中心里按編號依次選擇直至被選中配送中心總?cè)萘砍^救援點(diǎn)總需求量，按實(shí)際距離最短原則對救援點(diǎn)進(jìn)行初始劃分，即將救援點(diǎn)依次劃分給距離其最近的被選中的配送中心，若超出該配送中心容量則劃分給下一個近距離配送中心，以此類推。若有救援點(diǎn)未被分配，則從余下的備選配送中心中選擇到這些救援點(diǎn)總距離最小的配送中心放入被選中集合；

步驟3建立禁忌表，將初次選中的配送中心集合放入禁忌表，禁忌規(guī)則為不允許出現(xiàn)包含此配送中心集合的集合；

步驟4對已選擇的配送中心集合進(jìn)行換出換入處理，即從中換出一個并且從未被選擇的配送中心里換入一個，滿足步驟2條件和禁忌要求，并將新的集合放入禁忌表；

步驟5重復(fù)步驟4，直至對初始集合里的每個對象都遍歷完換入換出步驟。

階段二：根據(jù)階段一給出的禁忌表，采用啟發(fā)式規(guī)則構(gòu)造初始解，帶記憶累加的模擬退火算法求得每組集合對應(yīng)的最小成本和總配送時間。

(1)初始解構(gòu)造。在上一階段救援點(diǎn)的分配中已經(jīng)考慮到各救援點(diǎn)到被選中配送中心的距離，類似于聚類法，對救援點(diǎn)的劃分較為合理。采用貪婪就近原則構(gòu)造初始解，對某救援點(diǎn)是否被某輛車配送的判斷準(zhǔn)則為該救援點(diǎn)需求量不大于配送車輛的剩余容量，且車輛到達(dá)時間早于時間窗上限。

(2)模擬退火算法的設(shè)定。采用目標(biāo)函數(shù)值評價解的優(yōu)劣，每條線路上的救援點(diǎn)以兩兩互換的方式搜索鄰域，同時確定降溫速度。

(3)路線再調(diào)整。對于只服務(wù)個別救援點(diǎn)的車輛，判斷能否將這些救援點(diǎn)插入別的線路，判斷準(zhǔn)則為車輛剩余容量、對應(yīng)配送中心剩余容量、時間窗上限和目標(biāo)函數(shù)。

(4)記憶裝置的設(shè)計(jì)。算法運(yùn)行中設(shè)計(jì)一個記憶數(shù)組，記錄和比較每次鄰域轉(zhuǎn)換后目標(biāo)函數(shù)的值，不斷更新確保輸出的是搜索過程中的最優(yōu)解。

(5)累加裝置的設(shè)計(jì)。設(shè)計(jì)一個累加器，對每個救援點(diǎn)的裝卸時間和車輛行駛時間進(jìn)行累加，得到每個配送中心集合最優(yōu)成本方案下的總配送時間。

(6)終止準(zhǔn)則的確定。設(shè)定最低溫度，當(dāng)下降到該溫度時，算法終止。

圖1 算法流程圖

5 算例分析

隨機(jī)給出4個備選應(yīng)急配送中心，20個災(zāi)區(qū)救援點(diǎn)，本文研究的問題為一次性應(yīng)急配送，非多周期多階段活動，因此車輛數(shù)量足夠。隨機(jī)模擬方法生成各救援點(diǎn)坐標(biāo)及需求量，其中坐標(biāo)對應(yīng)單位是公里。定義轉(zhuǎn)換系數(shù)aij=1.5，車輛容量800件，派遣費(fèi)600元/輛，行駛速度90km/h，裝卸成本1元/件，卸貨時間為0.1min/件，運(yùn)輸成本為1元/km，時間懲罰成本為1元每件每小時。備選配送中心編號、平面坐標(biāo)、容量等信息如表1所示，各救援點(diǎn)平面坐標(biāo)、需求、時間窗等信息如表2所示。

表1 備選應(yīng)急配送中心信息

表2 救援點(diǎn)信息

模擬退火算法的主要參數(shù)有初始溫度、終止溫度、降溫函數(shù)、鄰域選擇策略等，許多文獻(xiàn)從理論研究、數(shù)值分析的角度證明了對不同規(guī)模的問題，設(shè)定參數(shù)的大小對收斂性的影響。鑒于本算例中各條運(yùn)輸路線車輛所服務(wù)的救援點(diǎn)不多，取初始溫度T0=28，終止溫度Tf=1，降溫函數(shù)定義為Tk+1=Tk-△T，降溫步長△T=3，內(nèi)循環(huán)次數(shù)設(shè)置為n(Tk)=5。一階段禁忌搜索得應(yīng)急配送中心可行集合，模擬退火算法求得各可行集的最優(yōu)配送路線及總配送時間，計(jì)算結(jié)果及車輛配送路線如表3-7所示。

表3 可行集合{A,B}

表4 可行集合{A,C}

表5 可行集合{A,D}

表6 可行集合{B,C}

表7 可行集合{C,D}

基于上層優(yōu)先決策并考慮在此基礎(chǔ)上下層自由安排路線的原則，選擇應(yīng)急配送中心B和C為最佳LRP方案。

由于混合整數(shù)雙層規(guī)劃模型具有遞階決策的結(jié)構(gòu)特性，無法用傳統(tǒng)算法求解，本文采用鄭斌等[14]設(shè)計(jì)的混合遺傳算法求解，與兩階段模擬退火算法進(jìn)行對比。對備選配送中心編號，基因位取0或1來表示是否選中該配送中心，當(dāng)已選配送中心容量小于總需求量時，隨機(jī)選中未被選擇的配送中心，選擇下層目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，即系統(tǒng)總成本和時間懲罰成本之和，采用輪盤選擇和精英保留結(jié)合的選擇策略，設(shè)置最大迭代次數(shù)，每次迭代結(jié)束輸出總成本和總時間，然后對選中的配送中心換入換出處理，直到遍歷完所有可行集合產(chǎn)生重復(fù)，算法終止，選擇其中總時間最少的解作為最優(yōu)方案，對應(yīng)的總成本即為下層模型的目標(biāo)值。混合遺傳算法求解最優(yōu)結(jié)果如下表所示。

表8 選址集合{B,C}

對比可知，所設(shè)計(jì)的兩階段模擬退火算法效果較好，無論是耗時還是成本都好于混合遺傳算法，且由于沒有禁忌表來產(chǎn)生可行配送中心集合，混合遺傳算法運(yùn)行中出現(xiàn)多個顯然不是最優(yōu)解的包含三個配送中心的迭代，運(yùn)行效率較低。

6 結(jié)語

本文針對應(yīng)急物流由政府和企業(yè)共同參與的表現(xiàn)形式，研究了災(zāi)后設(shè)施定位-運(yùn)輸路線安排問題，提出一個上層以應(yīng)急物流系統(tǒng)總耗時最短、下層以配送成本和時間懲罰成本最小的雙層規(guī)劃模型，以此對物流系統(tǒng)決策分析。根據(jù)上下層獨(dú)立決策又相互影響的特點(diǎn)，設(shè)計(jì)了帶禁忌搜索的混合模擬退火算法，并結(jié)合算例和對比算法驗(yàn)證所設(shè)計(jì)算法的可行性。

本文研究了確定性需求下對救援點(diǎn)進(jìn)行巡回配送的LRP，未考慮多配送方式以及動態(tài)需求下的配送，進(jìn)一步的研究還要考慮多車型混合配送以及動態(tài)需求下的多階段配送等問題。

[1] Jia Hongzhong, Ordonez F, Dessouky M M. Solution approaches for facility location of medical supplies for large-scale emergencies [J].Department of Industrial and Systems Engineering, 2007, 52(2):257-276.

[2] Doyen A, Aras N, Barbarosoglu G. A two-echelon stochastic facility location model for humanitarian relief logistics [J].Optimization Letters, 2011, 6(6):1123-1145.

[3] 劉波,李波,李硯.不確定條件下應(yīng)急物流系統(tǒng)魯棒雙層優(yōu)化模型[J].統(tǒng)計(jì)與決策,2014, 9(23):40—43.

[4] Alem D, Clark A, Moreno A. Stochastic network models for logistics planning in disaster relief [J] .European Journal of Operational Research, 2016, 21(28): 1-20.

[5] 王紹仁,馬祖軍.震后應(yīng)急物流系統(tǒng)中帶時間窗的模糊動態(tài)LRP[J].運(yùn)籌與管理,2011, 20(5):63—72.

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

[7] Pramanik S, Jana D K, Maiti M. Bi-criteria solid transportation problem with substitutable and damageable items in disaster response operations on fuzzy rough environment [J].Socio-Economic Planning Sciences, 2016(C), 55:1-13.

[8] 張曉楠,范厚明,李劍鋒.變動補(bǔ)償?shù)亩嗄：x址—路徑機(jī)會約束模型及算法[J].系統(tǒng)工程理論與實(shí)踐,2016, 36(2):442—453.

[9] 王紹仁,馬祖軍.震害緊急響應(yīng)階段應(yīng)急物流系統(tǒng)中的LRP[J].系統(tǒng)工程理論與實(shí)踐,2011,30(8):1497—1507.

[10] Sheu J B, Pan Cheng. Relief supply collaboration for emergency logistics responses to large-scale disasters [J].Transportmetrica A: Transport Science, 2015, 11(3): 210-242.

[11] 侯玉梅,賈震環(huán),田歆.帶軟時間窗整車物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學(xué)報,2015, 30(2):240—250.

[12] Vincent F. Yu, Parida Jewpanya, Voratas. Particle swarm optimization for the multi-period cross-docking distribution problem with time windows [J] .International Journal of Product Research, 2016, 54(2):509-525.

[13] 丁佩雯,蔣祖華,胡家文.帶有交貨期時間窗的生產(chǎn)與維護(hù)聯(lián)合調(diào)度優(yōu)化[J].上海交通大學(xué)學(xué)報,2015, 49(4):524—530.

[14] 鄭斌,馬祖軍,李雙琳.基于雙層規(guī)劃的應(yīng)急物流系統(tǒng)選址—聯(lián)運(yùn)問題[J].系統(tǒng)科學(xué)與數(shù)學(xué),2013, 33(9):1045—1060.

[15] Zhang Jingling, Wang Wanliang, Zhao Yanwei, et al. Multi-objective quantum evolutionary algorithm for the vehicle routing problem with customer satisfaction [J].Mathematical Problems in Engineering, 2012, 10: 1-19.

[16] Zhang Xiang, Wang Hao, Wang Wei. Bi-level programming model and algorithms for stochastic network with elastic demand [J] .Transport, 2015, 30(1):117-128.

[17] 周曉陽,趙璨暉,魯渤.不確定條件下基于分散式雙層規(guī)劃的綠色協(xié)同港口物流系統(tǒng)優(yōu)化[J].中國管理科學(xué),2015, 23(S1):262—268.

[18] 黃正海,林貴華,修乃華.變分不等式與互補(bǔ)問題、雙層規(guī)劃與平衡約束數(shù)學(xué)規(guī)劃問題的若干進(jìn)展[J].運(yùn)籌學(xué)學(xué)報,2014, 18(1):113—133.

Bi-level Programming Model and Algorithmof Location-routing Problem in Emergency Logistics

LOUZhen-kai

(School of Management and Economics, Beijing Institute of Technology, Beijing 100081,China)

To optimize emergency logistics distribution system for natural disasters like floods and earthquakes, a bi-level programming model of location allocation-vehicle routing problem is set up by considering the characteristics that government and enterprises participate together but make decision separately. The upper level is to minimize the total time of emergency logistics system, and the lower level is to minimize the sum of distribution costs and time penalty cost. According to the characteristic of independent decision-making and interaction effect in upper and lower level in the model, the problem is broken up into two stages. In the first stage, viable gathers of distribution center are produced. In the second stage, vehicles and transport routes are arranged under viable gathers. A heuristic rule of two stage hybrid simulated annealing algorithm, one-phase tabu search,is designed to determine feasible emergency distribution center collections. The initial solution is construeted by principle of greedy proximity. Code is exchanged to search neighborhood feasible solution. The optimal solution is recorded and updated unloading and driving time is accumulated and output as the basis of the upper decision. Finally a numerical example and the comparing hybrid genetic algorithm are given to verify the validity of the model and the feasibility of the algorithm. A solution for emergency logistics system planning problem of multi-level decision is provided.

emergency logistics system; location allocation-vehicle routing; bi-level programming; tabu search; simulated annealing algorithm

1003-207(2017)11-0151-07

10.16381/j.cnki.issn1003-207x.2017.11.016

F252

A

2016-07-29；

2017-02-27

樓振凱(1989-)，男(漢族)，浙江浦江人，北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院博士生，研究方向：決策理論優(yōu)化算法，E-mail：07224014@bjtu.edu.cn.