新冠疫情期間應急物資配送路徑優化研究

曲貝貝 王效俐

摘要：疫情期間保證應急物資的配送是嚴防嚴控的重要環節，考慮到新冠疫情傳染性強且具一定致死率，新冠應急物資在配送方面應注重時效性。在滿足載重量和需求量以及盡可能滿足時間窗要求的基礎上建立基于變異蟻群算法的物流配送路徑優化模型，并通過實例驗證算法可行性。從求解過程和結果來看本研究提出的模型和算法找到的路徑是較優的。

Abstract： Ensuring the distribution of emergency materials during the epidemic is an important part to control the epidemic. Timeliness should be paid attention to in the distribution of emergency supplies considering to highly contagious and lethal of the COVID-19 epidemic. To meet the time window requirements as much as possible， a logistics distribution route optimization model based on the mutation ant colony algorithm is established， and the feasibility of the algorithm is verified through examples. From the results， the path found by the model and algorithm proposed in this study is better.

關鍵詞：疫情應急物資;蟻群算法;路徑優化;變異因子

Key words： epidemic emergency supplies;ant colony algorithm;path optimization;mutation factor

中圖分類號：R197.32? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2020）31-0099-04

0? 引言

2019年12月以來，湖北省武漢市發現多起不明原因肺炎，現已證實為一種新型冠狀病毒感染引起的急性呼吸道傳染病。新冠病毒的傳染力較強，根據世衛組織的數據，新冠病毒的基本再生數（R0）在1.4-2.5之間（有資料統計為1.4-5.5）。這意味著，平均每個新冠病毒確診病例會感染1.4-2.5（或5.5）個人[1]。同時，新冠病毒具一定致死率，截至9月29日全球確診病例數高達3346萬，死亡病例數高達100萬，致死率約在3%遠高于普通流感[2]。新冠疫情暴發后，全國應急物資運輸保障中出現了運輸通道受阻、應急物資分撥不暢等問題，導致生活物資和必要的醫療物資出現供需失衡的問題。疫情的特殊性使得生活醫療物資的配送具有一定的時效性，可認為品質和時間呈負相關，因此改進物流配送，尋求最優的物流配送路徑，提高配送效率和準時性是保證新冠期間物資配送的重要研究方面。9月26日的第二屆海峽兩岸國際醫療與特需服務發展大會上，張文宏表示以現在疫情蔓延態勢來講，新冠病毒已經變成“常駐病毒”，全球疫情發展至今，隨時有可能出現一個“小火花”，即局部性的疫情小爆發。這意味著我們應當隨時對局部性疫情爆發做好準備，一旦出現疫情增長勢頭，迅速采取防控措施，同時保證相關醫療生活物資及時供應，以消除疫情擴散可能[3]。本文的研究將針對新冠期間應急物品配送車輛從物資配送中心到各個醫院的路徑進行優化研究。研究的目的在于改進物流配送從中心倉庫到各醫院的環節，在滿足醫療需求的條件下，尋求最優配送路徑。

1? 蟻群算法簡介

蟻群算法是由意大利學者Dorigo、Maniezzo等人于20世紀90年代首先提出來的。他們發現蟻群可以通過釋放“信息素（pheromone）”找到最短到達食物源的路徑，這即是蟻群算法。如果在給定點，一只螞蟻要在不同的路徑中選擇，那么，那些被先行螞蟻大量選擇的路徑（也就是信息素越濃的路徑）被選中的概率就越大，信息素越濃意味著路徑越短，也就意味著找到了一個更好的解。

蟻群算法在解決問題上主要有以下的優點：①蟻群算法與其他啟發式算法相比，在求解性能上，具有很強的魯棒性。②對算法模型稍加修改，便可以應用于其他問題，具有搜索較好解的能力。③蟻群算法是一種基于種群的進化算法，具有本質并行性，易于并行實現[4]。

變異是遺傳算法中一個重要的過程，變異運算用來模擬生物在自然的遺傳環境中由于各種偶然因素引起的基因突變，我們在這里中引入變異操作，使得螞蟻在初始基因組合以外的空間進行搜索，避免進化過程在早期就陷入局部解而進入終止過程，使之在盡可能大的空間中獲得質量較高的優化解[5，6]。

2? 模型建立

2.1 數據收集? 本文的研究收集了10個配送點的位置坐標，需求量，配送的時間窗，可接受時間窗和卸貨所需要的時間數據。如表1和表2所示。

由于配送點對于疫情應急物資具有時間窗要求，并且時間窗分為要求時間窗和可接受時間窗。為了滿足時間窗要求，本文在研究中對配送時間引入懲罰值。如果配送車輛在要求時間范圍內到達，則懲罰值為0，如果配送車輛超出要求時間但是在可接受時間范圍內到達，則懲罰值和時間之間呈線性相關[7]，如圖1所示。

2.2 數學模型

2.2.1 模型假設? 在構建配送的數學模型之前，對配送點的需求量，車輛的運行路線，車速，載重量等相關條件進行如下假設：①單一配送中心，配送中心的總貨量大于所有醫院的需求量;②車輛從配送中心出發，完成任務后返回配送中心;③已知醫院量、需求量、地理位置及時間窗;④每個醫院每日僅被配送1次，所有醫院都能得到配送;⑤車輛勻速行駛，速度為60km/h;⑥車輛只負責送貨，即單向物品流向;⑦所有醫院所需商品都由配送中心供給，醫院之間不存在相互調劑的情況;⑧各醫院的需求量確定，并在一定時期內相對穩定;⑨冷藏車所載貨物的質量不超過其載重量[8]。

2.2.2 參數設置

qi：醫院i的需求量;D：表示冷藏車輛的載重量;dij：表示任意2個醫院i、j之間的距離;Rkr：表示第r條路徑上第k個醫院的編號;ti：表示到達醫院i的時刻，i∈N;ti1：表示醫院i可接受時間窗的前一個時刻，i∈N;ti2：表示醫院i可接受時間窗的后一個時刻，i∈N;Vi：醫院i的時間窗處罰值，i∈N;Li：表示醫院i的卸貨時間，i∈N。

2.2.3 約束條件? 考慮到新冠疫情的傳染風險，在應急物資配送過程中每個配送點只配送一次，不存在多次配送最后總的配送量達到需求量的情況。車輛行駛的路徑的起點和終點均為配送中心。最后使得配送路程的總距離和時間窗懲罰值最小[9]。

用C 表示配送總距離，目標函數下：

約束條件如下：yi=1，i∈N表示每個醫院只被服務1次;xij=0，i=j∈N表示不能重復服務同一醫院;表示到達連續服務的2個醫院時刻的遞推關系;保證冷藏車到達醫院的時刻滿足醫院可接受的時間窗;表示每條路徑的出發點和終點均為配送中心;

表示每個醫院的時間窗懲罰值。

2.3 研究模型? 針對該配送問題采用混合蟻群算法，結合蟻群算法和遺傳算法，在蟻群算法的基礎上，增加遺傳算法中的變異算子，同時增加參數自適應，以避免陷入局部最優。

具體模型如圖2所示。首先進行初始化，在每一次迭代中，產生m只螞蟻，對于每只螞蟻，判斷其是否遍歷所有城市，如果沒有，計算城市間轉移概率，選取下一個訪問城市，判斷是否滿足載重量約束，若不滿足，則返回城市1，重新計算概率選取城市，若是滿足約束，則前往下一個城市，并更新禁忌表，如果遍歷了所有城市，對結果進行變異操作，計算變異后的路線對應的目標函數值，如果新路線優于原路線，則采用新路線，若不優于，則放棄變異結果，再更新信息素，進行參數自適應。當所有螞蟻完成后，增加迭代次數，循環操作，直至迭代次數達到最大迭代次數，然后輸出結果。模型如圖2所示。

3? 數據分析

3.1 初始參數條件算法求解結果? 為驗證算法的有效性，本研究將算法使用matlab實現，模型中的初始相關參數見表3。參數優化的目標是使時間窗懲罰成本和配送路徑之和的總目標函數值最小。在初始參數設置下，得到的實現結果如圖3所示。從圖3（a）可以看到，使用傳統蟻群算法（ACO_1算法）解決本研究問題時容易過早地陷入局部最優，導致目標函數值偏大，未能得到滿意解。因此，我們在蟻群算法基礎上加入了遺傳算法中的變異因子（ACO_2算法），從圖3（b）和（d）可以看到，加入遺傳因子后，算法收斂軌跡和總目標函數值均得到一定改善。因此本研究在ACO_2算法基礎上進行改進和參數調整。

3.2 參數自適應變化? 在ACO_2算法基礎上，加入參數的自適應變化，具體如下所示：

在每一次迭代計算后，α、β、ρ這三個參數都會發生自適應變化，其中alphac，betac，volc為自適應變化參數。初始自適應變化參數設置如表4所示。

在以上初始參數設置下，ACO_2算法的算法收斂軌跡和求解結果如圖4（a）、（b）所示。可以看到，算法在第700多次迭代后達到局部最優，同時其總目標函數值為93.0285，比之前得到的95.476有一定優化。這說明加入參數的自適應變化是可行的。在此基礎上我們對表4中的六個參數進行參數調整，以求得更好的結果。

3.3 參數調整? 本研究整體參數調整思路為調整α、β、ρ三個參數以及其變化范圍的大小，使其總目標函數值盡可能小。通過控制變量法進行參數調整，經過多次試驗，發現較優的參數設置如表5所示。在以上較優參數設置下，ACO_2算法的算法收斂軌跡和求解結果如圖5（a）、（b）所示。從圖5可以看到，算法在第700多次迭代后達到局部最優，同時其總目標函數值為87.231，比之前得到的93.0285有大幅度的優化。因此，得到的較優配送方案為：：1-10-8-3-2-1-7-4-11-5-9-1-6-1。

4? 研究總結

本研究分析了疫情應急物資的配送路徑優化問題。在滿足載重量和需求量以及盡可能滿足時間窗要求的基礎上，建立了以配送路徑距離和時間窗懲罰函數值最小為目標建立了考慮時間窗的的物流配送路徑優化模型，設計了結合變異算子的混合的蟻群優化算法進行求解。通過一個實例驗證了算法的可行性。從求解過程和結果來看可以保證本研究提出的模型和算法找到的路徑是較優的。

參考文獻：

[1]https：//wiki.antpedia.com/n-2355530-news？from=groupmessage&isappinstalled=0.

[2]https：//baijiahao.baidu.com/s？id=1679124835319072461&wfr

=spider&for=pc.

[3]https：//www.huashan.org.cn/ne ws/detail/10518.html.

[4]蔣麗，王靜，梁昌勇.基于改進蟻群算法的眾包配送路徑研究[J].計算機工程與應用，2019，55（08）：244-249.

[5]趙琨，史艷華，史曉霞.基于遺傳算法的即時配送路徑優化研究[J].現代商貿工業，2019，40（05）：31-32.

[6]陳成.基于改進遺傳算法的物流車輛路徑問題優化[J].信息技術與信息化，2018，09（10）：41-43.

[7]張云川，鄒婷.生鮮食品冷鏈物流配送路徑優化[J].江蘇農業科學，2019，47（03）：315-319.

[8]魏凱.改進遺傳算法在軟時間窗車輛路徑問題中的應用[D].安徽工業大學，2013.

[9]李汝佳.基于蟻群算法的旅游路線規劃問題研究[J].電腦知識與技術，2019，15（8）：137-140.