基于Floyd算法和線性規(guī)劃的疫情防控物資配送方案

惠慶華，張恒運(yùn)，唐晨洋，楊夢(mèng)瑤，朱冠霖，胡修志，吳玉帥*

(1.青海省測(cè)試計(jì)算中心有限公司，青海 西寧 810001； 2.青海大學(xué)土木工程學(xué)院，青海 西寧 810016；3.青海大學(xué)水利電力學(xué)院，青海 西寧 810016; 4.青海大學(xué)生態(tài)環(huán)境工程學(xué)院，青海 西寧 810016；5.青海大學(xué)財(cái)經(jīng)學(xué)院，青海 西寧 810016)

2020年初新型冠狀病毒肺炎(COVID-19)的爆發(fā)給我國(guó)的物流行業(yè)帶來(lái)了很大影響[1]。疫情防控期間，防控物資運(yùn)輸需求明顯增加，特別是疫情嚴(yán)重地區(qū)對(duì)防控物資的需求在短時(shí)間內(nèi)大幅增加，解決防控物資的合理調(diào)配問(wèn)題顯得至關(guān)重要。保障運(yùn)輸過(guò)程中經(jīng)濟(jì)與速度之間的平衡，就是在最短運(yùn)輸路徑和最低成本之間找到一個(gè)合理的運(yùn)輸方案[2]。目前，關(guān)于配送最優(yōu)方案的研究較為廣泛，胡小宇等[3]利用粒子群算法求得了單倉(cāng)儲(chǔ)多車物流的配送問(wèn)題，并且設(shè)計(jì)了全新的粒子更新方法，并驗(yàn)證了該算法的有效性；周顯春等[4]針對(duì)現(xiàn)實(shí)的交通狀況，構(gòu)建了基于不同約束條件的最優(yōu)路徑評(píng)價(jià)模型；劉海洋等[5]在研究分析公交車道設(shè)置的基礎(chǔ)上，提出基于 Floyd 算法城市最短路徑的規(guī)劃，有效解決公交車道的最優(yōu)路徑。因?yàn)榻^大多數(shù)最短路徑規(guī)劃不僅僅局限于路徑規(guī)劃，還引申至其他度量，所以使用最頻繁的算法仍然是Floyd 算法[6]。當(dāng)前主要的最優(yōu)距離求解均為改進(jìn)的最優(yōu)解距離算法，而沒(méi)有將不同的算法進(jìn)行結(jié)合[7]。鑒于此，本文通過(guò)Floyd算法和線性規(guī)劃相結(jié)合的方式，以供給點(diǎn)到需求點(diǎn)的最短供給時(shí)間、最大運(yùn)輸量為目標(biāo)，使運(yùn)輸路徑和運(yùn)輸成本之間保持平衡，得到疫情防控物資配送的最佳運(yùn)輸方案。

1 問(wèn)題背景

某市(詳情見(jiàn)圖1)由于疫情爆發(fā)導(dǎo)致醫(yī)療物資及生活物資匱乏，為更好地解決問(wèn)題，某市政府有關(guān)部門希望建立數(shù)學(xué)模型，為突發(fā)情況對(duì)醫(yī)療物資及生活物資的配送問(wèn)題提供合理的運(yùn)輸方案。

圖1 某市地形簡(jiǎn)圖Fig.1 Topographic map of a city

圖1中各邊表示連接各縣市的公路，各邊的權(quán)值表示車輛通過(guò)該路段所需的時(shí)間?，F(xiàn)已知丁1、丁2、丁33個(gè)地區(qū)爆發(fā)疫情，每天所需要的防控物資量分別為60、40、25 t。能夠提供物資的地區(qū)有甲1～甲12，每天能提供物資的量分別為18、16、15、15、14、16、22、20、22、14、22、35 t，各供給地區(qū)提供物資的成本分別為3、2、4、3、2、4、2、3、5、3、4、4萬(wàn)元/t，在保證丁1、丁2、丁3每天物資供給充足的情況下，設(shè)計(jì)一種經(jīng)濟(jì)快速的物資運(yùn)輸方案。

通過(guò)分布圖利用Floyd算法求解12個(gè)支援城市到3個(gè)疫情爆發(fā)區(qū)的最短時(shí)間，另外，通過(guò)確定權(quán)重，對(duì)經(jīng)濟(jì)配送和時(shí)間配送之間可能存在的制約進(jìn)行分析，并建立綜合評(píng)價(jià)經(jīng)濟(jì)效益和時(shí)間效益的風(fēng)險(xiǎn)度模型，通過(guò)遍歷法求解權(quán)重，將建立的評(píng)價(jià)模型所得的函數(shù)作為線性規(guī)劃的目標(biāo)函數(shù)，得到最經(jīng)濟(jì)、快速的物資配送方案。

2 模型建立與求解

2.1 Floyd算法求解最短距離

Floyd算法(弗洛伊德算法)是解決兩點(diǎn)間最短路徑的一種算法，可正確處理無(wú)向圖或有向圖的最短路徑問(wèn)題，該算法又稱插點(diǎn)法。它是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法[8]。此算法三重循環(huán)結(jié)構(gòu)緊湊，簡(jiǎn)單有效，適用于多源最短路徑 (All Pairs Shortest Paths，APSP)，對(duì)于稠密圖效果最佳，邊權(quán)可正可負(fù)[9]，效率要高于執(zhí)行|V|次Dijkstra算法，也高于執(zhí)行|V|次SPFA算法。因此，在綜合考慮多種圖論算法的情況下選擇，F(xiàn)loyd算法對(duì)甲1～甲12到丁1～丁3之間的最短距離進(jìn)行求解。在本研究中，每條邊的權(quán)為一個(gè)地點(diǎn)到另一個(gè)地點(diǎn)的時(shí)間，可將圖1進(jìn)行標(biāo)號(hào)處理，得到以下結(jié)果(圖2)。

圖2 標(biāo)記順序后的某市地圖Fig.2 Map of a city after marking sequence

G為鄰接矩陣，G(i,j)元素是頂點(diǎn)i到點(diǎn)j之間的邊權(quán)，可以是有向的，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)重為無(wú)窮大。對(duì)于每一項(xiàng)頂點(diǎn)i和j，是否存在一個(gè)頂點(diǎn)k，使得從i到k再到j(luò)比已知的路徑更短，如式(1):

G[i][j]=min(G[i][j],G[i][k]+G[k][j])

(1)

如果G[i][j]的值變小，重新定義一個(gè)矩陣D用來(lái)記錄所插入點(diǎn)的信息，如式(2):

D[i][j]=k

(2)

下表是根據(jù)Floyd算法計(jì)算出來(lái)的甲1～甲12到丁1～丁3的最短距離。

表1 疫情區(qū)防控物資供應(yīng)最短距離Tab.1 Shortest distance of epidemic prevention materials supply in epidemic area

對(duì)最短距離進(jìn)行求解，得到36個(gè)結(jié)果，為了方便后續(xù)計(jì)算，這里將其列為1行36列的矩陣t，如式(3)：

t=[t1,t2,t3…t36]

(3)

式中：[t1,t2,t3…t12]代表甲1～甲12中每個(gè)地區(qū)到丁1的最短時(shí)間(最短距離)，[t13,t14,t15…t24]代表甲1～甲12中每個(gè)地區(qū)到丁2的最短時(shí)間，[t25,t26,t27…t36]代表甲1～甲12中每個(gè)地區(qū)到丁3的最短時(shí)間。

2.2 多目標(biāo)和線性規(guī)劃模型的建立與求解

本文的目標(biāo)是從可提供物資的縣市(甲1～甲12)向3個(gè)疫情爆發(fā)區(qū)(丁1～丁3)進(jìn)行支援時(shí)，得到一個(gè)經(jīng)濟(jì)快速的防控物資運(yùn)輸方案。對(duì)于運(yùn)輸過(guò)程而言，運(yùn)輸?shù)娘L(fēng)險(xiǎn)與單向運(yùn)輸?shù)某杀竞瓦\(yùn)輸?shù)竭_(dá)區(qū)域最短時(shí)間有關(guān)，且二者可能存在一定的相互制約現(xiàn)象。因此，本文建立相應(yīng)的線性規(guī)劃模型來(lái)分析運(yùn)輸風(fēng)險(xiǎn)，如式(4)：

R=Rtotal+Rtime

(4)

式中:R為整個(gè)運(yùn)輸過(guò)程中的風(fēng)險(xiǎn)，Rtotal為運(yùn)輸物資量的風(fēng)險(xiǎn)，Rtime為運(yùn)輸?shù)竭_(dá)區(qū)域最短時(shí)間的風(fēng)險(xiǎn)。

每個(gè)提供物資的區(qū)域可提供的最大值恒定，且提供物資的數(shù)量不會(huì)影響到達(dá)不同地區(qū)的時(shí)間，即提供物資的數(shù)量和到達(dá)時(shí)間相互獨(dú)立。在抗疫期間，物資到達(dá)時(shí)間的早晚對(duì)疫情防控工作更為重要，而經(jīng)濟(jì)上的成本更容易隨著政府的政策傾斜而被妥善解決，所以支援時(shí)間的權(quán)重更為關(guān)鍵，即支援時(shí)間的權(quán)重越大，就會(huì)產(chǎn)生更好的反響，反之會(huì)產(chǎn)生更大的風(fēng)險(xiǎn)。因此，本文將Rtime的權(quán)重設(shè)置為a(0≤a≤1)，Rtotal的權(quán)重設(shè)置為b(0≤b≤1)，從而得出以下線性規(guī)劃風(fēng)險(xiǎn)度評(píng)價(jià)模型，如式(5)：

(5)

將運(yùn)輸物資量的風(fēng)險(xiǎn)和到達(dá)區(qū)域最短時(shí)間的風(fēng)險(xiǎn)進(jìn)行量化，運(yùn)輸物資量的風(fēng)險(xiǎn)主要為運(yùn)輸成本的風(fēng)險(xiǎn)。

這里設(shè)xi表示從i地區(qū)支援到丁1～丁3地區(qū)所需物資的數(shù)量，其中i表示甲位置，i=1,2,3…12。由于目的地分別為丁1、丁2、丁3，從i地區(qū)支援目的地共有3種情況：x(1,i)=(x1,x2,x3…x12)，代表甲1～甲12中每個(gè)地區(qū)到丁1的物資供給量；x(1,i+12)=(x13,x14,x15…x24)，代表甲1～甲12中每個(gè)地區(qū)到丁2的物資供給量；x(1,i+24)=(x25,x26,x27…x36)，代表甲1～甲12中每個(gè)地區(qū)到丁3的物資供給量。

成本風(fēng)險(xiǎn)以運(yùn)輸成本表示，則為運(yùn)輸噸數(shù)與每噸成本之積，即式(6)：

Rtotal=[x(1,i)+x(1,i+12)+x(1,i+24)]m(i)

(6)

式中：m(i)為每噸運(yùn)輸成本。

此外，將到達(dá)區(qū)域最短時(shí)間的風(fēng)險(xiǎn)量化為該時(shí)間下的運(yùn)輸量總量。在保證經(jīng)濟(jì)的情況下，為了盡快到達(dá)支援目的地應(yīng)既要保證盡快運(yùn)送，又要保證運(yùn)送的量合適，達(dá)到經(jīng)濟(jì)效益的最大化，見(jiàn)式(7)：

Rtime=xit

(7)

其中：t為運(yùn)輸時(shí)間。

在考慮風(fēng)險(xiǎn)度的情況下，由于本文著重考慮Rtime帶來(lái)的影響，認(rèn)為Rtime的增加和減少會(huì)帶來(lái)更多的客觀影響，并沒(méi)有著重考慮二者之間的制約；但是考慮在實(shí)際運(yùn)輸過(guò)程中，Rtime和Rtotal之間存在著相互制約，且運(yùn)輸方案更偏向于經(jīng)濟(jì)和速度的平衡，因此在通過(guò)風(fēng)險(xiǎn)度求解權(quán)重的情況下，建立線性運(yùn)輸模式代價(jià)模型，如式(8)：

C=bRtotal+a2Rtime

(8)

式中：C代表不同運(yùn)輸方式所需的代價(jià)。

基于丁1～丁3每天所需的物資及甲1～甲12可運(yùn)送的有限最大物資量，建立相應(yīng)的邊界條件，對(duì)物資運(yùn)輸進(jìn)行線性規(guī)劃。

丁1～丁3每天所需的物資量約束條件如式(9)：

(9)

甲1～甲12可運(yùn)輸?shù)淖畲笪镔Y量的約束條件如式(10)：

(10)

3 結(jié)果與分析

通過(guò)建立線性規(guī)劃風(fēng)險(xiǎn)度評(píng)價(jià)模型，對(duì)權(quán)重a、b進(jìn)行遍歷選取，從而得到風(fēng)險(xiǎn)最低的權(quán)重。通過(guò)Matlab R2017對(duì)b權(quán)重以0.01的步長(zhǎng)進(jìn)行遍歷分析，得到各個(gè)權(quán)重下的所有風(fēng)險(xiǎn)度值，再通過(guò)origin將風(fēng)險(xiǎn)度值進(jìn)行可視化(圖3)，從而得到步長(zhǎng)為0.01權(quán)重，b在0～1范圍內(nèi)的所有風(fēng)險(xiǎn)度數(shù)值。當(dāng)權(quán)重b為0.81時(shí)，風(fēng)險(xiǎn)度298.2為最小風(fēng)險(xiǎn)值，由式(5)可得到此時(shí)權(quán)重a為0.19。因此，在考慮風(fēng)險(xiǎn)度的過(guò)程中，權(quán)重a=0.19，b=0.81時(shí)所得到的風(fēng)險(xiǎn)值最低，然后將風(fēng)險(xiǎn)度最低的權(quán)重代入求解不同分配模式的代價(jià)模型，得到線性規(guī)劃的目標(biāo)函數(shù)為:

圖3 權(quán)重風(fēng)險(xiǎn)度可視化圖像Fig.3 Visualization image of weight risk

C=0.81Rtotal+0.192Rtime

(11)

在風(fēng)險(xiǎn)度最低為298.2的情況下，將該風(fēng)險(xiǎn)下的權(quán)重代入運(yùn)輸模式代價(jià)模型，得到疫情防控物資運(yùn)輸分配結(jié)果(表2)。

表2 防控物資運(yùn)輸分配結(jié)果Tab.2 Distribution scheme of epidemic prevention materials

由表2可知，甲1向丁1運(yùn)輸18 t物資；甲2向丁1運(yùn)輸16 t物資；甲3向丁2運(yùn)輸6 t物資；甲4向丁1運(yùn)輸12 t物資，向丁3運(yùn)輸3 t物資；甲5向丁1運(yùn)輸14 t物資；甲6不運(yùn)輸；甲7向丁2運(yùn)輸14 t物資，向丁3運(yùn)輸8 t物資；甲8向丁2運(yùn)輸20 t物資；甲10向丁3運(yùn)輸14 t物資；甲9、甲11和甲12不進(jìn)行運(yùn)輸?shù)哪Ｊ?，能達(dá)到經(jīng)濟(jì)快速地運(yùn)輸防控物資的目的。

4 討論與結(jié)論

本文通過(guò)Floyd算法和線性規(guī)劃模型的結(jié)合，引入運(yùn)輸模式代價(jià)的理念尋找相應(yīng)的權(quán)重，得到了風(fēng)險(xiǎn)度最低值及相應(yīng)的分配模式。采用以K-means算法為主的“聚類算法”進(jìn)行物資調(diào)配[10]時(shí)，不能分析調(diào)配物資量與風(fēng)險(xiǎn)度之間的關(guān)系；傳統(tǒng)的優(yōu)化算法[11]進(jìn)行物資調(diào)配策略運(yùn)行時(shí)，需要在事件爆發(fā)的瞬間就做好應(yīng)急處理，對(duì)從未接觸過(guò)的突發(fā)狀況而言存在很大的漏洞。而本研究的模型簡(jiǎn)單、易搭建，可快速進(jìn)行最短路徑規(guī)劃。

本研究得出，當(dāng)運(yùn)輸時(shí)間的權(quán)重為0.19，運(yùn)輸總量的權(quán)重為0.81時(shí)，可得到最低風(fēng)險(xiǎn)度數(shù)值298.2，運(yùn)輸方案為甲1向丁1運(yùn)輸18 t物資；甲2向丁1運(yùn)輸16 t物資；甲3向丁2運(yùn)輸6 t物資；甲4向丁1運(yùn)輸12 t物資，向丁3運(yùn)輸3 t物資；甲5向丁1運(yùn)輸14 t物資；甲6不運(yùn)輸；甲7向丁2運(yùn)輸14 t物資，向丁3運(yùn)輸8 t物資；甲8向丁2運(yùn)輸20 t物資；甲10向丁3運(yùn)輸14 t物資，甲11和甲12不進(jìn)行運(yùn)輸。可見(jiàn)，在多種情況下，如果要保證時(shí)間和成本平衡，并不代表對(duì)需要支援的城市均給予相應(yīng)的援助，最好的方案是“就近支援”，即每個(gè)城市支援最近的區(qū)域，就能保障運(yùn)輸成本與速度。同時(shí)，本模型也存在著不足，沒(méi)有考慮到在運(yùn)輸途中可能出現(xiàn)的意外事件等小概率問(wèn)題，只考慮了運(yùn)輸時(shí)間和運(yùn)輸成本兩個(gè)因素來(lái)分析風(fēng)險(xiǎn)度，導(dǎo)致模型并不完善。此外，對(duì)“經(jīng)濟(jì)快速”的定義只限于成本和時(shí)間這兩個(gè)因素，沒(méi)有考慮其他因素，導(dǎo)致分析的結(jié)果趨于單一化。因此，得出的結(jié)果仍然需要全方位改進(jìn)。