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

錢欣悅 張洪海 張 芳 劉 皞

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

0 引 言

隨著無人機技術(shù)的日趨成熟，其應(yīng)用已由軍事領(lǐng)域向民用領(lǐng)域轉(zhuǎn)變.物流領(lǐng)域作為無人機民用新興領(lǐng)域，物流無人機起降點的選址分配是物流配送系統(tǒng)的中心環(huán)節(jié)，是保證物流運輸安全、高效的關(guān)鍵.

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

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

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

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

1.1 問題描述

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

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

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

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

1.2 客戶時間滿意度

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

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

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

1.3 相關(guān)假設(shè)及符號說明

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

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

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

1.4.1目標函數(shù)

1)綜合成本最小.

(1)

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

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

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

(2)

(3)

(4)

1.4.2約束條件

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

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

Hmin≤Hk≤Hmax?k∈K

(12)

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

(13)

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

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

(14)

1.4.3模型建立

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

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

Hmin≤Hk≤Hmax?k∈K

(24)

(25)

(26)

2 算法設(shè)計方案

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

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

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

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

(27)

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

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

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

遺傳算法流程圖見圖3.

圖3 遺傳算法流程圖

3 算例分析

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

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

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

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

參閱相關(guān)文獻，并結(jié)合本文研究內(nèi)容，起降點參數(shù)設(shè)置見表1.

表1 物流無人機起降點參數(shù)設(shè)置

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

表2 物流無人機參數(shù)設(shè)置

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

針對第2節(jié)中設(shè)計的遺傳算法，具體參數(shù)設(shè)置見表3.

表3 遺傳算法參數(shù)設(shè)置

3.2 結(jié)果分析

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

圖5 選址分配結(jié)果示意圖

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

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

圖6 迭代效果示意圖

以上結(jié)果表明，遺傳算法在求解本文所建立的模型時表現(xiàn)出優(yōu)良的性能，具有良好的適應(yīng)性.

3.3 參數(shù)靈敏度分析

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

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

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

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

圖7 不同需求規(guī)模下的選址分配結(jié)果

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

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

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

圖8 不同空域結(jié)構(gòu)下的選址分配結(jié)果

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

4 結(jié) 論

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

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

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