劉蘇晴

摘要：隨著我國5G技術的高速發(fā)展，相較于以往的車輛運輸，無人機在路面交通不暢的災后現(xiàn)場配送能夠有效降低災區(qū)人員傷亡及財產損失，但同時其具有負載小、成本高等短板。因此配送車量與無人機聯(lián)合配送模式下的路徑優(yōu)化問題將是研究重點。在滿足車輛載重、無人機飛行距離和無人機載重的約束條件下，將完成一次整體配送所需時間作為衡量因素，建立分別在“配送車輛”運輸模式和“配送車輛-無人機”運輸模式下的最優(yōu)路徑模型對模型進行求解。

關鍵詞：VRP模型；FSTSP模型；選址問題；K-means聚類算法；遺傳算法

一、前言

近年來，國內外相關文獻主要集中于數學建模和分配模型的求解優(yōu)化兩個方面。顏瑞[1]等根據車輛限行和空域禁飛的情況，將區(qū)域限制因素嵌入到模型的構建當中。彭勇[2]等在疫情背景下，以配送商品時間最短為優(yōu)化目標，設計混合鄰域搜索算法求解無人機為多個客戶無接觸配送的路徑問題。為進一步求解數學模型，許多數學者均采用改進的優(yōu)化算法進行求解。王新[3]等為提高客戶的滿意度，綜合考慮無人機站點和客戶時間窗要求，建立以總成本最小化為目標的問題模型，并設計自適應大規(guī)模鄰域搜索算法進行求解。鄧永蕤[4]等在自然災害情境下建立配送車量與無人機聯(lián)合配送冷鏈物流優(yōu)化模型，采用進化逆轉操作，并設計改進的遺傳算法。李妍峰[5]等改進變鄰域搜索算法求解需求可拆分的路徑問題。曹英英[6]等利用遺傳模擬退火兩階段算法求解集群下的配送車量與無人機聯(lián)合配送問題。分為兩步提出新型優(yōu)化迭代算法進行路線的規(guī)劃。

基于此，我們建立分別在“配送車輛”運輸模式和“配送車輛—無人機”運輸模式下的最優(yōu)路徑模型，并通過一系列算法對所建立的模型進行求解。

二、模型的建立與求解

（一）模型一的建立與求解

因為配送車輛必須給所有地點配送完應急物資后并返回出發(fā)地才是一次整體配送，所以配送車輛必須經過每個地點至少一次，故該問題可簡化為：VRP模型。我們假設配送車輛行駛平均速度為50公里/時，為一定值，故可以將完成一次整體配送的時間最少通過：S=VT轉化為路程最短。設配送路線連通圖為G=（V，E）；頂點集為V={V1，V2，V3，V4…V14}；邊集為E；各頂點間的最短距離為dij（i， j=1，2，3…14）；決策變量：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?。由于我們將判定方案的最優(yōu)條件從時間最短轉化成了路程最短，故目標函數為：

模型中（2），（3）保證了對于每個地點而言，僅有一邊進和一邊出，（4）消除了子回路對模型的影響，（5）為決策變量的取值約束。對該模型我們使用MATLAB對其進行求解。由于我們需要先求出任意兩個地點間的最短距離dij。所以我們采用Floyd算法對VRP模型的求解做好準備。通過Floyd算法計算圖1中各個頂點的最短路徑時，需要引入兩個矩陣，矩陣S中的元素aij表示第i個頂點到第j個頂點的距離。矩陣P中的元素bij，表示頂點i到頂點j的中間點代數。由于模型一中頂點個數為14，則需要對矩陣D和矩陣P進行14次更新。在得到dij的距離矩陣之后，我們采用二邊逐次修正法來計算最優(yōu)路徑。我們先設定一個任意的回路：

最短的路程之和為：582公里；所需的完成一次完整的配送工作的最短時間為：11.64小時；最優(yōu)路徑方案為：9—13—14—10—6—4—6—5—2—3—5—7—1—11—12—8—9

（二）模型二的建立與求解

模型一的最優(yōu)方案會有路徑重復，在采用了“配送車輛+無人機”的配送模式后最理想的情況為：配送車輛和無人機的配送路徑無重復且完成一次整體配送的時間最短，把該模型看作對模型一的路徑優(yōu)化，但加入了第二種配送工具且兩種配送工具之間存在約束關系，故我們可將模型二看作是FSTSP模型。對于無人機的最大路程而言：其平均飛行速度為75公里/小時，單次最長飛行時間為70分鐘，所以無人機最長飛行距離為：? ? ? ? ? ? ? ? ? ? 公里。

因為本題采用“配送車輛+無人機”的配速模式，時間上存在重疊部分，所以不能使用最短路程作為方案設定的目標函數，應該采用完成一次整體配送所需的最短時間作為判定標準，假設：C={1，2…14}為頂點集；Cr={r1，r2…rn}為可由無人機配送的地點集；C0為配送車輛可達點+起始點C9；Cd為配送車輛可達點+終止點C9。

由于本模型中的起始點和終止點均為C9，故設C0，Cd對其進行區(qū)分。同時假設無人機的飛行路徑為F={i，j，k}，其中i為無人機的出發(fā)點； j為無人機的配送點； k為無人機的回收點；e為無人機的續(xù)航時間；tij1為配送車輛從Ci到Cj所需時間；tij2為無人機從Ci到Cj所需時間；Tj1為配送車輛到達Cj的時間；Tj2為無人機到達Cj的時間。

通過上述分析，我們可以得到目標函數：

由于理想情況為配送車輛和無人機沒有路徑重復，故我們將其轉化為配送車輛和無人機所服務的地點不重復，為了保證每一個地點都必須被配送到物資，故我們約束：

與模型一類似，我們需要先通過Floyd算法分別求出配送車輛和無人機到達任意兩個地點之間的最短路程dij。我們在對無人機的路程求解時，考慮到無人機的最長飛行路程為87.5公里，所以我們將超過了87.5公里的路程設為一個無窮大的數。并且由于無人機需要返回到配送車輛上進行充電，這期間存在一段由無人機等待車輛或者由車輛等待無人機的時間，所以我們將無人機的配送路徑進行篩選，進行子回路的消除，刪除等待時間過長的無人機路徑回路，最終得到無人機和配送車量的最佳配送地點范圍。

在此之后，我們采用遺傳算法對所建立的FSTSP模型進行求解。由于在求解的過程中，會存在局部最優(yōu)解或者最優(yōu)解不唯一的情況，所以我們假設種群數目為80，迭代數為5e2次，用提高迭代次數和種群數目的方法避免這種情況的發(fā)生。

完成一次完整的配送工作所需的最短時間為：6.28小時；配送車輛的路線為：9—8—7—5—2—5—6—10—9；無人機的路線為：9—13—8、8—12—7、7—11—1—2、6—3—4—10、10—14—9。即：配送車輛在地點9放出無人機后到達地點8，無人機從地點9經過地點13，在地點8被收回；配送車輛在地點8發(fā)出無人機后到達地點7，無人機經過地點12后在地點7被收回；配送車輛在地點7發(fā)出無人機后經過地點5到達地點2，無人機經過地點11、地點1后在地點2被收回；配送車輛帶著無人機從地點2經過地點5到達地點6；配送車輛在地點6放出無人機后到達地點10，無人機經過地點3、地點4后在地點10被收回；配送車輛在地點10放出無人機后，回到物資集中點9，無人機經過地點14后返回到物資集中點9被收回。

（三）模型三的建立與求解

由于當日總需求量為762千克大于500千克，故在配送過程中配送車輛必須至少返回應急物資集中點一次，所以可以看作是對模型二的變形。模型二中，我們已經給出了一種不返回應急物資集中點條件下的最優(yōu)路徑方案，故我們選擇將該方案中的各地點進行聚類，將這14個配送地點（包括應急物資集中點在內）分成兩類，并且這兩部分的總物資重量需要小于500千克。我們可以對傳統(tǒng)的K-means聚類算法進行改進，對配送地點進行聚類，采用距離進行相似性評估。用Distance（Vi，Vj）表示兩對象間歐式距離，計算公式如下，其中n為對象個數，本題中n為14。

聚類中心就是類簇內所有對象在各個維度的均值：

其中，Ct表示第l個聚類中心， | Sl |表示第l個類簇中對象的個數，Xi表示第i個對象。在對于該模型的求解過程中，由于本模型與模型二初始條件相同，所以同樣需要先用Floyd算法求出配送車輛和無人機的最短路程，并對無人機的路徑回路進行篩選，得到配送車輛和無人機的可行路徑集合。

由于車輛的最大載重為500千克，通過一次運輸無法完成配送，所以我們采用K-means聚類算法對已知地點進行分類。配送車輛只需返回到應急物資集中點一次即可完成所有物資配送。故令算法中的k=2，表示將其分為兩類。采用遺傳算法對其進行求解。通過第一次的求解，我們得到：配送車輛的路線為：9—10—9，無人機的路線為：9—6—10、10—4—3—4—10、10—14—9，具體路徑如圖1。

其中紅色箭頭代表無人機的路徑，藍色箭頭代表配送車輛的路徑。通過第二次的求解，我們得到：配送車輛第二次的路線為：9—5—2—5—7—8—9，無人機第二次的路線為：9—5—2、2—1—11—7、7—12—8、8—13—9。將兩次配送路徑結合起來，我們得到：

最短用時為7.73小時；配送車輛第一次的路線為：9—10—9，第二次的路線為：9—5—2—5—7—8—9；無人機第一次的路線為：9—6—10、10—4—3—4—10、10—14—9，第二次的路線為：9—5—2、2—1—11—7、7—12—8、8—13—9。

（四）模型四的建立與求解

由于各地當日總需求量：? 12+90+24+15+70+18+150+50+30+168+36+44+42+13+41+76+12+16+19+12+33+15+27+13+85+74+120+48+35+180=1552（千克）。

若兩輛配送車輛均不多次返回應急物資集中點裝物資，則最多配送：500×2=1000（千克），小于1552千克。若兩輛車只返回一次，即可裝配：500×3=1500（千克），小于1552千克。故至少需要返回兩次，即每輛車返回一次或某一車輛返回兩次才可完成對所有地點的物資配送，但由于應急物資集中點的位置尚未確定，故我們需要先對其選址進行模型建立。本題采用P-Median Problem模型。假設：C為頂點集；dij為Ci到Cj之間的最短距離；決策變量：

上述模型中，式（21）表示所選取的應急物資點到其他配送點的距離之和最??；約束（22）（23）表示所選的集中點必須服務到所有配送點；約束（24）表示在30個地點中選取2個地點作為應急物資集中點；約束（25）是對決策變量的約束。通過MATLAB對選址模型進行簡化運算，我們可以得到應急物資集中點的地址為：地點9、地點20。再通過K-means聚類方法對其進行分類，并對每一部分的FSTSP模型通過遺傳算法進行求解，得到結果如表1。

所以在有兩個應急物資集中點的條件下，通過“配送車輛-無人機”運輸模式對30個地點進行物資配送，完成一次完整的物資配送最優(yōu)方案所需時間為：9.46小時；

配送路徑為：第一輛配送車輛：9—1—11—1—7—8—9，9—5—2—5—6—10—9；第二輛配送車輛：20—25—16—20，20—21—22—27—26—30—26—20；第一架無人機：9—13—9，11—18—11，6—3—4—10，10—14—9；第二架無人機：25—24—19—24—25，25—15—16，22—23—27，27—28—26，30—29—30。

三、結語

通過上述對模型的分析，模型三最具有實用性，故在此我們對于模型三的方案進行檢驗。在此，我們不將這14個地點進行分類，而將其看作一個整體，經過運算后的結果為：配送車輛行駛路徑：9—8—7—5—2—5—9，9—10—14—9；無人機行駛路徑：9—13—8，8—12—7，7—11—1—2，5—3—4—10，10—6—9；總配送時間為：6.64小時；誤差為：0.93小時。

由于該誤差小于1小時，所以方案三具有較高準確度，并且計算速度很快，所以該方案可行，這也同樣代表本文所建立的模型正確。

參考文獻

[1]顏瑞，陳立雙，朱曉寧，等.考慮區(qū)域限制的卡車搭載無人機車輛路徑問題研究[J].中國管理科學，2022，30（05）：144-155.

[2]彭勇，黎元鈞.考慮疫情影響的卡車無人機協(xié)同配送路徑優(yōu)化[J].中國公路學報，2020，33（11）：73-82.

[3]王新.車輛和無人機聯(lián)合配送路徑問題研究[D].大連：大連海事大學，2020.

[4]鄧永蕤，徐菱，吳茂婷，等.基于無人機與卡車聯(lián)合運輸下的冷鏈物流網絡優(yōu)化[J].江蘇農業(yè)科學，2019，47（13）：268-272.

[5]李妍峰，李佳，向婷.需求可拆分的無人機與卡車協(xié)同路徑優(yōu)化問題[J].工業(yè)工程，2022，25（01）：54-63+143.

[6]曹英英，陳淮莉.基于集群的卡車與無人機聯(lián)合配送調度研究[J].計算機工程與應用，2022，58（11）：287-294.

作者單位：東北電力大學經濟管理學院