多層級物流末端配送無人機選址的LRP模型

文/梁晨 曹博凱 邢蓉 崔濤 楊雅楠

將物流末端配送的特點、無人機的具體性能等影響因素考慮其中，建立了物流末端配送無人機起降點的選址分配模型，并設(shè)計遺傳算法，以呼和浩特市下轄的托克托縣、和林格爾縣和清水河縣地區(qū)為實例，規(guī)劃該地區(qū)最優(yōu)的物流末端無人機及起降點的選址分配方案。最終得出在城關(guān)鎮(zhèn)（和林格爾縣）、盛樂鎮(zhèn)、雙河鎮(zhèn)、宏河鎮(zhèn)、窯溝鄉(xiāng)和城關(guān)鎮(zhèn)（清水河縣）建立物流末端配送無人機起降點為最優(yōu)方案。

1.文獻綜述。

國外無人機的發(fā)展歷史要遠遠長于國內(nèi)，因此在外國針對物流末端配送無人機起降點選址分配問題有大量的研究文獻，其中Insu Hong等基于最大覆蓋模型，將流動加油和無人機的雙飛行范圍等因素集成于其中，提出了無人機配送服務規(guī)劃的距離限制充電站覆蓋模型，并通過貪婪算法、空間交換啟發(fā)式算法進行求解，最后用模擬退火算法確定新方案的可接受性[1]。Darshan Chauhan等以滿足空間分布客戶的需求為目標，提出了一種新的無人機基于覆蓋能力的設(shè)施選址模型，之后運用貪婪啟發(fā)式和三階段啟發(fā)式分別對模型進行求解[2]。孫夢禪等設(shè)計了無人機物流轉(zhuǎn)運中心，并以薊州區(qū)為例進行無人機物流轉(zhuǎn)運中心的選址研究[3]。金垚煒考慮了無人機在城市中飛行對城市交通的影響，提出了無人機即時配送定位-路徑二層規(guī)劃模型[5]。綜上所述我們不難發(fā)現(xiàn)，有一部分的學者在研究無人機起降點選址時并未認真考慮他需要面對的空域限[3]，將無人機起降點選址問題當作物流中心選址問題來研究；還有一部分學者沒有將無人機配送中的具體需求作為必要的約束[2]。本文以最小化運營公司投資總成本和最大化顧客時間滿意度為目標函數(shù)，建立了物流末端配送無人機起降點的選址分配模型，設(shè)計了遺傳算法對模型進行求解，得出物流末端配送無人機起降點的最優(yōu)選址分配方案。

2.LRP模型建立

2.1 問題描述

假設(shè)在我們的研究區(qū)域內(nèi)所有的參與末端配送的無人機均為能夠垂直起降的四旋翼無人機來完成，在擁有商品處理能力和無人機起降能力的所有備選點中，根據(jù)不同的目標函數(shù)來選擇最佳的選址分配方案。每架無人機的飛行路線相同，為滿載商品從無人機起降點飛往需求點，再空載從需求點原路返回無人機起降點。本文同時使用了無人機起降點的選址總成本和客戶時間滿意度兩個目標函數(shù)，研究在選定區(qū)域內(nèi)物流末端配送無人機的最佳選址分配方案。由于本文研究的是物流配送中的末端配送，所以無人機將貨物從起降點直接運輸?shù)叫枨簏c，中間不會產(chǎn)生中轉(zhuǎn)。無人機起降點和各需求點之間的配送關(guān)系為“一對多”，即一個無人機起降點負責多個需求點的配送，每個需求點有且只有一個無人機起降點進行配送，如圖1所示：

圖1物流末端配送無人機起降點的配送模式示意圖

2.2 客戶時間滿意度

在客戶購買了商品到物流公司將商品運送到客戶手中的這段時間里，對客戶的滿意度產(chǎn)生影響的因素有很多，例如價格、時間、服務、是否有貨損等等。在這些影響因素中時間無疑是非常重要的。本文主要通過借鑒學者馬云峰的方法來計算時間滿意度，具體函數(shù)圖像如圖2所示：

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

圖2中所示，客戶時間滿意度（S（tij））的取值范圍為[0，1]，0表示客戶完全不滿意，1表示客戶完全滿意。tij表示商品從物流末端配送無人機起降點i開始配送處理到將貨物運送至需求點j的服務時間，tE表示客戶對商品送達感到完全滿意的最長維持時間，tL表示客戶對商品送達感到完全不滿意的最短維持時間。

2.3 相關(guān)假設(shè)

因為建立的模型是理想中的情況，所以需進行如下幾條假設(shè)：

（1）只考慮一種類型的貨物運輸。

（2）運輸所產(chǎn)生的費用與運輸量和運輸距離成正比。

（3）假設(shè)在運輸?shù)倪^程中貨物保存完好，不考慮無人機因為發(fā)生意外情況而導致的貨物損失和配送時間的延誤。

（4）只考慮一種型號的無人機進行貨物的配送，并且所有無人機的運輸速度恒定且一致。

（5）不考慮貨物裝卸搬運所需要的時間及成本，不考慮貨物到達需求點之后所需要的服務時間及成本，不考慮各配送地區(qū)的地面路網(wǎng)結(jié)構(gòu)。

2.4 相關(guān)符號說明

本文模型公式中所用符號及意義說明如表1所示：

表1公式中各符號及其代表意義說明

2.5LRP模型的建立。本文所建立的物流末端配送無人機起降點選址分配模型是雙層規(guī)劃模型，將普通物流配送中心選址分配的約束條件和物流末端配送無人機的本身性能約束考慮其中，從物流末端配送無人機的運營企業(yè)和其服務的客戶雙重角度來建立物流末端配送無人機起降點LRP模型。可以建立物流末端配送無人機起降點的LRP模型，模型如下所示：

3.物流無人機起降點選址算法設(shè)計。

上述模型為LRP問題（Location-Routing Problems），實例中數(shù)據(jù)較多且考慮的約束條件也較為復雜，故設(shè)計遺傳算法來進行求解。

3.1 算法設(shè)計方案

根據(jù)本文所建的模型，對遺傳算法的每一步操作有如下具體設(shè)置：

（1）編碼。利用遺傳算法求解問題時，首先要確定問題的目標函數(shù)和變量，然后對變量進行編碼，這樣做主要是因為在遺傳算法中，問題的解是用數(shù)字串來表示的，而且遺傳算子也是直接對串進行操作的。

（2）生成初試種群。本文通過隨機產(chǎn)生的方式，根據(jù)連同路徑的判斷和空域性質(zhì)兩個方面來判斷該起降點是否可以被選擇，使用blockId=0表示對起降點的禁用。在滿足了約束條件的情況下，生成對應規(guī)模大小的初始種群。

（3）設(shè)置適應度函數(shù)。由于本文設(shè)置了雙層規(guī)劃有兩個目標函數(shù)，而且兩個函數(shù)中既包含了最大值優(yōu)化問題又包含了最小值優(yōu)化問題，因此設(shè)置如下適應度函數(shù)：

（4）選擇。選擇是指從群體中選擇優(yōu)良個體并淘汰劣質(zhì)個體的操作，本文使用的是自然選擇的方法，適應度高的幾個個體將會進入下一代，剩余的個體以個體適應度占總體適應度的比例為條件進行擇優(yōu)篩選。

（5）染色體交叉。交叉就是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新的個體的操作。通過設(shè)置復制概率，以輪盤賭法選擇父代染色體，把兩個父代染色體的部分結(jié)構(gòu)進行交叉而生成新的個體。

（6）染色體變異。變異就是以很小的變異概率隨機地改變種群中個體的某些基因的值。通過設(shè)置變異概率，隨機選擇染色體基因片段進行變異重組。

（7）終止條件。本文以設(shè)置的迭代次數(shù)為終止條件。

4.實際算例分析（以呼和浩特市為例）。

呼和浩特市下轄的所有旗縣中，因為地理位置因素無法將武川縣和土默特右旗考慮到本文研究的范圍內(nèi)，因此本文以和林格爾縣、托克托縣和清水河縣為研究區(qū)域。本文平衡了物流末端配送無人機起降點的選址分配總成本和客戶時間滿意度兩個目標，研究林格爾縣、托克托縣和清水河縣地區(qū)的物流末端配送無人機起降點最佳選址分配方案。

在所研究的目標區(qū)域內(nèi)，主要的鄉(xiāng)鎮(zhèn)坐標位置及每個鄉(xiāng)鎮(zhèn)的配送重量如表2所示：

表2各鄉(xiāng)鎮(zhèn)的坐標位置及配送重量

通過大量文獻的閱讀及網(wǎng)絡上相關(guān)內(nèi)容的查找，物流末端配送無人機起降點的參數(shù)如下表所示：

表3物流末端配送無人機起降點參數(shù)

對市場的幾種主流的物流配送無人機進行對比，本文選取其中一種體形大小合適實際情況的無人機的參數(shù)，參數(shù)如表4所示：

表4物流末端配送那個無人機參數(shù)

利用上述數(shù)據(jù)資料，使用遺傳算法通過MATLAB進行求解，可得出一下選址結(jié)果和算法收斂曲線，由圖可知算法收斂良好，得出6個末端配送無人機起降點。

5.結(jié)束語。

本文考慮了無人機配送商品的重量對無人機續(xù)航里程的影響、最大載貨量和起降點容量等因素，通過構(gòu)建成本最小和顧客滿意度的雙層LRP模型，結(jié)合呼和浩特周邊地區(qū)的實際情況，并使用免疫遺傳算法對模型進行求解，最終得出最優(yōu)的物流末端配送無人機的最優(yōu)選址位置為：城關(guān)鎮(zhèn)（和林格爾縣）、盛樂鎮(zhèn)、雙河鎮(zhèn)、宏河鎮(zhèn)、窯溝鄉(xiāng)和城關(guān)鎮(zhèn)（清水河縣）。

圖3免疫遺傳算法求解結(jié)果

圖4免疫遺傳算法收斂曲線