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

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

1.文獻(xiàn)綜述。

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

2.LRP模型建立

2.1 問(wèn)題描述

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

圖1物流末端配送無(wú)人機(jī)起降點(diǎn)的配送模式示意圖

2.2 客戶時(shí)間滿意度

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

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

圖2中所示，客戶時(shí)間滿意度（S（tij））的取值范圍為[0，1]，0表示客戶完全不滿意，1表示客戶完全滿意。tij表示商品從物流末端配送無(wú)人機(jī)起降點(diǎn)i開(kāi)始配送處理到將貨物運(yùn)送至需求點(diǎn)j的服務(wù)時(shí)間，tE表示客戶對(duì)商品送達(dá)感到完全滿意的最長(zhǎng)維持時(shí)間，tL表示客戶對(duì)商品送達(dá)感到完全不滿意的最短維持時(shí)間。

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

因?yàn)榻⒌哪Ｐ褪抢硐胫械那闆r，所以需進(jìn)行如下幾條假設(shè)：

（1）只考慮一種類型的貨物運(yùn)輸。

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

（3）假設(shè)在運(yùn)輸?shù)倪^(guò)程中貨物保存完好，不考慮無(wú)人機(jī)因?yàn)榘l(fā)生意外情況而導(dǎo)致的貨物損失和配送時(shí)間的延誤。

（4）只考慮一種型號(hào)的無(wú)人機(jī)進(jìn)行貨物的配送，并且所有無(wú)人機(jī)的運(yùn)輸速度恒定且一致。

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

2.4 相關(guān)符號(hào)說(shuō)明

本文模型公式中所用符號(hào)及意義說(shuō)明如表1所示：

表1公式中各符號(hào)及其代表意義說(shuō)明

2.5LRP模型的建立。本文所建立的物流末端配送無(wú)人機(jī)起降點(diǎn)選址分配模型是雙層規(guī)劃模型，將普通物流配送中心選址分配的約束條件和物流末端配送無(wú)人機(jī)的本身性能約束考慮其中，從物流末端配送無(wú)人機(jī)的運(yùn)營(yíng)企業(yè)和其服務(wù)的客戶雙重角度來(lái)建立物流末端配送無(wú)人機(jī)起降點(diǎn)LRP模型?？梢越⑽锪髂┒伺渌蜔o(wú)人機(jī)起降點(diǎn)的LRP模型，模型如下所示：

3.物流無(wú)人機(jī)起降點(diǎn)選址算法設(shè)計(jì)。

上述模型為L(zhǎng)RP問(wèn)題（Location-Routing Problems），實(shí)例中數(shù)據(jù)較多且考慮的約束條件也較為復(fù)雜，故設(shè)計(jì)遺傳算法來(lái)進(jìn)行求解。

3.1 算法設(shè)計(jì)方案

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

（1）編碼。利用遺傳算法求解問(wèn)題時(shí)，首先要確定問(wèn)題的目標(biāo)函數(shù)和變量，然后對(duì)變量進(jìn)行編碼，這樣做主要是因?yàn)樵谶z傳算法中，問(wèn)題的解是用數(shù)字串來(lái)表示的，而且遺傳算子也是直接對(duì)串進(jìn)行操作的。

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

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

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

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

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

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

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

呼和浩特市下轄的所有旗縣中，因?yàn)榈乩砦恢靡蛩責(zé)o法將武川縣和土默特右旗考慮到本文研究的范圍內(nèi)，因此本文以和林格爾縣、托克托縣和清水河縣為研究區(qū)域。本文平衡了物流末端配送無(wú)人機(jī)起降點(diǎn)的選址分配總成本和客戶時(shí)間滿意度兩個(gè)目標(biāo)，研究林格爾縣、托克托縣和清水河縣地區(qū)的物流末端配送無(wú)人機(jī)起降點(diǎn)最佳選址分配方案。

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

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

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

表3物流末端配送無(wú)人機(jī)起降點(diǎn)參數(shù)

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

表4物流末端配送那個(gè)無(wú)人機(jī)參數(shù)

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

5.結(jié)束語(yǔ)。

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

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

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