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

惠慶華，張恒運，唐晨洋，楊夢瑤，朱冠霖，胡修志，吳玉帥*

(1.青海省測試計算中心有限公司，青海 西寧 810001； 2.青海大學土木工程學院，青海 西寧 810016；3.青海大學水利電力學院，青海 西寧 810016; 4.青海大學生態環境工程學院，青海 西寧 810016；5.青海大學財經學院，青海 西寧 810016)

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

1 問題背景

某市(詳情見圖1)由于疫情爆發導致醫療物資及生活物資匱乏，為更好地解決問題，某市政府有關部門希望建立數學模型，為突發情況對醫療物資及生活物資的配送問題提供合理的運輸方案。

圖1 某市地形簡圖Fig.1 Topographic map of a city

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

通過分布圖利用Floyd算法求解12個支援城市到3個疫情爆發區的最短時間，另外，通過確定權重，對經濟配送和時間配送之間可能存在的制約進行分析，并建立綜合評價經濟效益和時間效益的風險度模型，通過遍歷法求解權重，將建立的評價模型所得的函數作為線性規劃的目標函數，得到最經濟、快速的物資配送方案。

2 模型建立與求解

2.1 Floyd算法求解最短距離

Floyd算法(弗洛伊德算法)是解決兩點間最短路徑的一種算法，可正確處理無向圖或有向圖的最短路徑問題，該算法又稱插點法。它是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法[8]。此算法三重循環結構緊湊，簡單有效，適用于多源最短路徑 (All Pairs Shortest Paths，APSP)，對于稠密圖效果最佳，邊權可正可負[9]，效率要高于執行|V|次Dijkstra算法，也高于執行|V|次SPFA算法。因此，在綜合考慮多種圖論算法的情況下選擇，Floyd算法對甲1～甲12到丁1～丁3之間的最短距離進行求解。在本研究中，每條邊的權為一個地點到另一個地點的時間，可將圖1進行標號處理，得到以下結果(圖2)。

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

G為鄰接矩陣，G(i,j)元素是頂點i到點j之間的邊權，可以是有向的，如果兩點之間沒有邊相連，則權重為無窮大。對于每一項頂點i和j，是否存在一個頂點k，使得從i到k再到j比已知的路徑更短，如式(1):

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

(1)

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

D[i][j]=k

(2)

下表是根據Floyd算法計算出來的甲1～甲12到丁1～丁3的最短距離。

表1 疫情區防控物資供應最短距離Tab.1 Shortest distance of epidemic prevention materials supply in epidemic area

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

t=[t1,t2,t3…t36]

(3)

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

2.2 多目標和線性規劃模型的建立與求解

本文的目標是從可提供物資的縣市(甲1～甲12)向3個疫情爆發區(丁1～丁3)進行支援時，得到一個經濟快速的防控物資運輸方案。對于運輸過程而言，運輸的風險與單向運輸的成本和運輸到達區域最短時間有關，且二者可能存在一定的相互制約現象。因此，本文建立相應的線性規劃模型來分析運輸風險，如式(4)：

R=Rtotal+Rtime

(4)

式中:R為整個運輸過程中的風險，Rtotal為運輸物資量的風險，Rtime為運輸到達區域最短時間的風險。

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

(5)

將運輸物資量的風險和到達區域最短時間的風險進行量化，運輸物資量的風險主要為運輸成本的風險。

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

成本風險以運輸成本表示，則為運輸噸數與每噸成本之積，即式(6)：

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

(6)

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

此外，將到達區域最短時間的風險量化為該時間下的運輸量總量。在保證經濟的情況下，為了盡快到達支援目的地應既要保證盡快運送，又要保證運送的量合適，達到經濟效益的最大化，見式(7)：

Rtime=xit

(7)

其中：t為運輸時間。

在考慮風險度的情況下，由于本文著重考慮Rtime帶來的影響，認為Rtime的增加和減少會帶來更多的客觀影響，并沒有著重考慮二者之間的制約；但是考慮在實際運輸過程中，Rtime和Rtotal之間存在著相互制約，且運輸方案更偏向于經濟和速度的平衡，因此在通過風險度求解權重的情況下，建立線性運輸模式代價模型，如式(8)：

C=bRtotal+a2Rtime

(8)

式中：C代表不同運輸方式所需的代價。

基于丁1～丁3每天所需的物資及甲1～甲12可運送的有限最大物資量，建立相應的邊界條件，對物資運輸進行線性規劃。

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

(9)

甲1～甲12可運輸的最大物資量的約束條件如式(10)：

(10)

3 結果與分析

通過建立線性規劃風險度評價模型，對權重a、b進行遍歷選取，從而得到風險最低的權重。通過Matlab R2017對b權重以0.01的步長進行遍歷分析，得到各個權重下的所有風險度值，再通過origin將風險度值進行可視化(圖3)，從而得到步長為0.01權重，b在0～1范圍內的所有風險度數值。當權重b為0.81時，風險度298.2為最小風險值，由式(5)可得到此時權重a為0.19。因此，在考慮風險度的過程中，權重a=0.19，b=0.81時所得到的風險值最低，然后將風險度最低的權重代入求解不同分配模式的代價模型，得到線性規劃的目標函數為:

圖3 權重風險度可視化圖像Fig.3 Visualization image of weight risk

C=0.81Rtotal+0.192Rtime

(11)

在風險度最低為298.2的情況下，將該風險下的權重代入運輸模式代價模型，得到疫情防控物資運輸分配結果(表2)。

表2 防控物資運輸分配結果Tab.2 Distribution scheme of epidemic prevention materials

由表2可知，甲1向丁1運輸18 t物資；甲2向丁1運輸16 t物資；甲3向丁2運輸6 t物資；甲4向丁1運輸12 t物資，向丁3運輸3 t物資；甲5向丁1運輸14 t物資；甲6不運輸；甲7向丁2運輸14 t物資，向丁3運輸8 t物資；甲8向丁2運輸20 t物資；甲10向丁3運輸14 t物資；甲9、甲11和甲12不進行運輸的模式，能達到經濟快速地運輸防控物資的目的。

4 討論與結論

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

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