選址-庫存-路徑問題研究綜述

張 碩，楊學(xué)強

（陸軍裝甲兵學(xué)院，北京 100071）

0 引言

傳統(tǒng)的物流決策模型主要研究選址決策、庫存管理和車輛運輸路徑問題。三者分別屬于戰(zhàn)略、戰(zhàn)術(shù)和運作層面，即選址（Location）、庫存（Inventory）、運輸路徑（Routing）三種需要考慮的因素。倉庫數(shù)量越多，運輸路徑越短，服務(wù)水平越高，但運營成本也隨之增高。物流系統(tǒng)的選址-庫存-路徑問題，實質(zhì)上是一個效益與成本的權(quán)衡問題，需要找到一個平衡點，使得整個系統(tǒng)處于最優(yōu)狀態(tài)。因此，需要從系統(tǒng)角度對選址-庫存-路徑問題（Location-Inventory-Routing Problem，LIRP）進行研究。

1 LIRP問題研究發(fā)展歷程

學(xué)者們分別對選址、庫存、路徑這三個領(lǐng)域進行研究，并取得了很多的研究成果。但事實上，三者之間存在密切的相互依賴關(guān)系，這種依賴關(guān)系是物流優(yōu)化需要考慮的重要因素，要根據(jù)這種關(guān)系從綜合系統(tǒng)的角度去研究物流優(yōu)化問題[1]。

早期的基礎(chǔ)研究主要集中在三個決策要素的兩兩集成，如選址-路徑問題、庫存-路徑問題、選址-庫存問題等，并且以選址-庫存問題居多[2-12]。

近年來學(xué)者們開始關(guān)注三者綜合集成的選址-庫存-路徑問題的研究，Shen，等[13]認為戰(zhàn)略、戰(zhàn)術(shù)和運作這三個層面是密切聯(lián)系的，需要找到能使整個系統(tǒng)最優(yōu)的優(yōu)化方法。選址、庫存、路徑問題則分別對應(yīng)了戰(zhàn)略、戰(zhàn)術(shù)、運作層面。他建立了一個非線性規(guī)劃模型，綜合考慮了選址、庫存以及運輸三種因素。為求解該模型，他提出了內(nèi)嵌分枝定界法的拉格朗日算法，該方法與之前的研究相比，可顯著地節(jié)約成本，但該模型僅優(yōu)化了選址－庫存成本，并沒有給出運輸決策。Perl,Jayaraman,Nozick，等學(xué)者[14-18]都提出了一個綜合考慮設(shè)施位置、庫存和運輸路徑的分銷網(wǎng)絡(luò)設(shè)計模型，從系統(tǒng)的角度初步把選址、庫存、路徑三個要素結(jié)合了起來。

一般認為，最早研究選址-路徑-庫存問題的是Liu和Lee[19]，這也是針對嚴格的LIRP問題最早的文獻，在多節(jié)點的選址-路徑問題的基礎(chǔ)上進一步探討了庫存問題，研究對象為單一產(chǎn)品。文章還設(shè)計了一個兩階段的啟發(fā)式算法求解，之后通過仿真對模型和算法進行了測試。由于兩階段的啟發(fā)式算法容易找到局部最優(yōu)的解，Liu，等[20]又將LRIP問題分為選址-分派問題和路徑-庫存問題兩個子問題，并提出了混合禁忌搜索和退火模擬算法進行求解。

之后，國內(nèi)外學(xué)者在此基礎(chǔ)上，從模型的建立到算法的設(shè)計，從典型的LIRP模型到考慮多種約束條件的LIRP模型，對LIRP問題開展了廣泛研究。

2 利用現(xiàn)代啟發(fā)式算法求解的LIRP問題

一些學(xué)者利用經(jīng)典的運籌學(xué)方法對LIRP問題進行了求解。如杜麗敬，等[21]將非線性混合整數(shù)規(guī)劃轉(zhuǎn)化為線性整數(shù)集合覆蓋模型,先采用列生成算法來獲得一個近似最優(yōu)解,再用分支定價法對初始解進行改進,實現(xiàn)了對整個問題“完全集成”的優(yōu)化。但由于LIRP問題屬于NP-Hard問題，采用現(xiàn)代啟發(fā)式算法求解更為快捷方便。所以，更多的學(xué)者設(shè)計與改進了包括遺傳算法、禁忌搜索、模擬退火等多種現(xiàn)代啟發(fā)式算法用于求解LIRP問題。

崔廣彬和李一軍[22]建立了一個基于雙層規(guī)劃的LIRP問題的模型，并設(shè)計了一種啟發(fā)式算法求解模型。之后，崔廣彬[23]又在上文的基礎(chǔ)上，通過客戶模糊需求存儲策略確定了其最佳訂貨量。Guerrero，等[24]建立了一個混合整數(shù)規(guī)劃的LIRP問題的模型，并采用混合啟發(fā)式算法進行了求解，算例涉及了三種不同的情況。Guerrero，等[25]又采用列生成、拉格朗日和局部搜索這三者相結(jié)合的方法進行了求解。Liu，等[26]研究了考慮電商收益的LIRP問題，設(shè)計了一種偽并行模擬退火的算法進行求解。

采用各種啟發(fā)式算法解決LIRP問題時，以禁忌搜索算法和遺傳算法的應(yīng)用最為廣泛。

2.1 禁忌搜索算法

禁忌搜索（Tabu Search，TS，又稱禁忌搜尋法）是一種現(xiàn)代啟發(fā)式算法，是一個用來跳脫局部最優(yōu)解的搜索方法。由于禁忌搜索算法的優(yōu)越性，很多學(xué)者提出用禁忌搜索算法求解LIRP問題，并提出了很多改進禁忌搜索算法的方案，如與模擬退火算法相結(jié)合、采用兩階段的啟發(fā)式算法等。

Bard[27]和王運發(fā)[28]分別建立了一個多周期LIRP問題的模型，前者設(shè)計了一種自適應(yīng)的禁忌搜索算法求解，后者證明了禁忌搜索算法求解LIRP問題時，具有很強的魯棒性。尉遲群麗[29]和李昌兵[30]都研究了正向和逆向物流相結(jié)合的LIRP問題，采用改進的禁忌搜索算法進行求解。后者還把問題分成了選址和路徑-庫存兩個子問題。

更多的學(xué)者把禁忌搜索算法和其他算法結(jié)合了起來，用于求解LIRP問題。Javid，等[31]探討了不確定需求的LIRP問題，建立了一個混合凸整數(shù)規(guī)劃的模型，采用基于禁忌搜索和模擬退火的兩階段啟發(fā)式算法進行求解。呂飛和李延暉[32]在備件物流系統(tǒng)的LIRP問題中加入了時間因素，建立了一個帶軟時間窗的集成優(yōu)化模型，以兩階段混合式啟發(fā)算法求解。先將問題分解為選址-庫存和運輸路徑兩個子問題分別求解，用禁忌搜索算法求解選址-庫存問題，基于選址-庫存問題的結(jié)果，用改進的C-W節(jié)約算法求解運輸路徑問題。

唐瓊，等[33]建立了基于雙層規(guī)劃的LIRP問題的模型，后又考慮到送貨時間是衡量服務(wù)水平的重要因素，在模型中引入了軟時間窗，并設(shè)計了內(nèi)嵌禁忌搜索的改進模擬退火算法對模型進行了求解。還將文中的算法分別與禁忌搜索算法和模擬退火算法進行對比，證明了文中算法的優(yōu)越性[25]。

2.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法多與其他算法結(jié)合改進，用于LIRP問題的求解。

王超峰，等[35]在LIRP問題中考慮了橫向調(diào)度因素,設(shè)計了隱枚舉法和遺傳算法相結(jié)合的啟發(fā)式算法,最后通過仿真實驗驗證了算法的有效性。吳迪，等[36]研究了LIRP問題在邊遠群島海運物流體系的應(yīng)用，提出了一種基于遺傳算法和模擬植物生長算法的混合算法進行求解。張得志，等[37]設(shè)計了一種矩陣編碼的改進自適應(yīng)遺傳算法，用于求解多層級裝配型制造企業(yè)的LIRP問題。

此外，還有很多算法被設(shè)計、改進從而應(yīng)用于求解LIRP問題，如粒子群算法、蟻群算法、C-W節(jié)約算法等[38-40]。采用多種算法結(jié)合的兩階段啟發(fā)式算法是求解LIRP問題的一大發(fā)展趨勢。

3 考慮特殊約束的LIRP問題

除了對算法進行設(shè)計改進，很多學(xué)者還從模型的特殊約束條件對LIRP問題進行了研究，從而應(yīng)用于不同的實際場景，如上文提到的呂飛[32]、唐瓊[34]等，在LIRP問題中考慮了時間因素。王超峰[35]加入了橫向調(diào)度因素，吳迪[36]研究了LIRP問題在邊遠群島海運體系中的應(yīng)用等。而研究LIRP問題考慮最多的兩個特殊約束是閉環(huán)供應(yīng)鏈（如退貨、廢棄產(chǎn)品的回收再制造等）和碳排放。

3.1 考慮閉環(huán)供應(yīng)鏈的LIRP問題

典型的LIRP問題一般不包括逆向物流。但隨著經(jīng)濟發(fā)展，電商配送占據(jù)的市場份額逐漸增加，換退貨問題逐漸增多，為貼近現(xiàn)實，越來越多的學(xué)者開始在LIRP問題中引入逆向物流的因素，形成了閉環(huán)的供應(yīng)鏈。

Li，等[41]在LIRP問題中加入了無質(zhì)量問題退貨的因素，退回的產(chǎn)品回收后可以再次進入正向物流。Deng，等[42]在Li等的基礎(chǔ)上，又考慮了有質(zhì)量問題的退貨。Zhalechian，等[43]以企業(yè)加入逆向物流后帶來的工作機會的增加和環(huán)境污染的減輕為切入點，研究了多目標(biāo)的閉環(huán)LIRP問題。同樣研究閉環(huán)供應(yīng)鏈LIRP問題的學(xué)者還有Wang[44]、尉遲群麗[29]、李昌兵[30]等。

3.2 考慮碳排放的LIRP問題

隨著時代的發(fā)展以及教育水平的提升，越來越多的企業(yè)開始著眼于社會效益，越來越多的顧客也開始重視產(chǎn)品的環(huán)保因素。碳排放逐漸成為研究LIRP問題需要考慮的重要因素。

唐金環(huán)，等[45-48]進行了一系列研究，構(gòu)建了LIRP問題中考慮有“碳行為”偏好的聯(lián)合優(yōu)化模型，并分析了顧客的行為偏好，給出了碳配額稅的概念，引入了碳配額差值系數(shù)。還運用基于NNC的多目標(biāo)求解方法和改進的多目標(biāo)混合粒子群算法（MOHPSO）等方法進行了求解。王夢夢，等[49]在碳排放的LIRP模型中，選擇了易腐品作為重點研究對象。戢守峰，等[50]研究了擁堵和限速路況下考慮碳排放的LIRP問題，并通過基于中石油東北化工銷售公司的計算實驗與分析表明,所構(gòu)建的模型是有效的。

4 結(jié)語

本文對LIRP問題的研究現(xiàn)狀進行了綜述，主要梳理了LIRP問題研究的發(fā)展歷程、求解的現(xiàn)代啟發(fā)式算法以及考慮特殊約束條件的LIRP問題三個方面。從選址、庫存、路徑的兩兩結(jié)合的研究到綜合集成三個因素的研究，對LIRP問題的研究逐步深入。隨著現(xiàn)代啟發(fā)式算法的逐漸成熟，諸如禁忌搜索、模擬退火、遺傳算法等啟發(fā)式算法也開始廣泛應(yīng)用于LIRP問題的求解。LIRP問題考慮的約束條件也越來越多，如廢棄與回收物流、碳排放等，模型越來越貼合實際。

然而，LIRP問題的一大特征是應(yīng)用廣泛，很多現(xiàn)實的物流系統(tǒng)都可以抽象為LIRP問題。但是隨著現(xiàn)實物流系統(tǒng)的改變，供應(yīng)鏈的層級和流程在變化，LIRP的模型需要考慮的約束條件也應(yīng)隨之改變。不同的物流系統(tǒng)抽象出的LIRP模型也不盡相同，設(shè)計的求解算法也不同。后續(xù)研究應(yīng)針對所研究的具體領(lǐng)域，對LIRP問題進行創(chuàng)新。

另一方面，目前針對LIRP問題的研究，主要集中于單一品種產(chǎn)品，對多品種產(chǎn)品研究較少，且LIRP問題屬于NP-Hard問題，一步式啟發(fā)算法求解很容易陷入局部最優(yōu)。目前，很多學(xué)者通過兩階段啟發(fā)算法來避免這個問題，但實質(zhì)上是把LIRP問題分解成了兩個問題，回到了分別優(yōu)化或者部分集成優(yōu)化的過程，沒有體現(xiàn)“集成優(yōu)化”。針對LIRP問題的求解算法還有很大的優(yōu)化空間，后續(xù)研究可以從這些方面展開。