基于改進蟻群優(yōu)化算法求解應急物資庫存路徑問題

周丹 邱玉琢

摘要：建立以預測需求為導向進行補貨的應急物資庫存路徑問題的模型作為應急物資庫存路徑問題的通用模型。模型中采用預測需求函數作為補貨的基礎，避免單獨使用OU補貨政策導致補貨過度僵化脫離實際。運用改進蟻群優(yōu)化算法對模型進行求解，在蟻群優(yōu)化算法中結合遺傳算法中的多種操作，避免蟻群優(yōu)化算法過早陷入局部最優(yōu)，擴大其搜索域從而提高算法的性能。大量算例的計算表明，所提出的改進的蟻群優(yōu)化算法能夠在短時間內收斂;模型中各參數的敏感性分析結果表明：庫存持有成本的增加一般會增加目標函數值，缺貨成本的陡增不僅會增加目標函數值還會增加計算難度。

關鍵詞：應急物資;庫存路徑;蟻群優(yōu)化;預測需求函數;補貨策略

中圖分類號：O227文獻標識碼：ADOI：10.16465/j.gste.cn431252ts.20210617

2020年初爆發(fā)的大流行傳染病COVID-19昭示了當前社會對應急儲備物流優(yōu)化的迫切需求。突發(fā)性事件具有高度的突發(fā)性和緊急性，事件發(fā)生地區(qū)的物資儲備的種類及數量往往不能滿足事件發(fā)生地區(qū)的需求。應急物資一旦出現供需失衡，就會產生不可估量的后果，因此，必須要對應急物資進行有效且高效的管理。

自Dantzig和Ramser于1959年對著名的旅行商問題（TSP）進行推廣后得到了卡車調度問題以來，車輛路徑問題（Vehicle Routing Problem，VRP）已經發(fā)展了50多年。第一次明確地將庫存問題和路徑問題結合起來考慮是Federgruen等[1]，從而引出了如今的庫存路徑問題的研究（Inventory Routing Problem，IRP）。Archetti等[2]將供應商管理庫存的思想與路徑選擇相結合，在庫存計算和模型條件里面同時考慮了供應商的庫存和顧客的庫存。經過30 多年的發(fā)展，目前IRP被大多數學者接受的定義為：供應商向多個地理位置分散的客戶交付產品，可以通過同時優(yōu)化庫存管理、車輛路徑和交付計劃來提供集成的物流解決方案;從而確定何時為給定的客戶提供服務，在提供服務時給該客戶的交付量，以及由客戶和供應商組成的車輛路線。

目前IRP文獻中的供應商的補貨政策最常見的是訂單至最大庫存水平策略（Order-up-to-level policy，OU策略）[3]。OU政策可以闡釋為：如果在一個周期訪問了一個零售商，則運送給該零售商的產品數量要使該零售商的庫存水平達到其最大庫存水平。OU補貨策略是一種非常受歡迎，已經在許多IRP文獻中使用;但它同時又是相當僵化的庫存管理策略;而更靈活的補貨政策可能會產生大量的庫存費用。本文將以預測需求為導向，結合OU補貨策略對各個需求點進行補貨。

IRP的應用大多集中在海運、化工、石油和天然氣的運輸當中，也有許多文獻在汽車零部件、易腐品、油罐等產品中研究了路徑問題;但這些產品的研究很多僅僅是研究了它的車輛路徑，并沒有涉及庫存問題決策。在IRP當中考慮應急產品的文獻其實是相對較少的，大多數的應急產品是血液制品。查閱的眾多文獻中關于通用應急物資物流方面的研究主要還是在VRP的研究中，將IRP應用到通用的應急物資產品中的文獻較少;所以本文的主要目的是提供一個通用的應急物資IRP問題的模型，并通過改進的蟻群優(yōu)化算法為模型找到一個相對較好的上限。

到目前為止，求解IRP的方法一般分為兩類：精確算法和元啟發(fā)式算法。關于求解IRP的精確算法的文獻相對較少，且精確算法的類型較少;分支- 定價、分支-切割平面算法成為求解IRP的精確算法的主流。與精確算法相比，使用元啟發(fā)式算法的IRP文獻相對較多，如蟻群優(yōu)化、混合啟發(fā)式算法、禁忌搜索算法、粒子群優(yōu)化、遺傳算法等。學術界對各種算法的改進正在增加，但ACO近10年來在IRP方面取得的改進相對較少。

本文的主要目的是將IRP的應用拓寬至應急物流領域，證明應急物資庫存路徑問題的可建模性與可求解性。本文采用預測需求函數作為補貨的基礎，避免單獨使用OU補貨政策導致補貨過度僵化脫離實際。將IRP中客戶需求以規(guī)律的（能夠使用模型進行預測的）需求預測模型代替了以往研究中確定的需求或隨機性的需求（不規(guī)律的）。

1問題描述

2應急物資庫存路徑模型

在給出基本的IRP模型之前，首先對模型中的其他相關符號進行說明：

B₀：供應商的初始庫存水平;

B_t為供應商在t期初的庫存水平;

h₀：供應商的單位庫存成本;

C_ij：點i（x_i，y_i）到點j（x_i，y_i）的運輸成本;

s：缺貨成本;

I_it：t期初需求點的實際庫存水平;

Archetti等[2]在2007年提出的IRP模型是同時考慮供應商和客戶的庫存，以供應商管理庫存為大背景，為整個供應鏈提供庫存路徑的解的混合整數規(guī)劃模型。本文結合文獻[3]將基礎模型進行改進并整合為模型（P）：

使得：

目標函數式（1）是最小化供應商庫存成本、需求點庫存成本、運輸成本缺貨成本之和;式（2）是需求預測函數;式（3）～式（5）是根據訂單水平策略結合需求預測函數進行改進的補貨政策;式（6）～式（8）說明庫存平衡;式（9）是車輛容量限制;式（10）要求每個周期內每位客戶最多被拜訪一次;式（11）表示每期每個節(jié)點和每臺車輛的度約束條件;式（12）是每期每個車輛路線和每期子回路消除約束的條件;式（13）～式（16）是相應的變量約束。

3算法流程詳解

3.1路線構建

在應急物資IRP中使用蟻群算法時，每只螞蟻從倉庫出發(fā)，通過增量選擇客戶來構建自己的路線，然后返回倉庫，增量選擇需求點的過程就是構建路線的過程。基于多周期，需要在每條邊上構造多維信息素信息，即在不同的周期，每條邊上有不同的信息素信息;搜索過程中需要維護多個信息素信息矩陣;信息素信息矩陣的數量等于規(guī)劃周期。

3，2改進初始解和鄰近解

本文在蟻群算法中引入單點交叉操作、變異操作和2-opt操作來探索搜索空間和防止過早陷入局部最優(yōu)。在交叉操作方面，本文引用文獻[4]構建的改進蟻群算法中單點交叉操作和兩點交叉操作。單點交叉操作是同一周期內兩個車輛路線之間的子路線交換程序。與遺傳算法中的單點交叉操作一樣，交叉操作可以獲得兩個新的路徑。變異操作參照文獻[5]提出的改進蟻群算法以預定的概率改變每個子代路線。該操作可以幫助ACO在搜索領域達成進一步的解決方案。變異操作的思想是隨機地變異這條路線，并因此產生一個新的解決方案，這個新的解決方案離最初的解決方案不遠。在本文中，變異算子以隨機方式進行點交換。2-opt是對一條路線內的點進行操作，嵌入在交叉操作和變異操作中;即為交叉（變異）操作步驟的第七步。在2-opt交換中，對每臺車訪問的所有可能的成對客戶位置交換進行測試，以查看是否可以實現目標函數的整體改進。

3.3信息素更新

信息素軌跡的更新是蟻群算法自適應學習技術和改進未來解的關鍵。信息素更新旨在使屬于好的解決方案的組件對于在后續(xù)迭代中操作的螞蟻來說更加理想。本文選用信息素軌跡蒸發(fā)，信息素軌跡隨著時間的推移減少先前螞蟻沉積的信息素的機制。

4算例分析

4.1實例數據構建及算法參數設置

實驗的模型和算法是在計算機軟件MATLAB 2017a中實現的，運行是在配置為Intel CORE九代i5-9300H，GTX1650 8G 的個人電腦上。

為了在后續(xù)的實驗中不僵化整個算法參數的設置，本文根據每個實例所包含的需求點個數合理地確定種群大小（一般種群大小等于需求點個數）;a在[0.5，0.9]之間取值，點數越多，a越小;B在[0.5，7]之間取值，點數越多，取值越大;信息素蒸發(fā)系數在[0.4，0.8]之間取值來提高算法效率，實例越大取值越低;達到最大迭代次數后停止迭代，輸出結果。最大迭代次數根據實例周期大小以及包含需求點個數綜合確定，最大迭代時間小于等于1 000 s。

4.2計算結果

本文對每一個實例都進行了5次計算，結果顯示：在H=3的情況下，需求點個數小于等于20個點的實例基本上5次計算都得到同一個結果，超過20個點的實例計算結果出現了上下波動的情況;說明改進蟻群算法能在3個周期20個點以內的實例中快速有效收斂到相對較好的解。但是在實例大于等于10個需求點后，計算結果就不穩(wěn)定了;說明周期變長會大大增加IRP模型的復雜度，使得問題變得更難求解。在計算時，可以很明顯地看出，需求影響常數對目標函數值的影響不太大。但是需要注意的是，這些實例都是在所有參數相對較小的情況下計算的;一旦參數陡增，會使計算變得更加復雜。

缺貨成本陡增的情況下，計算結果在3個周期大于等于10個點時就出現了差異，在6個周期中大于等于5個點時計算結果就出現波動;說明缺貨成本參數陡增同樣會大大增加IRP模型的復雜度，使得問題變得更難求解。缺貨成本的陡增對目標函數值的影響較大。綜合來看，缺貨成本的陡增不僅會增加計算難度，還會使目標函數值惡化。在缺貨成本較大的情況下，小實例的計算結果會因為庫存持有成本的增加而惡化。

5結論

應急物資一旦出現供需失衡，就會產生不可估量的后果，因此，必須要對應急物資進行有效并且高效的管理。本文建立了以預測需求為導向進行補貨的應急物資庫存路徑問題的模型，并通過改進的蟻群優(yōu)化算法對其進行求解;通過大量實例運算，表明了IRP運用于應急物流的可行性較好。本文通過各種實例計算后發(fā)現，模型中的有關參數會對計算結果和計算難度造成較大的影響：需求影響常數的增加對目標函數值沒有太大的影響，庫存持有成本的增加一般會增加目標函數值，缺貨成本的陡增不僅會增加目標函數值還會增加計算難度。因此，在進行NP-hard問題求解時，要考慮相關參數的設置情況。在實踐運用中，可以通過標準化參數或同時降低所有參數來降低計算復雜度。

現實生活中的應急管理問題往往更加復雜，本文建立的模型還不能很好地反映應急物流的特性。因此，后續(xù)關于應急物流庫存路徑問題可以考慮更多現實性的問題，比如涉及多種商品、易腐產品運輸的庫存路徑問題等;蟻群算法除了和遺傳算法進行結合外，還可以在結合遺傳算法的基礎上引入模擬退火公式避免過早陷入局部最優(yōu)。

參考文獻

[1] FEDERGRUEN A，ZIPKIN P. A combined vehicle routing and inventory allocation problem[J]. Operations Research，1984，32（5）：1019-1037.

[2] ARCHETTI C，BERTAZZI L，LAPORTE G，et al. A branch- and-cut algorithm for a vendor-managed inventory-routing problem[J]. Transportation Science，2007，41（3）：382-391.

[3] ARCHETTI C，BOLAND N，GRAZIA SPERANZA M. A matheuristic for the multivehicle inventory routing problem[J]. INFORMS Journal on Computing，2017，29（3）：377-387.

[4] YU B，YANG Z Z. An ant colony optimization model：The period vehicle routing problem with time windows[J]. Transportation Research Part E，2011，47（2）：166-181.

[5] YU B，YANG Z Z，YAO B Z. An improved ant colony optimization for vehicle routing problem[J]. European Journal of Operational Research，2009，196（1）：171-176.

Based on the Improving Algorithm of Ant Colony Optimization to Solve the Emergency Inventory Routing Problem

Zhou Dan，Qiu Yuzhuo

（School of Marketing and Logistics Management，Nanjing University of Finance and Economics，Nanjing，Jiangsu 210046）

Abstract：A model of emergency material inventory path problem based on forecast demand-oriented replenishment is established as a general model of emergency material inventory path problem. In this model，the predictive demand function is used as the basis for replenishment，so as to avoid the over-rigidity of replenishment due to the OU replenishment policy alone. The model is solved by improving the ant colony optimization algorithm，combining the crossover，variation and 2-opt operation in the ant colony optimization algorithm，avoiding the ant colony optimization algorithm falling into local optimality too early，expanding its search domain and improving the performance of the algorithm. Finally，the sensitivity and comparative analysis of the algorithm parameters and model parameters are carried out to determine the algorithm parameters of the example calculation，and to analyze the influence of the parameters in the model on the model and the solution.

Key words：emergency material，inventory routing，ant colony optimization，predict demand functions，replenishment strategy