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

張 碩，楊學強

（陸軍裝甲兵學院，北京 100071）

0 引言

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

1 LIRP問題研究發展歷程

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

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

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

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

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

2 利用現代啟發式算法求解的LIRP問題

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

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

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

2.1 禁忌搜索算法

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

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

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

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

2.2 遺傳算法

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

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

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

3 考慮特殊約束的LIRP問題

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

3.1 考慮閉環供應鏈的LIRP問題

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

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

3.2 考慮碳排放的LIRP問題

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

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

4 結語

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

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

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