劉蘇晴

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

關(guān)鍵詞：VRP模型；FSTSP模型；選址問(wèn)題；K-means聚類(lèi)算法；遺傳算法

一、前言

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

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

二、模型的建立與求解

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

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

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

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

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

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

因?yàn)楸绢}采用“配送車(chē)輛+無(wú)人機(jī)”的配速模式，時(shí)間上存在重疊部分，所以不能使用最短路程作為方案設(shè)定的目標(biāo)函數(shù)，應(yīng)該采用完成一次整體配送所需的最短時(shí)間作為判定標(biāo)準(zhǔn)，假設(shè)：C={1，2…14}為頂點(diǎn)集；Cr={r1，r2…rn}為可由無(wú)人機(jī)配送的地點(diǎn)集；C0為配送車(chē)輛可達(dá)點(diǎn)+起始點(diǎn)C9；Cd為配送車(chē)輛可達(dá)點(diǎn)+終止點(diǎn)C9。

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

通過(guò)上述分析，我們可以得到目標(biāo)函數(shù)：

由于理想情況為配送車(chē)輛和無(wú)人機(jī)沒(méi)有路徑重復(fù)，故我們將其轉(zhuǎn)化為配送車(chē)輛和無(wú)人機(jī)所服務(wù)的地點(diǎn)不重復(fù)，為了保證每一個(gè)地點(diǎn)都必須被配送到物資，故我們約束：

與模型一類(lèi)似，我們需要先通過(guò)Floyd算法分別求出配送車(chē)輛和無(wú)人機(jī)到達(dá)任意兩個(gè)地點(diǎn)之間的最短路程dij。我們?cè)趯?duì)無(wú)人機(jī)的路程求解時(shí)，考慮到無(wú)人機(jī)的最長(zhǎng)飛行路程為87.5公里，所以我們將超過(guò)了87.5公里的路程設(shè)為一個(gè)無(wú)窮大的數(shù)。并且由于無(wú)人機(jī)需要返回到配送車(chē)輛上進(jìn)行充電，這期間存在一段由無(wú)人機(jī)等待車(chē)輛或者由車(chē)輛等待無(wú)人機(jī)的時(shí)間，所以我們將無(wú)人機(jī)的配送路徑進(jìn)行篩選，進(jìn)行子回路的消除，刪除等待時(shí)間過(guò)長(zhǎng)的無(wú)人機(jī)路徑回路，最終得到無(wú)人機(jī)和配送車(chē)量的最佳配送地點(diǎn)范圍。

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

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

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

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

聚類(lèi)中心就是類(lèi)簇內(nèi)所有對(duì)象在各個(gè)維度的均值：

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

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

其中紅色箭頭代表無(wú)人機(jī)的路徑，藍(lán)色箭頭代表配送車(chē)輛的路徑。通過(guò)第二次的求解，我們得到：配送車(chē)輛第二次的路線為：9—5—2—5—7—8—9，無(wú)人機(jī)第二次的路線為：9—5—2、2—1—11—7、7—12—8、8—13—9。將兩次配送路徑結(jié)合起來(lái)，我們得到：

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

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

由于各地當(dāng)日總需求量：? 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（千克）。

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

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

所以在有兩個(gè)應(yīng)急物資集中點(diǎn)的條件下，通過(guò)“配送車(chē)輛-無(wú)人機(jī)”運(yùn)輸模式對(duì)30個(gè)地點(diǎn)進(jìn)行物資配送，完成一次完整的物資配送最優(yōu)方案所需時(shí)間為：9.46小時(shí)；

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

三、結(jié)語(yǔ)

通過(guò)上述對(duì)模型的分析，模型三最具有實(shí)用性，故在此我們對(duì)于模型三的方案進(jìn)行檢驗(yàn)。在此，我們不將這14個(gè)地點(diǎn)進(jìn)行分類(lèi)，而將其看作一個(gè)整體，經(jīng)過(guò)運(yùn)算后的結(jié)果為：配送車(chē)輛行駛路徑：9—8—7—5—2—5—9，9—10—14—9；無(wú)人機(jī)行駛路徑：9—13—8，8—12—7，7—11—1—2，5—3—4—10，10—6—9；總配送時(shí)間為：6.64小時(shí)；誤差為：0.93小時(shí)。

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

參考文獻(xiàn)

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

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

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

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

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

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

作者單位：東北電力大學(xué)經(jīng)濟(jì)管理學(xué)院