曲貝貝 王效俐

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

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.

關(guān)鍵詞：疫情應(yīng)急物資;蟻群算法;路徑優(yōu)化;變異因子

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

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

0? 引言

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

1? 蟻群算法簡介

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

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

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

2? 模型建立

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

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

2.2 數(shù)學(xué)模型

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

2.2.2 參數(shù)設(shè)置

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

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

用C 表示配送總距離，目標(biāo)函數(shù)下：

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

表示每個醫(yī)院的時間窗懲罰值。

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

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

3? 數(shù)據(jù)分析

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

3.2 參數(shù)自適應(yīng)變化? 在ACO_2算法基礎(chǔ)上，加入?yún)?shù)的自適應(yīng)變化，具體如下所示：

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

在以上初始參數(shù)設(shè)置下，ACO_2算法的算法收斂軌跡和求解結(jié)果如圖4（a）、（b）所示?？梢钥吹?，算法在第700多次迭代后達到局部最優(yōu)，同時其總目標(biāo)函數(shù)值為93.0285，比之前得到的95.476有一定優(yōu)化。這說明加入?yún)?shù)的自適應(yīng)變化是可行的。在此基礎(chǔ)上我們對表4中的六個參數(shù)進行參數(shù)調(diào)整，以求得更好的結(jié)果。

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

4? 研究總結(jié)

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

參考文獻：

[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].計算機工程與應(yīng)用，2019，55（08）：244-249.

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

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

[7]張云川，鄒婷.生鮮食品冷鏈物流配送路徑優(yōu)化[J].江蘇農(nóng)業(yè)科學(xué)，2019，47（03）：315-319.

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

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