物流無人機城市低空軸輻式網絡構建方法研究

曲欣宇 葉博嘉 程予 雷昌定

摘要：無人機在城市物流配送方面具有極大應用潛力，然而城市低空空域運行場景中的潛在不確定因素較多，亟待通過科學方法構建安全有序的物流無人機配送網絡。從物流無人機運輸經濟性和運行安全性角度出發，結合物流無人機性能特征，在原有地面物流配送網點的基礎上，構建多層級軸輻式網絡的整數規劃模型，提出了帶距離限制的PAM（partitioning around medoids，圍繞中心點劃分）聚類與整數規劃相結合的網絡構建方法；從配送時效性、網絡安全性和網絡結構特征三方面選取評價指標，用于對比構建物流無人機運輸網絡與原地面運輸網絡；以南京市江寧區為例構建物流無人機配送網絡，驗證該網絡構建方法的可行性。實驗結果表明，該方法構建的無人機配送網絡在兼顧運輸成本與運輸安全性的同時，還具有較好的配送時效性。

關鍵詞：無人機；城市低空空域管理；物流配送；軸輻式運輸網絡；PAM聚類

中圖分類號：U8?? 文獻標志碼：A?? 文章編號：1002-4026（2023）06-0086-10

The method to construct an urban logistics unmanned aerial vehicles

low-altitude hub-and-spoke network

QU Xinyu， YE Bojia*， CHENG Yu， LEI Changding

（College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，China）

Abstract∶Unmanned aerial vehicles （UAVs） have considerable application potential in urban logistics delivery. However， there are many uncertainties in urban low-altitude airspace operation scenarios. Therefore， it is essential to build a safe and orderly logistics UAV delivery network using scientific methods. From the perspectives of delivery economy， operational safety， and features of logistics UAVs， an integer programming model of multilevel hub-and-spoke network was constructed based on the original ground logistics delivery network. A network construction method was proposed， which combines partitioning around medoids（PAM） clustering with distance restrictions and integer programming. Three evaluation indicators were selected， i.e.， delivery timeliness， network security， and network structure characteristics， to compare the constructed logistics UAV delivery network with the original ground delivery network. A logistics UAV delivery network was constructed in Jiangning District of Nanjing city to verify the feasibility of the proposed network construction method. The experimental results show that the UAV delivery network constructed using this method has good delivery timeliness while taking delivery costs and safety into account.

Key words∶unmanned aerial vehicle; low altitude airspace anagement; logistics and distribution; hub-and-spoke network; partitioning around medoids clustering

隨著快遞業務的迅猛發展，人們對快遞配送速度提出了更高的要求。無人機快遞配送不僅具有時效性強、成本低、可達性強的優點，還可有效減少快遞配送過程中人與包裹的接觸。美國亞馬遜、德國敦豪、順豐速運、京東等眾多國內外企業均在進行物流無人機的研發和試運行。此外，美國聯邦航空局、歐洲單一天空研究計劃等已開展無人機城市交通項目研究［1］，中國民用航空局也先后發布文件針對城市物流無人機制定技術規范與航線標準，推動我國城市物流無人機宏觀政策走向成熟。城市低空空域成為無人機應用的重要場景，無人機的安全高效運行受到各界廣泛關注。

為保障城市低空空域內無人機有序運行，各國學者對物流無人機航路網絡劃設展開研究。Venkatesh等［2］在需求和旅行時間限制下，分別對有容量和無容量限制的情況采用混合整數規劃方法進行機場選址；錢欣悅等［3］從配送效率出發，以最小化物流配送成本和最大化客戶時間滿意度為目標，建立物流無人機起降點選址分配模型；任新惠等［4］以步行距離最短為目標函數，以無人機機場的覆蓋半徑為約束構建基礎線性規劃模型；Chauhan等［5］考慮初始電池可用性和電池消耗的不確定性提出整數線性規劃公式，并使用魯棒優化最大化覆蓋率；Feng等［6］從建設成本和運營成本的角度出發，考慮性能限制、空域限制和容量限制，建立了城市環境下物流無人機機場的選址模型；Li等［7］結合城市低空環境特點和物流無人機的操作局限性，提出了一種基于改進元胞自動機算法和最優生成樹的航路網絡規劃方法；張洪海等［8］以總經濟成本最小和客戶滿意度最高為目標，以禁飛區、無人機性能、容需匹配等為約束構建整數規劃選址模型。目前這些研究多側重于無人機起降點的選址布局，大部分選址問題研究中考慮的常規因素有物流無人機的運輸需求、配送時間、配送距離、運輸成本等，少部分研究將無人機覆蓋半徑、禁飛區考慮在內。但研究通常忽視航路網絡的安全性，僅有少數學者在無人機路徑規劃時考慮了無人機與地面人員碰撞的風險［9-11］。此外，在物流無人機運輸研究中缺少對配送節點等級劃分和運輸網絡結構的研究。

本研究聚焦城市低空空域末端運輸，在地面快遞網點的基礎上構建無人機快遞運輸網絡。依據網點等級劃分將網絡構建問題分解為底層網點聚類和構建上層嚴格軸輻式網絡模型；最后，以南京江寧某快遞公司網點為例構建無人機快遞運輸網絡，對比分析網絡評價指標。研究為未來城市低空物流無人機配送網絡的構建提供方法參考，推動城市物流無人機未來商用化的發展。

1 問題分析

目前無人機快遞配送主要應用在區域樞紐機場到二、三線城市機場間的支線運輸和二、三線城市機場到顧客的末端運輸，物流企業可通過配置無人機起降平臺、快遞接駁柜等基礎設施改造原地面快遞網點。城市低空空域內建筑物、電磁信號等的干擾均會對物流無人機的運行帶來阻礙，物流無人機的投入使用必將增加城市低空運行的復雜度。為保障未來城市低空空域內物流無人機的安全運行，避免物流無人機無序運行導致低空空域環境復雜、危害居民生命財產安全，需對物流無人機配送網絡進行合理有序的規劃。

1.1 網絡結構選取

傳統地面快遞網絡依靠一定的網絡結構完成運輸活動，網絡中通常劃分快遞節點等級，包裹經各級節點層層分揀運輸最終送達目的地。民航運輸網絡與地面運輸網絡常見的結構有全連通網絡、軸輻式網絡［12］。其中，全連通網絡將網絡中每兩點都相連接，該網絡中快遞運輸不存在中轉，運輸效率高但穩定性差，適用于貨運量大且運輸網點少的情況。物流無人機運輸量達不到全聯通網絡的規模經濟需求，因此全聯通網絡結構并不適合無人機運輸時使用。而在軸輻式網絡中，快件至少經一次中轉到達目的地，其按非樞紐點間能否直接連接可進一步分類為嚴格和非嚴格軸輻式網絡。嚴格軸輻式網絡在快遞運輸中應用廣泛，與現有快遞運輸模式適應、便于追蹤快遞信息。為適應具有分揀、轉運等不同功能網點的運輸，本文選擇構建多層級嚴格軸輻式物流無人機運輸網絡。

多層級嚴格軸輻式網絡中至少包含3類網絡節點，如運作部、集配站、營業點。各層級網點與從上一級篩選出的樞紐點構成嚴格軸輻式網絡，而篩選出的樞紐點又可進一步構建出更高一級的軸輻式網絡，最終得到由多層級嚴格軸輻式航線網絡組成的城市物流無人機網絡，如圖1所示。

1.2 無人機運行安全因素

研究主要從城市低空空域使用、無人機城市運行風險和物流無人機性能三方面考慮城市低空物流無人機的運行安全。

低空空域指真高1 000 m（含）以下區域，根據2022年中國民用航空局發布的《城市場景輕小型無人駕駛航空器物流航線劃設規范》［13］，物流無人機航線應在高于高度零位面以上40 m并低于高度基準面以上120 m的空域范圍內劃設，航線高度可根據航空器性能和地形變化，物流無人機應在專為無人機劃設的隔離空域內運行。雖然目前尚未有明確的物流無人機隔離空域劃設規定，但為避免影響民航運輸的運行安全，民航局規定無人機城市運行需在機場、臨時起降點圍界以及周邊2 000 m外。因此，城市物流無人機網絡構建時需首先確保在規定高度層內且不飛經城市中機場禁飛區和限高區。

城市運行風險方面，無人機運行風險可大致分為空中飛行碰撞與地面碰撞，由于城市物流無人機需在隔離空域運行，本研究忽略無人機在空中與民航飛行器的空中碰撞風險。中國民航局發布的《無人駕駛航空器飛行管理暫行條例》［14］綜合考慮了無人機地面碰撞時可能引發的地面次生傷害、地面人員安全、地面設施安全以及可能引發碰撞的電磁環境等安全問題，規定了輕小型無人機在飛經衛星地面站、危險品存儲區、活動現場等各類城市區域時應保持的飛行間隔。為綜合考慮地面碰撞的所有可能風險，本文劃設六類城市物流無人機運行風險區域。由于最小飛行距離與風險值為正相關關系，可體現無人機在飛經各類區域可能產生風險的程度，將輕小型無人機與不同風險區應保持的最小飛行距離作為該類區域的風險值，詳細內容見表1。

在物流無人機性能方面，市面上現有的物流無人機實際運行時其飛行距離、載重、飛行轉彎角等方面均有上限。因此，在構建網絡時通常需考慮最大飛行距離、最大載重、最大轉彎角等限制，超出限制外的飛行行為將影響無人機運行安全。本研究將無人機最大飛行距離、最大載荷重量作為網絡構建的主要約束條件，而路徑規劃并非本文研究內容，因此對無人機最大轉彎角等涉及路徑規劃的性能約束做簡化處理。

2 網絡構建方法

2.1 建立整數規劃模型

以總配送成本和途徑區域風險值最低為目標函數構建嚴格軸輻式網絡模型，通過求解該模型可從上級網點中選出樞紐點以及各網點與上級樞紐點間的分配方式，自下而上在各層級網點構建軸輻式網絡，最終得到由多層級嚴格軸輻式航線網絡組成的城市物流無人機網絡。

2.1.1 假設與符號說明

模型中符號的含義及其單位見表2。本文假設說明如下：

（1）樞紐點容量總能滿足需求點需求；

（2）由樞紐點出發的無人機每次運輸多個包裹，每次包裹總重量達到無人機最大載荷；

（3）不考慮無人機載重對運輸能耗的影響；

（4）無人機運行中對航線高度上的建筑物等障礙物自主避障，繞飛程度以繞飛系數體現。

2.1.2 模型構建

min C=∑nk=1∑mi=1fαDidkiakixkibmax+∑mi=1Dih+pc，（1）

min E=∑oj=1∑nk=1∑mi=1rjekijakixki，（2）

s.t. ∑nk=1αkixki=1，（3）

∑nk=1yk=p，（4）

xki≤yk，（5）

akidkixki≤lmax，（6）

其中，公式（1）（2）為目標函數，即總配送成本最小和途徑區域風險值最低，配送成本包含貨物運輸能源成本、運營成本和樞紐點建設成本，其中，運營成本包括在樞紐和需求點以及運輸途中的管理費用。為減少無人機在城市空域運行的風險，無人機航線應盡量少地途徑黨政機關、電力設施、建筑物、公路等區域，即無人機應選擇風險值較低的航線。公式（3）確保每個節點都與樞紐點相連接。公式（4）限制樞紐點數量。公式（5）保證與各節點相連接的為被選中的樞紐點。公式（6）保證無人機實際飛行距離在最大飛行距離內。

選擇理想點法求解該多目標規劃模型。分別以式（1）和式（2）為目標求解兩個單目標模型，分別得到目標函數值C*、E*。再以式（7）為目標，將多目標規劃轉化為單目標規劃，求得距離兩理想點最近的解。

min F=（C*－CC*）2+（E*－EE*）2。（7）

2.2 底層網點聚類

在運輸網絡中各層級備選網點的數量逐級遞增，底層網點多且分布范圍廣，不宜將所有底層網點納入同一嚴格軸輻式網絡。考慮到無人機最大飛行距離限制，采用基于距離劃分的PAM（partitioning around medoids，圍繞中心點劃分）聚類算法，并將最大飛行距離作為約束加入，將底層網點分為多個簇。帶距離約束的PAM算法克服了k均值聚類算法（k-means）的缺陷，通過計算每簇中除聚類中心外的各點到其他所有點的距離的最小值修正聚類中心，同時還能夠篩除無人機最大飛行范圍外的樣本點，從樣本點中選取聚類中心。帶距離約束的PAM聚類算法步驟如下：

步驟1 從n個樣本點中隨機選取k個初始聚類中心；

步驟2 計算剩余點到聚類中心的距離，將樣本點歸入無人機最大飛行距離內且距離最近的聚類中心，若存在樣本點的無人機最大飛行距離內無初始聚類中心，則重復步驟1至每個非聚類中心的樣本點均與最大飛行距離內的聚類中心相匹配；

步驟3 計算所有樣本點與其聚類中心點的距離值，距離值累加得到損失值c0；

步驟4 選擇一個非中心樣本點替換聚類中心，重新計算損失值，若新的損失值小于c0，則將c0更新為新損失值，并將該非中心樣本點作為新的聚類中心；

步驟5 檢驗新聚類結果各簇中樣本點至聚類中心的距離，若存在簇內距離超過無人機最大飛行距離的樣本點，則拋棄該聚類結果；

步驟6 重復步驟4、步驟5，直至聚類中心不再改變。

除了確定聚類中心的位置外，還需要確定聚類中心的數量，文中聚類簇數將通過輪廓系數確定。需要注意的是，將樣本點分為較少的簇時，由于在PAM聚類算法中加入了距離約束，聚類結果可能因距離約束被否定，在遍歷不同的聚類簇數時可能會出現部分簇數情況的缺失。此外，為確保生成的各簇內樣本點間能夠構建嚴格軸輻式網絡，還需排除聚類結果中單個樣本點成為一簇的情況。因此，聚類簇數的選擇將在排除以上兩種情況后，選取具有輪廓系數最大值的簇數作為最終的聚類簇數。

3 算例分析

3.1 現狀分析

在南京江寧區內以快遞網點類型較全面且數量較多的快遞公司為例，共搜索到快遞中轉場、集散中心、集配站和營業點4類共55處網點。假定原有地面配送網絡中各網點均由距離最近的上一級網點配送，以直線連接的方式表示該快遞目前各級網點的分布情況，如圖2所示。

經觀察分析，該快遞現有地面快遞配送網絡存在超過物流無人機最大飛行距離的路徑。從大疆GEO（geospatial environment online，地理空間環境）系統中獲取南京祿口國際機場禁飛區與限高區，部分網點處在南京祿口機場禁飛區和限高區內。因此，不能直接以現有地面配送網絡作為無人機配送網絡，需要篩選網點并構建適合物流無人機運行的快遞配送網絡。

3.2 參數設置

擬使用市面上主流物流企業研發的物流無人機Ark方舟進行集配站到營業點樞紐的中短距離運輸，該機型最大載荷重量為12 kg，最大航程為20 km；營業點樞紐到營業點的短距離運輸由H4四旋翼無人機負責，該飛行器最大載荷重量為10 kg，最大航程為15 km。假設各營業點每日無人機快遞運輸需求為20 kg，其他參數假設見表3。

3.3 網絡構建

去除無人機禁飛區和限高區內的網點，在剩余43處營業點、4處集配站和1處集散中心的基礎上構建江寧區物流無人機運輸網絡。PAM聚類算法對43處營業點進行聚類，以H4四旋翼無人機最大航程15 km為距離約束。對營業點層級網點聚類，遍歷不同簇數量并計算輪廓系數，得到的輪廓系數折線圖如圖3（a）所示。當簇數量超過7時，出現單個網點為一簇的情況，此時該簇無法構成軸輻式網絡，因此不考慮簇數量超過7的聚類情況。而在此之前的輪廓系數隨簇數量的增加而變大，選取最大輪廓系數所對應的簇數，將營業點聚為7類，聚類結果如圖3（b）所示。

將各聚類中心作為樞紐點，分別構建如圖4（a）所示的7個單樞紐嚴格軸輻式網絡。按照表1中的分類標準統計江寧區的各類風險區域，無人機最大航程lmax=20 km帶入式（6），求解前文建立的多目標規劃模型。從集配站級網點中選擇東善橋集配站和淳化集配站作為7個營業點聚類中心的樞紐點；進一步以中科路集散中心為兩集配站的樞紐點，構建如圖4（b）所示的由三級嚴格軸輻式網絡組成的江寧區城市物流無人機配送網絡。

3.4 無人機配送網絡評價指標

3.4.1 指標選取

參考快遞運輸網絡和航線網絡評價指標并考慮無人機運行安全性，分別從配送時效性、網絡安全性、網絡結構特征等3方面對物流無人機快遞配送網絡進行評價。

（1）配送時效性

平均路徑長度是網絡中所有節點間最短路徑的平均值，用于衡量網絡的傳輸性能和效率，計算公式：

d=∑i≠j∈Vdij/nn－1，（8）

式中，n為網絡中節點數量，dij為網絡中任意兩節點間距離。

（2）網絡安全性

網絡安全性由網絡中各條航線風險值的平均值的倒數表示（為方便在雷達圖中比較，將倒數乘以100以擴大數量級），計算公式：

θ=1（E/u）×100，（9）

式中，u為網絡中邊的數量。

（3）網絡結構特征

節點的中心度指標包含點度中心度、接近中心度與中介中心度，分別反映節點i在整體網絡中的核心程度、與其他節點間的緊密程度以及銜接程度，數學表達式分別為式（10）～（12）。其中，ui為與節點i相連的邊的數量，dij為i、j兩點間最短路徑長度，gjk為網絡中兩點間最短路徑總數，gjk（i）為經過節點i的最短路徑，均可由Dijkstra算法計算得出。

網絡整體結構則選取平均點度中心性CRD、平均接近中心性CRP、平均中介中心性CRB與點度中心勢CD、接近中心勢CP、中介中心勢評價CB，數學表達式分別為式（13）～（18）［16］。其中，CDmax、CPmax、CBmax為網絡中相應類別的最大中心度值。

CD（i）=ui/（n－1），（10）

CP（i）=（n－1）/∑jdij，（11）

CB（i）=∑j≠k≠igjk（i）/gjk2（n－1）（n－2），（12）

CRD=∑iCD（i）/n，（13）

CRP=∑iCP（i）/n，（14）

CRB=∑iCB（i）/n，（15）

CD=∑i（CDmax－CD（i））/n－2，（16）

CP=∑i（CPmax－CP（i））/n－1，（17）

CB=2n－3∑i（CBmax－CB（i））n－2n－1。（18）

3.4.2 評價分析

將去除了禁飛區內網點的江寧區某快遞公司原地面配送網絡網點及運輸模式稱為原配送網絡，實驗中構建的無人機配送網絡為新建配送網絡，均以無人機作為運輸工具進行配送，兩網絡中各項指標計算結果見表3，并結合圖5中各指標雷達圖進行對比分析。

對比新建配送網絡與原配送網絡，新建配送網絡在運輸時效性與運輸安全性方面均呈現更優表現，尤其在安全性方面得到顯著提高。網絡結構方面，新建配送網絡平均點度中心性與平均接近中心性均高于原配送網絡，即網絡中各節點的連接更緊密，節點之間能更加快速地到達，相應的網絡運輸效率更高；多層級的嚴格軸輻式網絡結構使得新建配送網絡具有較高的平均中介中心性，網絡中各節點在其他點之間調節能力和控制能力較強；此外，新建配送網絡的點度中心勢與中介中心勢較低，表明相比于原配送網絡，新建配送網絡中各點的中心度分布較均衡，且節點對樞紐依賴性較低，網絡魯棒性較好。

4 結語

為適應現有物流運輸模式、保障城市低空空域無人機安全有序運行，選擇多層級的嚴格軸輻式網絡結構，采用帶距離約束的PAM聚類和以運輸成本與運輸風險為目標的整數規劃模型，對地面快遞網點進行樞紐點的選址和軸輻式網絡的構建。以南京市江寧區某快遞公司為例構建無人機快遞運輸網絡，對比分析網絡評價指標，發現所構建的無人機運輸網絡在兼顧運行成本與運行安全性的同時，相比于原配送網絡在網絡配送時效性方面也得到了提高。

研究中有以下幾個方面可在未來進行深入研究：第一，由于研究中僅考慮了無人機最大運輸距離、最大載荷等性能約束，所構建的物流無人機軸輻式網絡僅為二維運輸網絡，在后續研究中可考慮無人機飛行高度等約束，構建由飛行路徑所組成的三維城市物流無人機運輸網絡；第二，在構建的網絡中以直線作為航線表示網點間分配關系，并未對障礙物避障、轉彎角等做詳細規劃，可在選址問題后銜接路徑規劃，進一步研究城市物流無人機的選址、路徑優化問題。

參考文獻：

［1］姚虹翔， 葉博嘉， 程予. 低空無人機空中交通管理研究［J］. 科技創新與應用， 2021， 11（25）： 183-187.

［2］VENKATESH N， PAYAN A， JUSTIN C Y， et al. Optimal siting of sub-urban air mobility （sUAM） ground architectures using network flow formulation［C］//American Institute of Aeronautics and Astronautic，Aviation 2020 Forum. Reston， USA： AIAA. 2020： 2921.DOI： 10.2514/6.2020-2921.

［3］錢欣悅， 張洪海， 張芳， 等. 末端配送物流無人機起降點選址分配問題研究［J］. 武漢理工大學學報（交通科學與工程版）， 2021， 45（4）： 682-687. DOI： 10.3963/j.issn.2095-3844.2021.04.013.

［4］任新惠， 王柳. 即時配送下無人機全自動機場分區選址模型［J］. 計算機工程與應用， 2021， 57（10）： 266-272. DOI： 10.3778/j.issn.1002-8331.2003-0433.

［5］CHAUHAN DARSHAN R， AVINASHU， MIGUELF， et al. Robust maximum coverage facility location problem with drones considering uncertainties in battery availability and consumption［J］. Transportation Research Record， 2021， 2675（2）： 25-39.

［6］FENG D K， ZHANG HH， LIU H， et al. Research on location of logistics UAV airport in urban environment［C］// 6th International Conference on Information Science， Computer Technology and Transportation. Xishuangbanna， China： VDE， 2022： 1-5.

［7］LI S， ZHANG HH， LI Z L， et al. An air route network planning model of logistics UAV terminal distribution in urban low altitude airspace［J］. Sustainability， 2021， 13（23）： 13079. DOI： 10.3390/su132313079.

［8］張洪海， 馮棣坤， 張曉瑋， 等. 城市物流無人機起降點布局規劃研究［J］. 交通運輸系統工程與信息， 2022， 22（3）： 207-214. DOI： 10.16097/j.cnki.1009-6744.2022.03.023.

［9］ZHANG X J， LIU Y， ZHANG Y， et al. Safety assessment and risk estimation for unmanned aerial vehicles operating in national airspace system［J］. Journal of Advanced Transportation， 2018， 2018（Pt.6）：4731585. DOI： 10.1155/2018/4731585.

［10］胡莘婷， 戴福青. 基于城區行人安全的無人機運行風險評估［J］. 中國安全科學學報， 2020， 30（8）： 137-142. DOI： 10.16265/j.cnki.issn1003-3033.2020.08.020.

［11］鐘罡， 勵瑾， 張曉瑋， 等. 物流無人機對地風險評估方法研究［J］. 交通運輸系統工程與信息，2022，22（4）： 246-254. DOI：10.16097/j.cnki.1009-6744.2022.04.028.

［12］李鵬飛， 彪蔚然. 快遞網絡結構研究進展［J］. 西安郵電大學學報， 2020， 25（1）： 34-41. DOI： 10.13682/j.issn.2095-6533.2020.01.004.

［13］中國民用航空局空管行業管理辦公室.城市場景輕小型無人駕駛航空器物流航線劃設規范： MH/T 4054-2022［S］.北京： 中國民航出版社， 2022.

［14］中國民用航空局. 無人駕駛航空器飛行管理暫行條例［EB/OL］.［2023-01-17］.https：//www.gov.cn/zhengce/content/202306/content_6888799.htm.

［15］中通研究院. “末端+支線”無人機運營場景成本分析［EB/OL］.［2023-01-16］.http：//hkjjyjzx.zua.edu.cn/info/1066/1264.htm.

［16］陳欣， 李心茹， 盛寅. 基于復雜網絡的長三角航線網絡結構特征分析［J］. 交通信息與安全， 2020， 38（4）： 139-146. DOI： 10.3963/j.jssn.1674-4861.2020.04.017.