新冠疫情期間應(yīng)急物資配送路徑優(yōu)化研究

曲貝貝 王效俐

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

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

0? 引言

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

1? 蟻群算法簡介

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

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

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

2? 模型建立

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 參數(shù)調(diào)整? 本研究整體參數(shù)調(diào)整思路為調(diào)整α、β、ρ三個(gè)參數(shù)以及其變化范圍的大小，使其總目標(biāo)函數(shù)值盡可能小。通過控制變量法進(jìn)行參數(shù)調(diào)整，經(jīng)過多次試驗(yàn)，發(fā)現(xiàn)較優(yōu)的參數(shù)設(shè)置如表5所示。在以上較優(yōu)參數(shù)設(shè)置下，ACO_2算法的算法收斂軌跡和求解結(jié)果如圖5（a）、（b）所示。從圖5可以看到，算法在第700多次迭代后達(dá)到局部最優(yōu)，同時(shí)其總目標(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)化問題。在滿足載重量和需求量以及盡可能滿足時(shí)間窗要求的基礎(chǔ)上，建立了以配送路徑距離和時(shí)間窗懲罰函數(shù)值最小為目標(biāo)建立了考慮時(shí)間窗的的物流配送路徑優(yōu)化模型，設(shè)計(jì)了結(jié)合變異算子的混合的蟻群優(yōu)化算法進(jìn)行求解。通過一個(gè)實(shí)例驗(yàn)證了算法的可行性。從求解過程和結(jié)果來看可以保證本研究提出的模型和算法找到的路徑是較優(yōu)的。

參考文獻(xiàn)：

[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ìn)蟻群算法的眾包配送路徑研究[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（08）：244-249.

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

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

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

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

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