為了更好地推進(jìn)城市無人機(jī)物流配送，需要解決選址-分配問題(LAP)。LAP最早由Curry, Skeith[3]于1969年提出。現(xiàn)階段關(guān)于無人機(jī)的選址-分配研究，劉正元，王清華[4]提出無人機(jī)應(yīng)急物流任務(wù)分配模型，為戰(zhàn)場應(yīng)急物資配送提供指導(dǎo)。陳剛，付江月[5]研究在軍民融合戰(zhàn)略背景下，基于需求點(diǎn)和配送中心類型建立無人機(jī)配送中心選址分配模型，并通過算例分析對模型進(jìn)行驗(yàn)證，以期為特殊情況下無人機(jī)配送布局提供支持與幫助。Chauhan D等[6]以需求覆蓋范圍最大化為目標(biāo)，考慮無人機(jī)能耗與飛行限制的影響，建立解決無人機(jī)最大覆蓋設(shè)施位置問題的模型，并通過真實(shí)案例進(jìn)行分析，從而明確無人機(jī)設(shè)施的選址點(diǎn)。劉光才，馬寅松[7]研究了城市無人機(jī)配送中心選址及任務(wù)分配問題，構(gòu)建了多約束條件下的模型，設(shè)計(jì)了改進(jìn)模擬退火遺傳算法，達(dá)到預(yù)期效果。

綜上可知，當(dāng)前關(guān)于無人機(jī)選址-分配問題的研究多針對軍事作戰(zhàn)領(lǐng)域，關(guān)于城市無人機(jī)物流配送這一特定場景下的LAP研究較少，沒有綜合考慮到城市、企業(yè)和客戶三個(gè)視角。因此，本文考慮城市物流“最后一公里”配送需求，建立城市物流無人機(jī)選址-分配模型，并設(shè)計(jì)遺傳-粒子群算法求解出優(yōu)化方案。

1 數(shù)學(xué)模型建立

1.1 問題描述

在存在禁飛區(qū)或障礙區(qū)的城市區(qū)域內(nèi)，已知每個(gè)備選配送中心的位置、建設(shè)成本和每個(gè)需求點(diǎn)的坐標(biāo)、需求量等信息，根據(jù)區(qū)域范圍內(nèi)所有客戶需求選取位置最合適的多個(gè)配送中心，將多個(gè)配送任務(wù)分配給不同配送中心的多架無人機(jī)執(zhí)行，每架無人機(jī)裝載規(guī)定重量的貨物，從配送中心出發(fā)，分別飛往各個(gè)需求點(diǎn)，并且在完成配送任務(wù)后空載返回配送中心。當(dāng)選擇的配送中心與需求點(diǎn)之間存在禁飛區(qū)域或障礙區(qū)域，則該需求點(diǎn)的配送不選擇此配送中心(圖1)。

1.2 模型假設(shè)

為便于深入研究，本模型的主要假設(shè)如下：

①每個(gè)需求點(diǎn)的位置和需求量已知且恒定，在一定時(shí)間內(nèi)無波動(dòng)；

②每個(gè)需求點(diǎn)由一個(gè)配送中心(一架無人機(jī))配送，每個(gè)配送中心可以覆蓋多個(gè)需求點(diǎn)；

③物流無人機(jī)在配送過程中保持勻速，且忽略無人機(jī)起飛和降落過程；

④忽略自然天氣對無人機(jī)配送過程的影響；

⑤在進(jìn)行任務(wù)分配時(shí)，每架無人機(jī)單次只能為一個(gè)需求點(diǎn)服務(wù)，在完成需求點(diǎn)配送任務(wù)之后空載按原路返回配送中心。

1.3 目標(biāo)函數(shù)構(gòu)建

本模型以總成本最小為目標(biāo)，包括建設(shè)成本C1、配送成本C2、耗電成本C3以及碳排放環(huán)境成本C4四個(gè)部分：

minC=C1+C2+C3+C4(1)

①配送中心建設(shè)成本。Xj=1或0表示是否在j點(diǎn)建設(shè)配送中心，固定建設(shè)成本為f。

C1=∑j∈JXj⋅f$?{}_1={\displaystyle \sum _{?\in ?}?}{}_{?}\cdot ?$(2)

②配送成本。每架參與配送的無人機(jī)，在一次可行的任務(wù)分配方案中，飛行距離dkji${}_{??}^{?}$與單位損耗成本λij的乘積為配送成本。Ykij${}_{??}^{?}$=1或0,表示是否用無人機(jī)k來完成j配送中心對i客戶的配送；Zkij${}_{??}^{?}$=1或0,表示是否配送路徑上不存在障礙。

C2=∑i∈I∑j∈J∑k∈Kdkji⋅λij⋅Ykij⋅Zkij$?{}_2={\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}?}}}{}_{??}^{?}\cdot ?{}_{??}\cdot ?{}_{??}^{?}\cdot ?{}_{??}^{?}$(3)

③耗電成本。耗電成本通過無人機(jī)的能耗E與單位電價(jià)p的乘積來表示。

C3=E·p (4)

與無人機(jī)的自重相比，每個(gè)包裹的重量都不容忽視。能耗[8]與自重φ和實(shí)時(shí)載荷Wkij${}_{??}^{?}$相關(guān)，可表示為：

E=∑i∈I∑j∈J∑k∈K(φ+Wkij)⋅dij⋅P370⋅η⋅γ⋅(P−e)$?={\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}}}}\frac{(?+?{}_{??}^{?})\cdot ?{}_{??}\cdot ?}{370\cdot ?\cdot ?\cdot (?-?)}$(5)

其中，η是電機(jī)的轉(zhuǎn)換效率，γ是升阻比，e是無人機(jī)電池的能量損失，P為無人機(jī)最大飛行功率。

④碳排放環(huán)境成本。二氧化碳排放環(huán)境成本是指減少二氧化碳排放所產(chǎn)生的環(huán)境損失所需的費(fèi)用。無人機(jī)在配送流程中只需要考慮上游企業(yè)發(fā)電所產(chǎn)生的碳排放，碳排放量的計(jì)算與電網(wǎng)排放因子θ有關(guān)。因此，電動(dòng)無人機(jī)的二氧化碳排放環(huán)境成本可表示為：

C4=E·θ·α(6)

其中，α表示單位碳排放環(huán)境成本。

1.4 約束條件說明

①啟用的配送中心數(shù)量約束。

啟用的配送中心個(gè)數(shù)不大于備選配送中心的數(shù)量A。

∑j∈JXj≤A${\displaystyle \sum _{?\in ?}?}{}_{?}\le ?$(7)

②配送中心最大配送能力約束。

一個(gè)配送中心最多能為m個(gè)客戶點(diǎn)服務(wù)。

∑i∈IXji≤m,∀j∈J${\displaystyle \sum _{?\in ?}?}{}_{??}\le ?,\forall ?\in ?$(8)

③配送點(diǎn)可執(zhí)行任務(wù)約束。

在一次可行的配送任務(wù)中，需要滿足j地建設(shè)有配送中心，且用k無人機(jī)完成j地對i客戶的配送。

Ykij${}_{??}^{?}$≤Xj(9)

④無人機(jī)起降點(diǎn)位置約束。

無人機(jī)從配送中心出發(fā)完成配送任務(wù)后只能返回該配送中心，不能從一個(gè)配送中心出發(fā)后回到另一個(gè)配送中心。

∑i∈I∑k∈KXkji=∑i∈I∑k∈KXkij=1${\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}}}?{}_{??}^{?}={\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}}}?{}_{??}^{?}=1$(10)

∑j∈JXjj=0${\displaystyle \sum _{?\in ?}}?{}_{??}=0$(11)

⑤無人機(jī)最遠(yuǎn)里程約束。

分配給每架無人機(jī)的配送任務(wù)必須滿足一次往返飛行距離不大于無人機(jī)的單次最遠(yuǎn)飛行里程限制Dmax。

∑i∈I∑j∈J2⋅Yijdij≤Dmax${\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}2}}\cdot ?{}_{??}?{}_{??}\le ?{}_{\max }$(12)

⑥無人機(jī)最大載重約束。

無人機(jī)每次配送任務(wù)的載重不大于最大載重限制Wmax。

Wkij${}_{??}^{?}$≤Wmax(13)

2 算法設(shè)計(jì)

2.1 算法描述

在求解多配送中心選址-分配這類問題時(shí)，多采用智能化啟發(fā)式算法。遺傳算法和粒子群算法都是優(yōu)化領(lǐng)域的經(jīng)典算法，各自具有不同的優(yōu)點(diǎn)和適用場景。

粒子群算法具有較強(qiáng)的局部搜索能力，且收斂速度快，但容易導(dǎo)致種群喪失多樣性，容易陷入局部最優(yōu)。而遺傳算法具有較強(qiáng)的全局搜索能力，通過隨機(jī)概率進(jìn)行選擇、雜交、變異，這種概率性特點(diǎn)增加了種群多樣性，擴(kuò)大了搜索空間。將這兩種算法結(jié)合使用，可以取長補(bǔ)短，提高了算法的魯棒性和適應(yīng)性，發(fā)揮更強(qiáng)大的優(yōu)勢。

2.2 設(shè)計(jì)思路

①編碼。

遺傳算法的編碼方法直接影響到了交叉算子、變異算子等遺傳算子的運(yùn)算，因此很大程度上決定了遺傳進(jìn)化的效率[9]。本文采用符號(hào)編碼，設(shè)計(jì)m+n個(gè)基因表示配送中心選址和任務(wù)分配的結(jié)果，前m個(gè)基因作為客戶需求點(diǎn)的編碼，m+1至n為配送中心編碼。

②種群規(guī)模。

種群大小代表算法中可以并行搜索的解的數(shù)量，過小的種群可能會(huì)導(dǎo)致陷入局部最優(yōu)解；而過大的種群則會(huì)增加計(jì)算的復(fù)雜性，降低算法效率。

③適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)是衡量粒子優(yōu)劣的標(biāo)準(zhǔn)，以目標(biāo)函數(shù)作為本文算法的適應(yīng)度函數(shù)，總成本越小即目標(biāo)函數(shù)越小。

④選擇。

本文選用輪盤賭法選擇粒子，計(jì)算每個(gè)粒子的適應(yīng)度值，令fi為粒子i的適應(yīng)度值，∑fi為群體的適應(yīng)度值總和，那么粒子i產(chǎn)生后代的能力表示為fi/∑fi。

⑤交叉。

本文選用多點(diǎn)交叉方式，通過將父代染色體中的多個(gè)位置交換基因創(chuàng)建新的后代染色體。假設(shè)兩條父代染色體分別是[2 6 1 7 10]和[4 5 8 3 9],交叉點(diǎn)位置為1和4,那么產(chǎn)生的后代染色體為[4 6 1 3 10]和[2 5 8 7 9]。

⑥變異。

本文采用均勻變異算子作為變異方法，對一條染色體以相同的概率隨機(jī)改變基因值，設(shè)置變異概率的大小，若基因位置對應(yīng)的隨機(jī)數(shù)小于變異概率則發(fā)生變異，該基因變異為基因取值范圍內(nèi)的任意整數(shù)。

⑦迭代結(jié)束。

設(shè)置最大的迭代次數(shù)，當(dāng)?shù)螖?shù)達(dá)到最大值時(shí)，算法停止，返回當(dāng)前最優(yōu)解。

3 算例分析

3.1 仿真環(huán)境與參數(shù)設(shè)置

基于Python語言模擬某城市配送場景，在20km×20km區(qū)域范圍內(nèi)隨機(jī)生成36個(gè)客戶需求點(diǎn)、12個(gè)備選配送中心的坐標(biāo)位置以及客戶需求量。其中，“·”代表客戶需求點(diǎn)的位置和編號(hào)，黑體數(shù)字為客戶需求量，“○”表示備選配送中心的位置和編號(hào)(圖2)。

為了使城市無人機(jī)規(guī)劃過程盡量貼近實(shí)際配送場景，通過查閱文獻(xiàn)和走訪現(xiàn)代物流企業(yè)，設(shè)置模型的參數(shù)如表1所示。

3.2 結(jié)果分析

設(shè)置粒子群N=60,迭代次數(shù)MAXGEN=100,交叉概率Pc=0.8,變異概率Pm=0.05。分配方案如表2所示。

當(dāng)從12個(gè)備選無人機(jī)配送中心中選擇編號(hào)為2、4、7、8、9這5個(gè)配送中心時(shí)，適應(yīng)度函數(shù)值最優(yōu)，總飛行里程為313.90km,建設(shè)成本C1=10萬元，配送成本C2=188.34元，耗電成本為C3=242.48元，碳排放環(huán)境成本C4=58.45元。

3.3 敏感性分析

3.3.1 空域約束

保持其他參數(shù)不變，改變空域環(huán)境中障礙區(qū)域的位置和數(shù)量，生成的選址-分配結(jié)果如圖3所示。

當(dāng)障礙區(qū)域數(shù)量增多時(shí)，選擇2、4、8、9、11號(hào)配送中心成本最低，總飛行里程為338.2399km,配送中心建設(shè)成本C1=10萬元，配送成本C2=202.94元，耗電成本C3=261.62元，碳排放環(huán)境成本C4=62.99元。

當(dāng)障礙區(qū)域數(shù)量減少為0時(shí)，選擇2、4、7、8、9號(hào)配送中心成本最低，總飛行里程為310.3855km,配送中心建設(shè)成本C1=10萬元，配送成本C2=186.23元，耗電成本C3=240.08元，碳排放環(huán)境成本C4=57.81元。

結(jié)合圖2和圖3分析，城市無人機(jī)的配送中心選址-分配結(jié)果會(huì)受到空域環(huán)境中障礙數(shù)量和位置的影響。當(dāng)障礙區(qū)域數(shù)量較多時(shí)，配送中心需要承擔(dān)距離較遠(yuǎn)的配送需求，導(dǎo)致總成本上漲。

3.3.2 配送中心能力約束

保持其他參數(shù)不變，改變配送中心能力約束，生成選址-分配結(jié)果，如圖4所示。

當(dāng)配送中心的最大配送能力為6時(shí)(圖4(a)),需要啟用至少6個(gè)配送中心，此時(shí)的配送成本更小，但總成本因配送中心的啟用數(shù)量增加而顯著提升；當(dāng)配送中心的最大配送能力為9時(shí)(圖4(b)),配送中心的選址數(shù)量僅為4個(gè)，此時(shí)的配送成本更大，但總成本更小。

4 結(jié)語

本文針對單客戶配送場景，以建設(shè)成本、配送成本、與載重相關(guān)的耗電成本以及碳排放環(huán)境成本之和最小為目標(biāo)函數(shù)，以城市障礙區(qū)域、配送中心能力限制、無人機(jī)最大載重與最大續(xù)航里程等為約束條件，建立城市物流無人機(jī)配送中心選址-分配數(shù)學(xué)模型，設(shè)計(jì)遺傳-粒子群算法求解，最后基于Python程序設(shè)計(jì)驗(yàn)證了本文模型與算法的有效性。