考慮無人機(jī)運(yùn)行風(fēng)險的車機(jī)協(xié)同配送路徑規(guī)劃方法

摘 要：針對城市無人機(jī)與車輛協(xié)同配送路徑規(guī)劃問題，考慮無人機(jī)在城市區(qū)域飛行過程中的墜落傷亡風(fēng)險和噪聲影響，設(shè)計無人機(jī)路徑分割方法，并采用相應(yīng)的量化模型計算無人機(jī)墜落傷亡風(fēng)險和噪聲影響程度；引入無人機(jī)載重限制、區(qū)域噪聲排放限制、無人機(jī)續(xù)航能力限制作為約束條件，構(gòu)建以經(jīng)濟(jì)成本和風(fēng)險成本最小為目標(biāo)函數(shù)的雙目標(biāo)無人機(jī)與車輛協(xié)同配送路徑規(guī)劃模型。設(shè)計帶精英策略的非支配排序遺傳算法（NSGA-Ⅱ）對模型進(jìn)行求解。結(jié)果表明：所提模型較傳統(tǒng)車輛配送模型能夠節(jié)約配送經(jīng)濟(jì)成本，并有效降低無人機(jī)運(yùn)行風(fēng)險，在規(guī)模較小、分布較均勻、中低風(fēng)險配送節(jié)點(diǎn)較多的配送網(wǎng)絡(luò)中效果更顯著。

關(guān)鍵詞：運(yùn)輸規(guī)劃；無人機(jī)與車輛協(xié)同配送；路徑優(yōu)化；NSGA-Ⅱ；墜落傷亡風(fēng)險；噪聲影響

中圖分類號：U121 文獻(xiàn)標(biāo)識碼：A" " " " " "文章編號：1007-1199（2024）03-0032-10

DOI：10.19327/j.cnki.zuaxb.1007-1199.2024.03.004

昆明理工大學(xué) 交通工程學(xué)院，云南 昆明 650500

隨著無人機(jī)技術(shù)的發(fā)展，無人機(jī)用于物流配送的潛力被不斷發(fā)掘。然而無人機(jī)運(yùn)行過程中不可避免地存在墜落傷亡風(fēng)險以及噪聲影響居民等問題。Luppicini ［1］的技術(shù)倫理審查結(jié)果表明，盡管商用無人機(jī)的使用可以改善生活方式并提高效率，但引發(fā)了安全、隱私和道德問題，有必要對可能產(chǎn)生的負(fù)面影響和未知后果給予更多關(guān)注。因此，研究考慮無人機(jī)墜落傷亡風(fēng)險和噪聲影響的協(xié)同配送路徑規(guī)劃問題有助于提高配送的經(jīng)濟(jì)性、時效性和安全性，具有很強(qiáng)的現(xiàn)實意義。

目前，國內(nèi)外考慮墜落傷亡風(fēng)險和噪音影響的無人機(jī)路徑規(guī)劃大多是針對無人機(jī)點(diǎn)到點(diǎn)的航跡規(guī)劃。

為降低無人機(jī)的運(yùn)行風(fēng)險，Hu等［2］提出了基于風(fēng)險成本的無人機(jī)飛行航跡規(guī)劃，張智杰等［3］建立了最大化運(yùn)行效率和最小化風(fēng)險的多目標(biāo)規(guī)劃模型，胡莘婷等［4］對城市無人機(jī)飛行路徑進(jìn)行規(guī)劃時發(fā)現(xiàn)，不同區(qū)域的風(fēng)險成本區(qū)別明顯。Pang等［5］在進(jìn)行無人機(jī)航跡規(guī)劃時，進(jìn)一步考慮了第三方風(fēng)險成本并引入噪聲影響因素，張洪海等［6、7］研究了物流無人機(jī)攜帶貨物的情況，提出了考慮空域環(huán)境、運(yùn)輸任務(wù)等約束，以效率、經(jīng)濟(jì)成本、風(fēng)險作為優(yōu)化目標(biāo)的無人機(jī)航跡規(guī)劃模型。

無人機(jī)與車輛協(xié)同配送的路徑規(guī)劃已經(jīng)受到部分學(xué)者關(guān)注，但幾乎沒有考慮無人機(jī)的墜落傷亡風(fēng)險和噪音影響。

無人機(jī)與車輛協(xié)同配送問題首先由Murray［8］提出，問題以最小化配送完成時間為目標(biāo)，對1架無人機(jī)與1輛送貨卡車協(xié)同工作時最佳任務(wù)分配進(jìn)行決策。Agatz等［9］提出了協(xié)同無人機(jī)的旅行商問題，研究表明無人機(jī)與車輛組合配送相較僅車輛配送可有效節(jié)約成本，Ha等［10］在此基礎(chǔ)上設(shè)置優(yōu)化目標(biāo)為最小化運(yùn)營成本，Tinic等［11］研究了一輛卡車與多架無人機(jī)協(xié)同配送的經(jīng)濟(jì)成本優(yōu)化，考慮了無人機(jī)與車輛對接的等待成本，Campuzano等［12］考慮了天氣條件對無人機(jī)飛行速度的影響，在TSP-D中增加了對飛行速度的決策，Bogyrbayeva等［13］則探索了當(dāng)下流行的深度強(qiáng)化學(xué)習(xí)方法在TSP-D問題中的應(yīng)用。與本文研究比較類似的是Jeong［14］和朱曉寧［15］等的研究。Jeong研究了由于區(qū)域政策和天氣原因?qū)е聼o人機(jī)服務(wù)范圍受限的路徑規(guī)劃問題。朱曉寧等則進(jìn)一步研究了客戶所處區(qū)域限行或限飛時的調(diào)度問題。新冠肺炎疫情背景下，彭勇等［16］考慮了由于疫情導(dǎo)致某些地區(qū)車輛限行無法進(jìn)行配送的無人機(jī)與車輛協(xié)同配送，并證明了其應(yīng)用價值。

本文以城市無人機(jī)與車輛協(xié)同配送為研究對象，通過對無人機(jī)墜落傷亡風(fēng)險和噪聲影響的量化，構(gòu)建以配送經(jīng)濟(jì)成本、墜落傷亡風(fēng)險和噪聲影響最小為目標(biāo)函數(shù)，滿足無人機(jī)載重、續(xù)航、區(qū)域噪聲排放限制約束的無人機(jī)與車輛協(xié)同配送路徑規(guī)劃模型。設(shè)計適用于該多目標(biāo)模型的NSGA-Ⅱ算法，并以昆明市某藥品連鎖門店配送為例，驗證模型和算法的可行性。論文的研究可以為降低無人機(jī)配送對社會造成的負(fù)面影響、促進(jìn)無人機(jī)在物流配送中的實際應(yīng)用提供理論基礎(chǔ)。

1 問題建模

1.1 問題描述與假設(shè)

在城市物流末端中小型貨物配送中，為了追求更低的配送成本和更高的時效性，物流企業(yè)選擇由1輛卡車攜帶1架無人機(jī)、多個無人機(jī)備用電池以及貨物從配送中心出發(fā)，在城市中協(xié)同執(zhí)行配送任務(wù)。車輛在為1個客戶進(jìn)行配送時，無人機(jī)可以從車上發(fā)射為另1個客戶服務(wù)，完成任務(wù)后在下個節(jié)點(diǎn)與車輛對接，返回車輛，更換電池并攜帶貨物執(zhí)行下一次配送任務(wù)。

無人機(jī)在執(zhí)行配送任務(wù)時，會在不同區(qū)域上空飛行。不同的區(qū)域中建筑、樹木、人口密度不同，噪聲排放限制閾值也不相同，這導(dǎo)致無人機(jī)墜落傷害及噪聲影響的效果有明顯的差異，因此會產(chǎn)生不同的墜落傷亡風(fēng)險成本及噪聲影響［17、18］。

作為決策者，配送成本是無人機(jī)與車輛協(xié)同配送路徑規(guī)劃的第一優(yōu)化目標(biāo)，但出于對社會以及更大利益的考慮，無人機(jī)配送產(chǎn)生的墜落傷亡風(fēng)險和噪聲影響也必須作為目標(biāo)進(jìn)行考慮，見圖1。

為了便于模型構(gòu)建和求解，在不影響對關(guān)鍵因素考慮的前提下，本文作以下假設(shè)：

（1）不考慮客戶節(jié)點(diǎn)服務(wù)時間，以及無人機(jī)執(zhí)行配送任務(wù)過程中從車輛上發(fā)射、回收、更換電池的時間。

（2）卡車行駛距離為曼哈頓距離，無人機(jī)飛行距離為歐幾里得距離。

（3）假設(shè)無人機(jī)在2個節(jié)點(diǎn)間的飛行路徑最多經(jīng)過2個不同區(qū)域，且無人機(jī)在不同區(qū)域中的飛行距離與區(qū)域面積占比有關(guān)。

1.2 無人機(jī)墜落傷亡風(fēng)險和噪聲影響量化

1.2.1 路徑分割方法

為量化無人機(jī)在不同區(qū)域上空飛行時的墜落傷亡風(fēng)險與噪聲影響，本文提出1種基于區(qū)域面積占比的路徑分割方法，如圖2所示，無人機(jī)從節(jié)點(diǎn)[i]發(fā)射到[j]服務(wù)的過程時會跨過2個不同的區(qū)域，[i]、[j]之間的飛行弧段為“L1+L2”，2段飛行弧段各屬于不同的區(qū)域，無人機(jī)在[i]和[j]所處區(qū)域中的飛行距離分別為[dij×Lu（i）]、[dij×Lu（j）]， [Lu]為節(jié)點(diǎn)所處區(qū)域的用地面積占比，因此將無人機(jī)執(zhí)行1次配送任務(wù)的路徑[i→j→k]分為4段L1， L2， L3， L4， 這4段分別對應(yīng)不同的墜落傷亡風(fēng)險成本和噪聲影響程度，下文中用[η]表示弧段的序號。

1.2.2 墜落傷亡風(fēng)險

根據(jù)Specific Operations Risk Assessment特定操作風(fēng)險評估規(guī)則（SORA），地面運(yùn)行風(fēng)險需要考慮人群密度、天氣以及地面遮蔽物等因素，由于本文重點(diǎn)研究無人機(jī)運(yùn)行的墜落傷亡風(fēng)險，因此將人群密度與地面遮蔽系數(shù)設(shè)置為主要評估參數(shù)。墜落傷亡風(fēng)險量化參考文獻(xiàn)[5]中行人傷亡風(fēng)險計算，見式（1）。

[Cf=PfNhitRf] （1）

式（1）中[Pf]為無人機(jī)運(yùn)行時發(fā)生故障墜落的概率?，F(xiàn)有研究中指出電池電量不足是無人機(jī)墜落事故的主要誘因，物流無人機(jī)正常運(yùn)行時發(fā)生安全事故的概率大約為[6.54×10-3][19]，無人機(jī)在運(yùn)行過程中隨飛行距離[d]增加，剩余續(xù)航能力[Δε]減少，進(jìn)而無人機(jī)系統(tǒng)故障概率[Pf]增加[20]。無人機(jī)墜落概率[Pf]的計算見式（2）。

[Pf=6.54×10-3+1-6.54×10-315×d] （2）

式（1）中[Nhit]為無人機(jī)墜落地面擊中的人數(shù)，計算見式（3）。

[Nhit=Shitσpda] （3）

式中：[Shit]表示墜落后地面受影響的矩形面積，通過無人機(jī)尺寸[a]求得；[σp]表示墜落點(diǎn)對應(yīng)區(qū)域的人口密度。

式（1）中[Rf]為無人機(jī)墜落造成傷害的能力，計算見式（4）[21]。

[Rf=11+αββEp14Sc] （4）

式中：[Ep]為人機(jī)墜落時的動能；[Sc]為墜落發(fā)生區(qū)域的遮蔽系數(shù)；[α]為[Sc=0.5]時，造成50%死亡率的撞擊動能；[β]為[Sc]趨近于0時，造成死亡的撞擊動能。無人機(jī)墜落時的動能[Ep]計算見式（5）。

[Ep=12mv2] （5）

式中：[m]包括無人機(jī)自身質(zhì)量[muav]以及貨物質(zhì)量[ugoods]，若無人機(jī)完成任務(wù)返回車輛則認(rèn)定[ugoods=0]；[v]為無人機(jī)墜落時的速度，由水平飛行速度與自由落體速度合成。

1.2.3 噪聲影響程度

無人機(jī)噪聲為點(diǎn)聲源，由于聲音傳播與距離和聲屏障有關(guān)，因此無人機(jī)飛行高度及環(huán)境聲屏障是影響其噪聲傳播的關(guān)鍵，噪聲影響程度計算參考文獻(xiàn)[22]中無人機(jī)運(yùn)行噪聲風(fēng)險量化公式，見式（6）。

[Cn=LA×1Gp×Ndt] （6）

式中：[LA]為無人機(jī)噪聲經(jīng)過衰減之后到達(dá)人耳的瞬時聲強(qiáng)；[Gp]為無人機(jī)運(yùn)行環(huán)境的聲屏障因子；[Ndt]為受無人機(jī)影響的人數(shù)。為簡化模型，假設(shè)每個區(qū)域中人口分布均勻，這里用無人機(jī)在該區(qū)域上方飛行的距離[d]代表受影響人數(shù)。[LA]計算見式（7）。

[LA=LS+10lg14πh2] （7）

式中[LS]為無人機(jī)作為點(diǎn)聲源發(fā)出噪聲的聲強(qiáng)級。

1.3 無人機(jī)與車輛協(xié)同配送路徑規(guī)劃模型

本研究綜合考慮城市無人機(jī)與車輛協(xié)同配送過程中產(chǎn)生的經(jīng)濟(jì)成本以及無人機(jī)運(yùn)行帶來的墜落傷人風(fēng)險和噪聲影響，同時考慮無人機(jī)性能、城市法規(guī)限制等因素，構(gòu)建以配送經(jīng)濟(jì)成本和無人機(jī)運(yùn)行風(fēng)險最小為目標(biāo)的雙目標(biāo)路徑規(guī)劃模型。

1.3.1 模型符號相關(guān)說明

模型使用符號及相關(guān)說明見表1。

1.3.2 目標(biāo)函數(shù)

（1） 配送經(jīng)濟(jì)成本

以配送經(jīng)濟(jì)成本[CE]最小為1個優(yōu)化目標(biāo)，即

[minCE]" " " " " " " " " " （8）

配送經(jīng)濟(jì)成本包括了無人機(jī)配送費(fèi)用，卡車配送費(fèi)用，無人機(jī)等待成本和卡車等待成本，見式（9）[CE=sti∈N0j∈N+dijxij+sdi∈N0j∈Nk∈N+dij+djkyijk+swti∈Nwi+swdi∈Nw′i]（9）

（2） 風(fēng)險綜合成本

由于無人機(jī)墜落傷亡風(fēng)險和噪聲影響與經(jīng)濟(jì)成本相對立，本文將墜落傷亡風(fēng)險成本和噪聲影響程度2個目標(biāo)通過歸一化與加權(quán)轉(zhuǎn)化為單一目標(biāo)，稱為風(fēng)險綜合成本[CZ]。以其最小為模型另1個優(yōu)化目標(biāo)，見式（10）～（11）。

[minCZ] （10）

[CZ=λfωfCf+λnωnCn] （11）

[λ]表示2個子成本的權(quán)重因子，且[λf+λn=1]，[ω]為歸一化因子，為了消除2個子成本量綱的影響，需要進(jìn)行歸一化處理，使所有成本在（0， 1）范圍內(nèi)， 引入歸一化因子[ωf]和[ωn]，歸一化因子和子成本最大值[Cmax]之間的相關(guān)性表示為：

[ω=1Cmax] （12）

無人機(jī)最大墜落傷亡風(fēng)險成本[Cf_max]和最大噪聲影響程度[Cn_max]由求解以經(jīng)濟(jì)成本最低為目標(biāo)函數(shù)的TSP-D問題得出。

目標(biāo)函數(shù)中墜落傷亡風(fēng)險成本和噪聲影響程度計算見式（13）～（14）。

[Cf=i，j，k∈Pyijk×Pf_ijkη=14Nf_η×Rf_η] （13）

[Cn=i，j，k∈Pη=14LA×1Gp_η×dη] （14）

[Pf-ik]為上文所描述的無人機(jī)配送路徑中墜落[i→j→k]概率的積分。

1.3.3 約束條件

（1）節(jié)點(diǎn)服務(wù)約束

客戶需求會在無人機(jī)或車輛進(jìn)行過1次配送后得到滿足，配送任務(wù)完成意味著要滿足所有客戶的需求，因此每個客戶必須被車輛或無人機(jī)服務(wù)1次且僅1次，即

[i∈N0i≠jxij+i∈N0i≠jk∈N+i，j，k∈Pyijk=1，?j∈N0?N+] （15）

任務(wù)開始時車輛攜帶貨物從配送中心出發(fā)，任務(wù)完成后需返回配送中心，即

[j∈N+x0j=1] （16）

[i∈N0xi，n+1=1] （17）

（2）無人機(jī)與車輛協(xié)同約束

無人機(jī)需要在車輛上發(fā)射，且完成配送后需返回車輛進(jìn)行裝載貨物、更換電池等操作，因此無人機(jī)發(fā)射回收節(jié)點(diǎn)之間必須有1條車輛路線，即

[2yijk≤h∈N0h≠ixhi+l∈Nl≠kxlk，?i∈N，j∈N：j≠i，k∈N+：i，j，k∈P] " （18）

[y0jk≤h∈N0h≠kxhk，?j∈N，k∈N+：0，j，k∈P] （19）

（3） 無人機(jī)與車輛等待約束

為達(dá)到時間同步，無人機(jī)與車輛在返回節(jié)點(diǎn)處需要相互等待，出發(fā)時間不能早于到達(dá)時間，即

[tk≥rk-E1-i∈N0i≠kj∈Ni，j，k∈Pyijk，?k∈N+] （20）

[tk≥rk-E1-i∈N0i≠kj∈Ni，j，k∈Pyijk，?k∈N+] （21）

在發(fā)射節(jié)點(diǎn)，無人機(jī)與車輛需同時出發(fā)，即

[ti≥ti-E1-j∈Nj≠ik∈N+i，j，k∈Pyijk，?i∈N0] （22）

[ti≤ti-E1-j∈Nj≠ik∈N+i，j，k∈Pyijk，?i∈N0] （23）

本研究為了避免返回節(jié)點(diǎn)處無人機(jī)等待車輛時續(xù)航不足、故障、被擊落等潛在風(fēng)險，要求車輛在發(fā)射節(jié)點(diǎn)與返回節(jié)點(diǎn)間不再服務(wù)其他客戶，即

[xik=1，?i∈N，k∈{N+：i，j，k∈P}] （24）

（4）無人機(jī)載重約束。

無人機(jī)無法為需求超出自身最大載重量的客戶服務(wù)。

[mj≤DM+E（1-yijk），?k∈N+，j∈N：j≠k，i∈N0：i，j，k∈P] " （25）

（5）無人機(jī)續(xù)航約束。

無人機(jī)每次執(zhí)行任務(wù)飛行距離不能超出其最大航程。

[" " " " "dij+djk≤ε+E（1-yijk），" " " " ?k∈N+，j∈N：j≠k，i∈N0：i，j，k∈P]" " " " （26）

（6）無人機(jī)噪聲排放約束。

無人機(jī)在某一區(qū)域上方飛行時，其到達(dá)地面聲級[LA]不能超出該區(qū)域噪聲排放限值[Lh]，即

[LA≤minLh（i），Lh（j），Lh（k）+E（1-yijk），?k∈N+，j∈N：j≠k，i∈N0：i，j，k∈P] （27）

上述模型在針對無人機(jī)與車輛協(xié)同配送的特性，在傳統(tǒng)的TSP-D模型基礎(chǔ)上引入了無人機(jī)運(yùn)行風(fēng)險量化模型，分割無人機(jī)在不同區(qū)域中的配送路徑以計算墜落傷人風(fēng)險與噪聲影響程度，在保證無人機(jī)與車輛協(xié)同性的前提下同時優(yōu)化配送經(jīng)濟(jì)成本和無人機(jī)運(yùn)行風(fēng)險。根據(jù)城市區(qū)域法規(guī)，賦予每個區(qū)域噪聲排放約束，避免無人機(jī)在禁飛區(qū)域進(jìn)行飛行、起降操作，貼合當(dāng)前城市無人機(jī)應(yīng)用應(yīng)考慮的安全與道德要求。

2 算法設(shè)計

上文提出的多目標(biāo)模型中，不可能讓2個相互沖突且量綱不同的目標(biāo)同時達(dá)到最優(yōu)，但可以在滿足約束條件的情況下，生成包含多個最優(yōu)解的Pareto解集。NSGA-Ⅱ為帶有精英保留策略的快速非支配多目標(biāo)優(yōu)化算法，該算法是一種基于Pareto最優(yōu)解的多目標(biāo)優(yōu)化算法。上述模型通過NSGA-Ⅱ求解可以得到多個同樣優(yōu)秀的配送路徑方案，在此基礎(chǔ)上根據(jù)不同偏好選擇最優(yōu)解。

2.1 編碼方式

由于需要決策路徑以及各節(jié)點(diǎn)所用的配送方式，所以遺傳算法采用雙層編碼[23]。第1層編碼表示節(jié)點(diǎn)的訪問順序，采用實數(shù)編碼，第2層編碼表示節(jié)點(diǎn)采用的配送方式，采用二進(jìn)制編碼。該方式可以使車輛從發(fā)射節(jié)點(diǎn)直接駛往返回節(jié)點(diǎn)，一定程度上避免無人機(jī)等待車輛時續(xù)航不足、故障、被擊落等潛在風(fēng)險。在目標(biāo)函數(shù)計算中引入懲罰因子，使求得的方案滿足約束條件。

2.2 沖突消除

由于第2層編碼可能出現(xiàn)連續(xù)多個節(jié)點(diǎn)由無人機(jī)配送的情況，即連續(xù)多個0的情況，需要對第2層編碼進(jìn)行修正，基因位若為0，則將其前后兩基因不為1的變化為1，重復(fù)此操作，直至沒有沖突為止。

2.3 遺傳操作

針對無人機(jī)與車輛協(xié)同配送的特性，本研究對兩層染色體編碼分別制定交叉、變異策略，第1層染色體編碼交叉采用部分匹配交叉（PMX），第2層采用適用于二進(jìn)制編碼的多點(diǎn)交叉策略，為維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象，對兩次染色體編碼分別進(jìn)行單點(diǎn)交換變異和多基因位翻轉(zhuǎn)變異，在交叉變異完成后，需對第2層編碼進(jìn)行沖突檢測，消除連續(xù)多個0的片段，最終形成子代個體，與父代個體合并后進(jìn)行快速非支配排序和擁擠度計算，篩選出新的父代進(jìn)行下一步迭代。

3 算例驗證與分析

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

為了對模型與算法進(jìn)行驗證，以昆明市某連鎖藥房為例，該藥房在昆明城市片區(qū)共有10個線下藥店，配送中心位置已知。根據(jù)線下門店所處區(qū)域的占地面積、人口密度、遮蔽系數(shù)、環(huán)境屏障因子和噪聲排放限制的差異，將門店所在區(qū)域分為高風(fēng)險區(qū)域、中風(fēng)險區(qū)域和低風(fēng)險區(qū)域，見表2。其中，無人機(jī)飛行違反高風(fēng)險區(qū)域噪聲排放限制，配送中心節(jié)點(diǎn)序號為1。

模型中涉及了卡車、無人機(jī)的相關(guān)參數(shù)，參考文獻(xiàn)［10］中的數(shù)據(jù)以及目前主流配送無人機(jī)相關(guān)參數(shù)，取值見表3。

上述NSGA-Ⅱ算法采用 MATLAB R2021b 編程實現(xiàn)，計算機(jī)CPU為Intel（R） Core（TM） i5-12400F，主頻為2.50GHz，內(nèi)存16GB，操作系統(tǒng)為64位win10。NSGA-Ⅱ種群規(guī)模設(shè)置為200，最大迭代次數(shù)為500，交叉概率和變異概率分別為0.9和0.05，懲罰因子設(shè)置為1000。

為了驗證算法的有效性，在不考慮無人機(jī)運(yùn)行風(fēng)險的情況下對不同節(jié)點(diǎn)數(shù)量的算例使用Gurobi進(jìn)行求解，并與NSGA-Ⅱ求解結(jié)果進(jìn)行對比。

3.2 結(jié)果分析

在對上述實例的求解中，Gurobi與NSGA-Ⅱ的表現(xiàn)相當(dāng)，前者耗時20.32s，后者為18.67s，不考慮無人機(jī)運(yùn)行風(fēng)險的情況下，二者經(jīng)濟(jì)成本求解結(jié)果均為388.51元。在此基礎(chǔ)上，NSGA-Ⅱ求解得到帕累托前沿，包含13個Pareto解，見圖4。對節(jié)點(diǎn)個數(shù)分別為11、16、21、26的算例求解對比結(jié)果見表4，NSGA-Ⅱ算法耗時均為20s左右，而Gurobi求解16個節(jié)點(diǎn)規(guī)模的算例時，就需要計算119個連續(xù)變量和5491個整數(shù)變量，并且具有13580行、5610列的約束，求解耗時已超過3600s。

結(jié)果表明，NSGA-Ⅱ算法相較于Gurobi在求解時間上具有顯著優(yōu)勢，同時可以找到與Gurobi相同甚至更優(yōu)的解，這充分顯示了本文設(shè)計的NSGA-Ⅱ算法的有效性。

使用NSGA-Ⅱ算法對上述實例進(jìn)行求解后的部分方案可視化見圖5，可以發(fā)現(xiàn)：隨著經(jīng)濟(jì)成本降低、風(fēng)險綜合成本增長，無人機(jī)配送節(jié)點(diǎn)數(shù)呈增加趨勢。方案13，見圖5（a），僅由車輛配送，其對應(yīng)的經(jīng)濟(jì)成本為513.25元；方案1，見圖5（b），對應(yīng)僅考慮配送經(jīng)濟(jì)成本而不考慮無人機(jī)墜落傷亡風(fēng)險與噪聲影響的TSP-D問題的解，經(jīng)濟(jì)成本為388.51元，相較方案1節(jié)約了24.3%。在考慮無人機(jī)墜落傷亡風(fēng)險和噪聲影響的情況下，方案5，見圖5（c），相較于方案1風(fēng)險綜合成本降低42.5%，經(jīng)濟(jì)成本為408.38元，較僅車輛配送的方案可降低20.43%；方案7，見圖5（d），風(fēng)險綜合成本降低51.82%，經(jīng)濟(jì)成本為428.36元，較僅車輛配送的方案仍可降低16.54%。

3.3 考慮墜落傷亡風(fēng)險和噪聲對經(jīng)濟(jì)成本的影響

為了進(jìn)一步驗證模型與算法的適用性，探究不同節(jié)點(diǎn)個數(shù)及分布情況下風(fēng)險綜合成本與經(jīng)濟(jì)成本之間的關(guān)系，生成12個算例，分為4組進(jìn)行對比分析。

算例1-3的節(jié)點(diǎn)個數(shù)為11，其中高風(fēng)險節(jié)點(diǎn)1個、中風(fēng)險節(jié)點(diǎn)與低風(fēng)險節(jié)點(diǎn)各5個，均勻分布于10×10的矩形范圍內(nèi)；算例4-6的節(jié)點(diǎn)個數(shù)為16，其中高風(fēng)險節(jié)點(diǎn)2個、中風(fēng)險節(jié)點(diǎn)與低風(fēng)險節(jié)點(diǎn)各7個，均勻分布于20×20的矩形范圍內(nèi)；算例7-9、10-12的節(jié)點(diǎn)個數(shù)分別為21、26，其中高風(fēng)險節(jié)點(diǎn)個數(shù)分別為3、4，中、低風(fēng)險區(qū)域節(jié)點(diǎn)各占剩余節(jié)點(diǎn)數(shù)量的1/2，隨機(jī)分布于30×30的矩形范圍內(nèi)。

表5選取了無人機(jī)綜合風(fēng)險成本降低約50%后的方案結(jié)果，與未考慮無人機(jī)運(yùn)行風(fēng)險的方案結(jié)果及僅由車輛配送方案的結(jié)果進(jìn)行對比。未考慮無人機(jī)運(yùn)行風(fēng)險時，即為經(jīng)濟(jì)成本最優(yōu)的方案，該方案相較于僅用車輛進(jìn)行配送可節(jié)約10%～30%的經(jīng)濟(jì)成本。但在這些方案中，會有潛在的無人機(jī)墜落傷亡風(fēng)險和噪聲影響。若決策者考慮該潛在因素造成的后果，要求無人機(jī)風(fēng)險綜合成本降低50%左右，相應(yīng)的最優(yōu)方案中無人機(jī)配送節(jié)點(diǎn)數(shù)量減少1-3個，經(jīng)濟(jì)成本降低幅度變小，但較僅車輛進(jìn)行配送仍可節(jié)約5%～20%經(jīng)濟(jì)成本。

由圖6可見：隨著配送范圍擴(kuò)大，節(jié)點(diǎn)數(shù)量增加，無人機(jī)配送節(jié)點(diǎn)的數(shù)量增長幅度較小，經(jīng)濟(jì)成本節(jié)約比例降低。這說明無人機(jī)的利用率并不隨著任務(wù)規(guī)模的增大而提高。同時，降低風(fēng)險前后的方案中，無人機(jī)配送節(jié)點(diǎn)相差個數(shù)隨著配送任務(wù)規(guī)模的大幅增加僅有小幅度的波動。

在節(jié)點(diǎn)分布較均勻的算例1-6中，2個方案經(jīng)濟(jì)成本節(jié)約比例差值相對穩(wěn)定，而在算例7-12中有著明顯的波動，這是由于節(jié)點(diǎn)分布均勻時，無人機(jī)在不同節(jié)點(diǎn)之間的飛行距離差值不大，其會選擇主動避開某些風(fēng)險較高的區(qū)域，而在節(jié)點(diǎn)隨機(jī)分布情況下可以通過2種途徑降低無人機(jī)墜落傷亡風(fēng)險與噪聲影響：①使無人機(jī)避開風(fēng)險較高區(qū)域的配送任務(wù)；②避免無人機(jī)執(zhí)行距離較遠(yuǎn)的配送任務(wù)。當(dāng)選擇第2種途徑時，相當(dāng)于降低了無人機(jī)的利用率以降低風(fēng)險，無人機(jī)節(jié)約成本的效果因此衰減。

因此，當(dāng)配送網(wǎng)絡(luò)規(guī)模較小，且分布均勻時，無人機(jī)與車輛協(xié)同配送可以在降低風(fēng)險的同時取得較好的經(jīng)濟(jì)效益。

考慮到不同的配送節(jié)點(diǎn)構(gòu)成可能會影響配送方案及結(jié)果，調(diào)整上文算例5中高、中、低風(fēng)險區(qū)域中節(jié)點(diǎn)的個數(shù)后進(jìn)行求解對比，見圖7。

虛線左側(cè)為算例A集合，高風(fēng)險節(jié)點(diǎn)個數(shù)為2，虛線右側(cè)為算例B集合，高風(fēng)險節(jié)點(diǎn)個數(shù)為0。對比A、B集合可以發(fā)現(xiàn)，B集合考慮風(fēng)險前后的經(jīng)濟(jì)成本要低于A集合，說明高風(fēng)險區(qū)域節(jié)點(diǎn)越少，無人機(jī)與車輛協(xié)同配送經(jīng)濟(jì)成本越低，這是由于可供無人機(jī)起降、服務(wù)的節(jié)點(diǎn)增多，提高了無人機(jī)的利用率，從而降低了經(jīng)濟(jì)成本。分別對比集合內(nèi)的算例可以發(fā)現(xiàn)，考慮風(fēng)險后相同經(jīng)濟(jì)成本的配送方案，在中風(fēng)險節(jié)點(diǎn)較多的情況下風(fēng)險綜合成本更低，即考慮無人機(jī)運(yùn)行風(fēng)險后，經(jīng)濟(jì)效益相同的配送方案在中風(fēng)險節(jié)點(diǎn)較多的時候降低風(fēng)險的效果更顯著。

綜上說明，考慮無人機(jī)運(yùn)行風(fēng)險下的無人機(jī)與車輛協(xié)同配送，在中低風(fēng)險節(jié)點(diǎn)較多的配送任務(wù)中更具經(jīng)濟(jì)優(yōu)勢。

4 結(jié)束語

無人機(jī)與車輛協(xié)同配送能夠同時發(fā)揮車輛和無人機(jī)的優(yōu)勢，從而更好地提高配送的時效性和降低配送成本，具有良好的發(fā)展前景。本文針對無人機(jī)在飛行過程中存在的墜落傷亡風(fēng)險和噪聲擾民特性，建立了以經(jīng)濟(jì)成本、墜落傷亡風(fēng)險和噪聲影響綜合成本最小的雙目標(biāo)無人機(jī)與車輛協(xié)同配送路徑規(guī)劃模型，設(shè)計了求解模型的NSGA-Ⅱ算法。同時，設(shè)計了不同規(guī)模和屬性特征的算例進(jìn)行實驗分析。結(jié)果表明：所建模型與算法可以被用于無人機(jī)與車輛協(xié)同配送路徑規(guī)劃問題；當(dāng)要求降低墜落傷亡風(fēng)險與噪聲影響時，可以選擇減少無人機(jī)配送節(jié)點(diǎn)數(shù)量或使無人機(jī)優(yōu)先執(zhí)行距離較短的配送任務(wù)；在規(guī)模較小，且分布較為均勻的配送網(wǎng)絡(luò)中，無人機(jī)與車輛協(xié)同配送可以在降低墜落傷亡風(fēng)險和噪聲影響的同時帶來不錯的經(jīng)濟(jì)效益；限制無人機(jī)飛行的高風(fēng)險區(qū)域節(jié)點(diǎn)的減少會提高無人機(jī)的利用率，降低經(jīng)濟(jì)成本，另外，同樣的配送方案在低風(fēng)險區(qū)域節(jié)點(diǎn)較少的任務(wù)中降低無人機(jī)運(yùn)行風(fēng)險的效果更顯著?？紤]到城市中需求發(fā)生的隨機(jī)性以及城市路網(wǎng)的規(guī)范化，無人機(jī)在配送任務(wù)中可主要發(fā)揮輔助作用，以應(yīng)對特殊或者突發(fā)需求。

無人機(jī)與車輛組合配送模式越來越多樣化，未來可進(jìn)一步研究考慮風(fēng)險的無人機(jī)與車輛并行、車輛協(xié)助無人機(jī)、多無人機(jī)與車輛協(xié)同等配送問題。另外，還可以在本研究基礎(chǔ)上考慮無人機(jī)飛行時受外界不確定因素影響的情況，或考慮車輛配送的風(fēng)險。

參考文獻(xiàn)：

［1］LUPPICINI R，SO A.A technoethical review of commercial drone use in the context of governance， ethics， and privacy［J］. Technology in Society，2016（46）：109-119.

［2］HU X T，PANG B Z，DAI F Q，et al. Risk assessment model for UAV cost-effective path planning in urban environments［J］. IEEE Access，2020（8）：162-173.

［3］張智杰，羊釗，陸佳歡.城市復(fù)雜環(huán)境下多目標(biāo)無人機(jī)路徑規(guī)劃［J］.航空計算技術(shù)，2021，51（6）：79-83.

［4］胡莘婷，戴福青.基于城區(qū)行人安全的無人機(jī)運(yùn)行風(fēng)險評估［J］.中國安全科學(xué)學(xué)報，2020，30（8）：137-142.

［5］PANG B Z，HU X T，DAI W，et al. UAV path optimization with an integrated cost assessment model considering third-party risks in metropolitan environments［J］.Reliability Engineering amp; System Safety，2022（222）：1-18.

［6］張啟錢，許衛(wèi)衛(wèi)，張洪海，等.復(fù)雜低空物流無人機(jī)路徑規(guī)劃［J］.北京航空航天大學(xué)學(xué)報，2020，46（7）：1275-1286.

［7］張洪海，張連東，劉皞，等.城市低空物流無人機(jī)航跡規(guī)劃模型研究［J］.交通運(yùn)輸系統(tǒng)工程與信息，2022，22（1）：256-264.

［8］MURRAY C C，CHU A G.The flying sidekick traveling salesman problem：Optimization of drone-assisted parcel delivery［J］.Transportation Research Part C：Emerging Technologies，2015（54）：86-109.

［9］AGATZ N，BOUMAN P，SCHMIDT M.Optimization approaches for the traveling salesman problem with drone［J］.Transportation Science，2018，52（4）：965-981.

［10］HA Q M，DEVILLE Y，PHAM Q D，et al.On the min-cost traveling salesman problem with drone［J］. Transportation Research Part C：Emerging Technologies，2018（86）：597-621.

［11］TICNIC G O，KARASAN O E，KARA B Y，et al. Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones［J］.Transportation Research Part B： Methodological，2023（168）：81-123.

［12］CAMPUZANO G，LALLA R E，MES M.The drone-assisted variable speed asymmetric traveling salesman problem［J］.Computers amp; Industrial Engineering，2023，109003：1-20.

［13］BOGYRBAYEVA A，YOON T，KO H，et al.A deep reinforcement learning approach for solving the traveling salesman problem with drone［J］.Transportation Research Part C： Emerging Technologies，2023，103981：1-19.

［14］JEONG H Y，SONG B D，LEE S.Truck-drone hybrid delivery routing： Payload-energy dependency and No-Fly zones［J］.International Journal of Production Economics，2019（214）：220-233.

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

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

［17］PRIMATESTA S，RIZZO A，LACOUR-HARBO A. Ground risk map for unmanned aircraft in urban environments［J］.Journal of Intelligent amp; Robotic Systems，2020，97（3）：489-509.

［18］韓鵬，趙嶷飛.基于飛行環(huán)境建模的UAV地面撞擊風(fēng)險研究［J］.中國安全科學(xué)學(xué)報，2020，30（1）：142-147.

［19］韓鵬，王夢琦，趙嶷飛.基于貝葉斯網(wǎng)絡(luò)的物流無人機(jī)失效風(fēng)險評估［J］.中國安全生產(chǎn)科學(xué)技術(shù)，2020，16（11）： 178-183.

［20］李翰，張洪海，張連東，等.城市區(qū)域多物流無人機(jī)協(xié)同任

務(wù)分配［J］.系統(tǒng)工程與電子技術(shù)，2021，43（12）：3594-3602.

［21］DALAMAGKIDIS K，VALAVANIS K P，PIEGL L A.Evaluating the risk of unmanned aircraft ground impacts［C］.16th mediterranean conference on control and automation.Ajaccio， France：IEEE， 2008.

［22］任新惠，程彩霞.城市運(yùn)行無人機(jī)第三方風(fēng)險模型構(gòu)建及應(yīng)用［J］.中國安全科學(xué)學(xué)報，2021，31（9）：15-20.

［23］范利陽.基于改進(jìn)遺傳算法的多能源車輛路徑問題研究［D］.成都：西南交通大學(xué)，2020.

責(zé)任編校：杜晚霞，羅 紅

Collaborative Distribution Path Planning Considering UAV Operational Risks

WEI Wei，SHUI Wenbing

（Faculty of Transportation Engineering， Kunming University Of Science And Technology， Kunming 650500， China）

Abstract： Aiming at the problem of collaborative delivery path planning between UAV and vehicle in cities， considering the risk of falling casualties and noise impact caused by UAV flying， the UAV path segmentation method is designed， and the corresponding quantitative model is used to calculate the UAV fall casualty risk and noise impact degree; The UAV load limit， regional noise emission limit and UAV endurance limit are introduced as constraints， and a dual-objective UAV-vehicle cooperative distribution path planning model with the minimum economic cost and risk cost as the objective function is constructed. A non-dominated sorting genetic algorithm （NSGA - Ⅱ） with elitist strategy is designed to solve the model. The results show that compared with the traditional vehicle distribution model， the proposed model can save the economic cost of distribution and reduce the operational risk of UAV effectively. The effect is more significant in the distribution network with smaller scale， more uniform distribution and more medium-low risk distribution nodes.

Key words： transportation planning; UAV-vehicle collaborative distribution; path planning; NSGA-Ⅱ; risk of falling casualty; noise impact