基于改進(jìn)蟻群優(yōu)化算法求解應(yīng)急物資庫(kù)存路徑問題

周丹 邱玉琢

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

關(guān)鍵詞：應(yīng)急物資;庫(kù)存路徑;蟻群優(yōu)化;預(yù)測(cè)需求函數(shù);補(bǔ)貨策略

中圖分類號(hào)：O227文獻(xiàn)標(biāo)識(shí)碼：ADOI：10.16465/j.gste.cn431252ts.20210617

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

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

目前IRP文獻(xiàn)中的供應(yīng)商的補(bǔ)貨政策最常見的是訂單至最大庫(kù)存水平策略（Order-up-to-level policy，OU策略）[3]。OU政策可以闡釋為：如果在一個(gè)周期訪問了一個(gè)零售商，則運(yùn)送給該零售商的產(chǎn)品數(shù)量要使該零售商的庫(kù)存水平達(dá)到其最大庫(kù)存水平。OU補(bǔ)貨策略是一種非常受歡迎，已經(jīng)在許多IRP文獻(xiàn)中使用;但它同時(shí)又是相當(dāng)僵化的庫(kù)存管理策略;而更靈活的補(bǔ)貨政策可能會(huì)產(chǎn)生大量的庫(kù)存費(fèi)用。本文將以預(yù)測(cè)需求為導(dǎo)向，結(jié)合OU補(bǔ)貨策略對(duì)各個(gè)需求點(diǎn)進(jìn)行補(bǔ)貨。

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

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

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

1問題描述

2應(yīng)急物資庫(kù)存路徑模型

在給出基本的IRP模型之前，首先對(duì)模型中的其他相關(guān)符號(hào)進(jìn)行說明：

B₀：供應(yīng)商的初始庫(kù)存水平;

B_t為供應(yīng)商在t期初的庫(kù)存水平;

h₀：供應(yīng)商的單位庫(kù)存成本;

C_ij：點(diǎn)i（x_i，y_i）到點(diǎn)j（x_i，y_i）的運(yùn)輸成本;

s：缺貨成本;

I_it：t期初需求點(diǎn)的實(shí)際庫(kù)存水平;

Archetti等[2]在2007年提出的IRP模型是同時(shí)考慮供應(yīng)商和客戶的庫(kù)存，以供應(yīng)商管理庫(kù)存為大背景，為整個(gè)供應(yīng)鏈提供庫(kù)存路徑的解的混合整數(shù)規(guī)劃模型。本文結(jié)合文獻(xiàn)[3]將基礎(chǔ)模型進(jìn)行改進(jìn)并整合為模型（P）：

使得：

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

3算法流程詳解

3.1路線構(gòu)建

在應(yīng)急物資IRP中使用蟻群算法時(shí)，每只螞蟻從倉(cāng)庫(kù)出發(fā)，通過增量選擇客戶來構(gòu)建自己的路線，然后返回倉(cāng)庫(kù)，增量選擇需求點(diǎn)的過程就是構(gòu)建路線的過程?；诙嘀芷?，需要在每條邊上構(gòu)造多維信息素信息，即在不同的周期，每條邊上有不同的信息素信息;搜索過程中需要維護(hù)多個(gè)信息素信息矩陣;信息素信息矩陣的數(shù)量等于規(guī)劃周期。

3，2改進(jìn)初始解和鄰近解

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

3.3信息素更新

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

4算例分析

4.1實(shí)例數(shù)據(jù)構(gòu)建及算法參數(shù)設(shè)置

實(shí)驗(yàn)的模型和算法是在計(jì)算機(jī)軟件MATLAB 2017a中實(shí)現(xiàn)的，運(yùn)行是在配置為Intel CORE九代i5-9300H，GTX1650 8G 的個(gè)人電腦上。

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

4.2計(jì)算結(jié)果

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

缺貨成本陡增的情況下，計(jì)算結(jié)果在3個(gè)周期大于等于10個(gè)點(diǎn)時(shí)就出現(xiàn)了差異，在6個(gè)周期中大于等于5個(gè)點(diǎn)時(shí)計(jì)算結(jié)果就出現(xiàn)波動(dòng);說明缺貨成本參數(shù)陡增同樣會(huì)大大增加IRP模型的復(fù)雜度，使得問題變得更難求解。缺貨成本的陡增對(duì)目標(biāo)函數(shù)值的影響較大。綜合來看，缺貨成本的陡增不僅會(huì)增加計(jì)算難度，還會(huì)使目標(biāo)函數(shù)值惡化。在缺貨成本較大的情況下，小實(shí)例的計(jì)算結(jié)果會(huì)因?yàn)閹?kù)存持有成本的增加而惡化。

5結(jié)論

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

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

參考文獻(xiàn)

[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