末端配送物流無人機起降點選址分配問題研究

錢欣悅 張洪海 張 芳 劉 皞

(南京航空航天大學民航學院 南京 211106)

0 引 言

隨著無人機技術的日趨成熟，其應用已由軍事領域向民用領域轉變.物流領域作為無人機民用新興領域，物流無人機起降點的選址分配是物流配送系統的中心環節，是保證物流運輸安全、高效的關鍵.

國外針對物流無人機起降點選址分配進行了大量研究.Brian等[1]結合無人機性能特點及包裹吞吐量限制等，構建無人機貨運地點選址優化模型；Darshan等[2]考慮無人機能量消耗和射程限制，以需求覆蓋最大化為目標，建立物流無人機設施點定位選址模型；Insu等[3]提出物流無人機充電定位優化模型，綜合最小生成樹、貪婪減法等多種算法進行求解.國內目前對物流無人機起降點選址分配研究較少.陳剛等[4]基于軍民融合背景，考慮需求點及配送中心類型，建立無人機配送中心選址分配模型并設計不同場景進行驗證；金垚煒考[5]慮無人機對城市交通的影響，提出無人機即時配送LRP(location-routing problems)二層規劃模型.

由此可知，有些研究將無人機起降點選址分配問題簡化為物流配送中心選址分配問題，未考慮無人機配送特點及空域限制；有些研究只實現了無人機對需求的部分覆蓋,未將具體需求作為必要約束；有些研究考慮因素單一，難以應用于實際配送場景.解決物流無人機起降點選址分配問題的關鍵在于地面物流配送中心選址分配與無人機物流配送的結合.目前研究存在的普遍問題就是對兩者的融合不夠緊密，導致選址分配結果不理想或不符合現實情況.

文中從物流系統配送效率出發，以最小化物流配送系統的綜合成本和最大化客戶時間滿意度為目標函數，建立物流無人機起降點選址分配模型，并設計遺傳算法進行求解，以獲取最優選址及分配方案.

1 物流無人機起降點選址分配問題建模

1.1 問題描述

某城區根據其物流需求分布情況，以社區為單位分設不同的需求點.假設該城區內所有末端配送的任務均由能夠垂直起降的充電式四旋翼無人機完成[6]，在具備包裹處理能力和無人機承載能力的幾個備選場址中，確定滿足配送任務要求的最佳選址分配方案.單架無人機的飛行路線為從起降點裝載包裹飛行至需求點并空載返回起降點.本文以平衡無人機起降點選址配送總成本與客戶時間滿意度為目標，研究城區物流無人機起降點選址分配的最優方案.

為方便研究，將各需求片區及無人機配送中心簡化為點進行討論.由于物流無人機實現的是末端配送，因此起降點與需求點之間直接配送，無需中轉.兩者之間的配送關系為“一對多”，即每個需求點由且僅由一個起降點覆蓋配送，一個起降點可以覆蓋多個需求點的需求.圖1為物流無人機起降點與需求點之間的配送模式示意圖.

圖1 物流無人機配送模式示意圖

在圖1中，以不同塊狀區域的形心表示各需求點和無人機起降點.其中，中心圓點為該圖中的物流無人機起降點，負責其覆蓋范圍內所有●需求點的貨物運輸，▲需求點為該起降點由于各種原因無法到達的點.

1.2 客戶時間滿意度

在顧客決定購買產品直至產品送達過程中，顧客對產品的滿意程度體現在多個方面.此處僅考慮顧客對產品到達時間的需求.選用文獻[7]中提出的混合時間滿意度函數對客戶時間滿意度進行表述，該函數的圖像見圖2.

圖2 物流末端配送過程中客戶時間滿意度函數

S(tij)為客戶的時間滿意度，取值范圍為[0,1]，0為完全不滿意，1為完全滿意.tE為客戶對貨物送達感到完全滿意的最長維持時間，tL為客戶對貨物送達感到完全不滿意的最短維持時間.tij為訂單從物流無人機起降點i開始處理至貨物送達需求點j的時間.

1.3 相關假設及符號說明

假設條件：①僅考慮單類型貨物運輸；②運輸費用與運輸量和運輸距離成正比；③運輸過程保證貨物完好，不考慮由于意外情況造成的配送延誤及無人機相撞問題；④僅考慮單機型無人機運輸，所有物流無人機的運輸速度恒定；⑤不考慮貨物的裝卸搬運時間與成本，不考慮貨物到達需求點后的服務時間，不考慮各需求片區之間的地面路網結構.

1.4 多約束條件物流無人機起降點選址分配模型

本文所建立的物流無人機起降點選址分配模型是一個多目標函數規劃模型，綜合考慮了普通物流中心選址配送約束和物流無人機的性能約束，從物流無人機運營企業與客戶的雙重角度建立物流無人機起降點選址分配模型.

1.4.1目標函數

1)綜合成本最小.

(1)

第一個目標函數是綜合成本最小化.在本文中綜合成本主要涵蓋物流運輸、起降點建設,以及無人機投資三個方面，具體包括4個部分.

式(1)中第一部分是起降點至需求點的貨物運輸成本；第二部分是貨物在起降點處的管理成本；第三部分是無人機使用成本；最后一部分是無人機飛行里程成本.其中無人機飛行里程成本包括無人機裝載貨物進行配送的成本和空載返回的成本.各成本的計算公式如上.

2)客戶時間滿意度最大：

(2)

(3)

(4)

1.4.2約束條件

1)需求約束 所有運往需求點j的運輸量之和要滿足該需求點的實際需求，約束為

(5)

2)點對點約束 每個需求點j由且僅由一個物流無人機起降點i與之對應，約束如下.

(6)

3)無人機起降點數量約束 無人機起降點的數量不能超過候選場址的數量，約束如下.

(7)

4)無人機起降點容量約束 無人機起降點負責配送的需求點的需求總量不能超過該起降點的容量，約束見式(8).

(8)

5)配送范圍約束 所有需求點j均應在各物流無人機起降點的配送范圍內，約束如下.

(9)

6)客戶時間滿意度約束 對于每個物流需求點j，其滿意度至少要滿足該需求點的最低滿意度，約束為

(10)

7)無人機飛行航程約束 無人機k的飛行距離不能超過其最大航程，約束為

8)無人機飛行高度約束 物流無人機的飛行高度要在指定的低空空域高度范圍內，約束為

Hmin≤Hk≤Hmax?k∈K

(12)

9)無人機載重約束 無人機每次的運輸量不超過其最大載重量，約束為

(13)

10)空域約束 當無人機起降點與物流需求點間的路徑處于禁飛空域時，無法進行貨物運輸，約束為

?i∈I,?j∈J,?k∈K

(14)

1.4.3模型建立

整合1.4.1中的目標函數和1.4.2中的約束條件，即可建立物流無人機起降點選址分配模型，其模型為

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

Hmin≤Hk≤Hmax?k∈K

(24)

(25)

(26)

2 算法設計方案

結合本文所建模型，對遺傳算法每一步操作的具體設置如下.

1)編碼 所求解的是一個選址分配問題，其編碼需充分體現對解的要求且不得冗余.針對每個染色體個體，設計j個基因表示對無人機起降點的選擇以及起降點與需求點之間的分配關系.這j個基因分別對應需求點1～j所選擇的起降點編號(0～i-1).假設現有5個起降點和10個需求點，編碼[0,0,1,3,2,2,3,0,1,2]表示在所有起降點中選擇了第1-4個起降點，1號起降點負責編號為1、2、8的需求點貨物配送，2號起降點負責編號為3、9的需求點貨物配送，3號起降點負責編號為5、6、10的需求點貨物配送，4號起降點負責編號為4、7的需求點貨物配送.這種編碼方式無需對選址結果額外編碼，從分配關系即可看出最終選擇的起降點情況.

2)生成初始種群 通過隨機方式，以空域性質和連通路徑判斷起降點能否被選擇，使用blockId=0表示對起降點的禁用.在滿足相應約束條件的限制下，生成對應規模大小的初始種群.

3)設置適應度函數 所建立的模型是一個多目標規劃函數，既包含最小值優化問題，也包含最大值優化問題，鑒于此，對適應度函數設置如下：

(27)

4)選擇 對于染色體的選擇，采用自然選擇的方法，適應度最高的n個個體直接進入下一代，剩余個體以每個個體的適應度占總適應度的比例為篩選條件，選擇優良個體.

5)交叉變異 通過復制概率的設置，以輪盤賭法選擇父母染色體，將生成的父染色體和母染色體的一部分基因片段進行交叉以生成新的染色體.通過對變異概率的設置，隨機選擇染色體基因片段進行變異重組.

6)終止條件 以所設置的迭代次數作為終止條件.

遺傳算法流程圖見圖3.

圖3 遺傳算法流程圖

3 算例分析

3.1 參數設置

在LRP算例集中[9-12]，選取Gaskell67-50x5算例，以此對需求點和備選物流無人機起降點的相關參數進行設置，為與本文末端配送的概念相適應，將各點的坐標和各需求點的需求進行了適當的修改，具體分布見圖4.

圖4 備選無人機起降點與需求點分布示意圖

在圖4中，各點旁的數字表示備選無人機起降點的編號和物流需求點的編號，括號中的數字為各對應編號需求點的需求量，單位為kg.圖中三個深色區域處于禁飛空域中，其他區域處于可行空域中.

參閱相關文獻，并結合本文研究內容，起降點參數設置見表1.

表1 物流無人機起降點參數設置

參考目前市面上常用的物流無人機機型，對物流無人機性能參數的仿真設置見表2.

表2 物流無人機參數設置

關于客戶時間滿意度中的參數，選取VRP-H(vehicle routing problem-H)測試庫中的RC106數據集[13-14]，用該數據集的平均值代表客戶時間滿意度函數中的tE及tL兩個參數，最終，tE參數取為77 min，tL參數取為139 min.每個需求點j的最低滿意度λj取為0.5.

針對第2節中設計的遺傳算法，具體參數設置見表3.

表3 遺傳算法參數設置

3.2 結果分析

通過遺傳算法的求解，最終在5個備選物流無人機起降點中選擇了編號為3、4、5的起降點，每個起降點與需求點之間的分配情況見圖5.

圖5 選址分配結果示意圖

由圖5可知，編號為3的起降點負責編號為1、2、5、6、7、8、12、15、17、26、27、28、29、39、41、44、47、48、50的需求點的配送，編號為4的起降點負責編號為3、4、9、11、13、16、18、19、20、21、22、23、24、30、32、33、35、36、40、43、45、49的需求點的配送，編號為5的起降點負責編號為10、14、25、31、34、37、38、42、46的需求點的配送.該分配方案下對應的綜合成本為49.559 7萬元，滿意度為1.

由于客戶滿意度最優值變化不是很明顯，此處僅列出綜合成本最優值隨迭代次數的變化情況，見圖6.由圖6可知，當迭代次數在320代左右時種群收斂.

圖6 迭代效果示意圖

以上結果表明，遺傳算法在求解本文所建立的模型時表現出優良的性能，具有良好的適應性.

3.3 參數靈敏度分析

在求解無人機起降點選址分配規劃模型時，需求點的需求分布、起降點的特性、空域性質等均會對求解結果造成影響.本文僅探究需求點的需求規模和空域性質對起降點選址分配結果的影響變化.

保持3.1中其他參數不變，采用對照實驗法進行如下參數分析.

1)需求規模 對3.1節中所有需求點的需求量分別擴大至原來的1.5倍和縮小至原來的1/2，以擴大后的需求規模為大規模需求，縮小后的需求規模為小規模需求，原有需求規模為中等規模需求進行求解.

經過求解，在小規模需求場景下，綜合成本為32.828 8萬元，客戶滿意度為1.在大規模需求場景下，綜合成本為74.101 5萬元，客戶滿意度為1.各需求規模下的選址分配結果見圖7.

圖7 不同需求規模下的選址分配結果

由圖7可知，當需求規模不同時，選址分配結果會發生部分變化.對于大規模的需求分布，隨著需求量的持續增加，綜合成本也明顯增加.當需求量增加超過一定范圍時，由于起降點規模未發生變化，不能對各需求點的需求有效供應，其選址分配結果將發生較大改變.對于小規模的需求分布，雖然在成本上得到了有效控制，但起降點的容量有較大冗余，造成個別起降點負擔較重，利用率相對較低.因此，選擇與備選起降點相匹配規模的需求點能夠大大提升物流無人機起降點選址分配的效率.

2)空域性質 在原有空域設置基礎上分別增加了禁飛空域和可行空域，以原有空域為平衡空域，對新模型進行求解.

經過求解，在多禁飛空域場景下，綜合成本為53.560 9萬元，客戶滿意度為1.在多可行空域場景下，綜合成本為44.634 5萬元，客戶滿意度為1.各空域結構下的選址分配結果見圖8.

圖8 不同空域結構下的選址分配結果

由圖8可知，當空域設置不同時，起降點的選址分配結果和綜合成本均有較明顯的變化.當可行空域增多時，起降點的選擇和分配增加了更多可能性，其綜合成本求解結果更優，但從選址分配結果上來說，易存在需求點分配不均勻的情況，造成起降點功能的浪費.當禁飛空域增多時，無人機飛行受到了更多的限制，負擔較重的起降點會將需求進行轉移，但綜合成本相對于可行空域較多的情況明顯增加.

4 結 論

1)構建了物流無人機起降點選址分配模型，并設計了遺傳算法對模型進行求解，通過算例驗證了該算法的可行性和有效性.

2)在參數靈敏度分析部分，考慮了需求規模和空域性質，以探究該模型的最佳使用效率，為無人機投放配送市場提供了理論依據.

3)目前有關物流無人機起降點選址分配的研究較少，需求架次數據獲取困難，下一步將結合實際需求架次，并融合起降場選址分配，建立完整的物流無人機起降場點選址分配體系.