應急物流系統LRP的雙層規劃模型及算法

樓振凱

(北京理工大學管理與經濟學院，北京 100081)

應急物流系統LRP的雙層規劃模型及算法

樓振凱

(北京理工大學管理與經濟學院，北京 100081)

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

應急物流；設施定位-運輸路線；雙層規劃；禁忌搜索；模擬退火算法

1 引言

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

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

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

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

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

2 問題描述

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

本文作如下假設：

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

(2)應急物資足夠，且車輛數足夠；

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

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

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

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

3 模型構建

3.1 符號說明

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

C= {r|r=1,2,…,R}、CQr表示應急物資需求點集合以及需求點r的需求量；

U=D∪C表示所有節點的集合；

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

TDp表示配送中心p投入使用的準備時間；

TVk表示車輛k單位物資裝卸花費的時間；

ETr表示需求點r期待物資到達的時間點；

LTr表示需求點r要求物資到達的最晚時間點；

Tr表示需求點r被服務的時間；

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

dij表示節點i到j的最小行駛距離；

aij表示平面距離與最小行駛距離之間的轉換系數，aij=aji，且aij≥1；

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

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

SL表示單位物資到達需求點的裝卸成本；

SU表示配送車輛的單位距離運輸成本；

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

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

g表示時間窗內懲罰成本隨時間的變化系數決策變量：

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

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

yrp：應急需求點r分配給投入使用的配送中心p時取1，否則取0；

zijk：車輛k從節點i駛向j則取1，否則取0。

對符號做一點補充說明。考慮無孤立需求點的應急物流配送問題，總是存在一個非無窮大的常數aij，使得任意點j到某點i的可行路徑存在。顯然這是符合現實的，任意兩地之間不管曲直，總存在可到達路徑。

3.2 模型建立

上述應急物流系統設施定位-運輸路線問題可以用雙層規劃模型描述：

上層模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

(11)

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

下層模型

(12)

zijk≤uk,?i,j∈U

(13)

(14)

(15)

(16)

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

其中時間懲罰成本函數表達如下：

(17)

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

4 算法設計

上述模型是一個典型的混合整數雙層規劃模型，屬于NP-hard問題，不存在精確求解算法，許多文獻對求解雙層規劃模型的高效算法進行了研究。對非線性雙層規劃問題，下降方向法是較常用的一種；對線性雙層規劃問題，求解的方法較多，如極點搜索法、互補旋轉法、罰函數法等。然而以上算法在原理上大多要求目標函數在可行域或分塊領域內連續，因此對混合整數雙層規劃問題而言，智能優化算法的應用更為廣泛。

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

基于以上模型的特點和實際問題的意義，設計了一種結合禁忌搜索技術的兩階段混合模擬退火算法進行求解。

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

步驟1對每個備選配送中心進行編號；

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

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

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

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

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

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

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

(3)路線再調整。對于只服務個別救援點的車輛，判斷能否將這些救援點插入別的線路，判斷準則為車輛剩余容量、對應配送中心剩余容量、時間窗上限和目標函數。

(4)記憶裝置的設計。算法運行中設計一個記憶數組，記錄和比較每次鄰域轉換后目標函數的值，不斷更新確保輸出的是搜索過程中的最優解。

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

(6)終止準則的確定。設定最低溫度，當下降到該溫度時，算法終止。

圖1 算法流程圖

5 算例分析

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

表1 備選應急配送中心信息

表2 救援點信息

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

表3 可行集合{A,B}

表4 可行集合{A,C}

表5 可行集合{A,D}

表6 可行集合{B,C}

表7 可行集合{C,D}

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

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

表8 選址集合{B,C}

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

6 結語

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

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

[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] 劉波,李波,李硯.不確定條件下應急物流系統魯棒雙層優化模型[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] 王紹仁,馬祖軍.震后應急物流系統中帶時間窗的模糊動態LRP[J].運籌與管理,2011, 20(5):63—72.

[6] 劉長石,彭怡,寇綱.震后應急物資配送的模糊定位-路徑問題研究[J].中國管理科學,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] 張曉楠,范厚明,李劍鋒.變動補償的多模糊選址—路徑機會約束模型及算法[J].系統工程理論與實踐,2016, 36(2):442—453.

[9] 王紹仁,馬祖軍.震害緊急響應階段應急物流系統中的LRP[J].系統工程理論與實踐,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] 侯玉梅,賈震環,田歆.帶軟時間窗整車物流配送路徑優化研究[J].系統工程學報,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] 丁佩雯,蔣祖華,胡家文.帶有交貨期時間窗的生產與維護聯合調度優化[J].上海交通大學學報,2015, 49(4):524—530.

[14] 鄭斌,馬祖軍,李雙琳.基于雙層規劃的應急物流系統選址—聯運問題[J].系統科學與數學,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] 周曉陽,趙璨暉,魯渤.不確定條件下基于分散式雙層規劃的綠色協同港口物流系統優化[J].中國管理科學,2015, 23(S1):262—268.

[18] 黃正海,林貴華,修乃華.變分不等式與互補問題、雙層規劃與平衡約束數學規劃問題的若干進展[J].運籌學學報,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-)，男(漢族)，浙江浦江人，北京理工大學管理與經濟學院博士生，研究方向：決策理論優化算法，E-mail：07224014@bjtu.edu.cn.