多倉(cāng)庫(kù)下物流無(wú)人機(jī)協(xié)同配送方法

杜鵬飛，何 翔，張學(xué)軍，2

（1.西華大學(xué)航空航天學(xué)院，四川成都 610039；2.北京航空航天大學(xué)電子信息與工程學(xué)院，北京 100191）

0 引言

隨著電子商務(wù)快遞業(yè)的快速發(fā)展，物流配送量與日俱增。當(dāng)前，傳統(tǒng)的地面車輛配送很難在短時(shí)間內(nèi)配送大批量的包裹，且車輛易受到地形的影響，使得配送成本和配送時(shí)間大大增加。在此背景下，物流無(wú)人機(jī)逐漸興起，并具有巨大的發(fā)展前景[1]，它可以有效提高配送效率。但大多數(shù)無(wú)人機(jī)存在電能不足、續(xù)航時(shí)間短等問(wèn)題[2-3]。因?yàn)樵谖锪髋渌椭校瑸樘岣吲渌托?、減少配送成本，就需要進(jìn)一步考慮任務(wù)協(xié)同分配[4]。所以，科學(xué)規(guī)劃配送路線變得尤為重要。

在針對(duì)無(wú)人機(jī)配送建模中，大多是對(duì)無(wú)人機(jī)飛行范圍、飛行時(shí)間等進(jìn)行簡(jiǎn)單約束，構(gòu)建的模型無(wú)法滿足實(shí)際的配送需求。因此，精確估計(jì)載重、能耗等因素對(duì)于配送的影響至關(guān)重要。當(dāng)前，很多研究者[5-8]在進(jìn)行無(wú)人機(jī)路徑優(yōu)化過(guò)程中，充分考慮了路徑長(zhǎng)度、安全風(fēng)險(xiǎn)以及燃料損耗等目標(biāo)，并通過(guò)加權(quán)求和，將這些目標(biāo)轉(zhuǎn)化為單目標(biāo)問(wèn)題。

文獻(xiàn)[9]提出無(wú)人機(jī)和卡車存在同一個(gè)配送網(wǎng)絡(luò)的問(wèn)題，在建模中綜合考慮了載重的變化。在對(duì)多倉(cāng)庫(kù)配送問(wèn)題的解決方案中，文獻(xiàn)[10]構(gòu)建了1 個(gè)新的整數(shù)線性規(guī)劃模型，該模型允許在目標(biāo)函數(shù)內(nèi)體現(xiàn)倉(cāng)庫(kù)位置和路線的優(yōu)化。文獻(xiàn)[11]考慮了不同倉(cāng)庫(kù)間車輛的共享，得出共享的車輛資源可以潛在地減少交付距離和燃料消耗。文獻(xiàn)[12]提出了K互連多站多旅行推銷員問(wèn)題，并提出了1 種基于超啟發(fā)式的人工蜂群算法。文獻(xiàn)[13]采用邊界分配法將該問(wèn)題轉(zhuǎn)化為單倉(cāng)庫(kù)車輛調(diào)度問(wèn)題，并結(jié)合遺傳算法（Genetic Algorithm，GA）與蟻群算法求解跨區(qū)域配送最優(yōu)調(diào)度方案。文獻(xiàn)[14]用聚類分析最短距離分配法，將多倉(cāng)庫(kù)車輛調(diào)度問(wèn)題動(dòng)態(tài)地分解為多個(gè)單倉(cāng)庫(kù)車輛調(diào)度問(wèn)題進(jìn)行求解。針對(duì)求解規(guī)劃問(wèn)題時(shí)存在易陷入局部最優(yōu)的問(wèn)題，文獻(xiàn)[15]在求解無(wú)人機(jī)路徑的基礎(chǔ)上，基于傳統(tǒng)PSO 的基礎(chǔ)上，引入細(xì)菌覓食算法，有效提高了尋優(yōu)能力。文獻(xiàn)[16]針對(duì)傳統(tǒng)的粒子群優(yōu)化算法容易陷入局部最優(yōu)解的問(wèn)題，提出了1 種自適應(yīng)粒子群優(yōu)化算法，在迭代尋優(yōu)過(guò)程中自適應(yīng)地調(diào)節(jié)慣性權(quán)重和2個(gè)學(xué)習(xí)因子的數(shù)值。文獻(xiàn)[17]針對(duì)多基地?zé)o人機(jī)協(xié)同規(guī)劃航跡計(jì)算復(fù)雜、容易陷入局部最優(yōu)的問(wèn)題，在GAPSO的基礎(chǔ)上，引入禁忌搜索算法混合為GAPSO-TS算法。文獻(xiàn)[18]提到了基于深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的任務(wù)分配研究在未來(lái)研究中的趨勢(shì)。

當(dāng)前的研究中，針對(duì)建模，各個(gè)模型考慮的因素有限，無(wú)法貼合物流配送真實(shí)場(chǎng)景。同時(shí)還需注意到，針對(duì)算法的改進(jìn)，主要是通過(guò)改進(jìn)操作算子以及融合其他算法以提高算法的搜索能力，進(jìn)一步獲取成本更優(yōu)的配送方案?；诖?，本文在允許無(wú)人機(jī)攜帶多個(gè)包裹的情況下，考慮了無(wú)人機(jī)的能耗變化、顧客混合時(shí)間窗以及同時(shí)取送貨情況，構(gòu)建多倉(cāng)庫(kù)物流配送模型。考慮到GA存在收斂速度慢的問(wèn)題，基于GA引入LNS（Large Neighborhood Search Algorithm，LNS）用作局部搜索算子提出基于改進(jìn)GA（Improved GA，IGA）的物流無(wú)人機(jī)協(xié)同配送算法，利用GA 的全局搜索和LNS局部搜索的優(yōu)化機(jī)制進(jìn)行求解，進(jìn)一步獲取最優(yōu)配送方案。

1 配送問(wèn)題建模

1.1 問(wèn)題描述

設(shè)定某城市區(qū)域存在多個(gè)倉(cāng)庫(kù)和若干個(gè)顧客需求點(diǎn)，引入移動(dòng)充電樁給物流無(wú)人機(jī)更換電池以提高無(wú)人機(jī)的飛行時(shí)長(zhǎng)。在配送的過(guò)程中，可以到距離最近的充電樁充電。本文做以下假設(shè)。

1）網(wǎng)絡(luò)中包含兩類節(jié)點(diǎn)：第一類是倉(cāng)庫(kù)，倉(cāng)庫(kù)是無(wú)人機(jī)的出發(fā)和返回點(diǎn)；第二類是顧客點(diǎn)，每1個(gè)顧客都包含服務(wù)時(shí)間窗、服務(wù)時(shí)間、包裹需求以及寄送量等需求。

2）顧客的時(shí)間窗設(shè)定為混合時(shí)間窗模式，該模式包含軟時(shí)間窗和硬時(shí)間窗。

3）針對(duì)顧客的取送貨情況可分為3種情況，分別是同時(shí)有取貨和寄貨需求的顧客、只有取貨需求的顧客以及只有寄貨需求的顧客。無(wú)人機(jī)對(duì)3種類型顧客的服務(wù)時(shí)間不同。

4）無(wú)人機(jī)在配送過(guò)程中處于耗能狀態(tài)，耗能速率隨著載重而變化。

5）無(wú)人機(jī)的出發(fā)和返回配送站可以不同。

1.2 模型構(gòu)建

1）參數(shù)與變量。本文涉及的參數(shù)如表1所示。

表1 參數(shù)定義Tab.1 Parameter definition

2）目標(biāo)函數(shù)。本模型以優(yōu)化經(jīng)濟(jì)成本為主，其中，根據(jù)無(wú)人機(jī)配送能量消耗過(guò)程建立模型[19]，電池功率表示為：

式（1）中：Pij為無(wú)人機(jī)從顧客i到顧客j時(shí)的飛行功率；W為無(wú)人機(jī)本身質(zhì)量；l為無(wú)人機(jī)的載重；vij為無(wú)人機(jī)從顧客i到顧客j的速率；η為螺旋槳?jiǎng)恿鬟f效率；γ為無(wú)人機(jī)升阻比；e為無(wú)人機(jī)電子元件能耗?？紤]到電子元件耗能所占比重較小，因而在本文中不予考慮。

本文假設(shè)無(wú)人機(jī)以恒定速率飛行，則無(wú)人機(jī)從顧客i到顧客j之間消耗的電能可以表示為：

物流無(wú)人機(jī)協(xié)同配送的總目標(biāo)是使得物流配送產(chǎn)生的成本最小，目標(biāo)函數(shù)為式（3），其中：第1項(xiàng)為無(wú)人機(jī)在配送過(guò)程中的能耗成本；第2 項(xiàng)為無(wú)人機(jī)單次飛行的固定成本；第3 項(xiàng)為無(wú)人機(jī)違反顧客時(shí)間窗的懲罰成本。

3）約束條件：

針對(duì)無(wú)人機(jī)的約束，式（4）為0、1 變量，表示對(duì)于無(wú)人機(jī)k、顧客i與顧客j的路徑是否聯(lián)通；式（5）表示i點(diǎn)完成飛行的無(wú)人機(jī)數(shù)量等于在i點(diǎn)開(kāi)始飛行的無(wú)飛機(jī)數(shù)量；針對(duì)載重的約束，式（6）表示每1 架無(wú)人機(jī)的載重量不得超過(guò)其最大載重；式（7）為保證無(wú)人機(jī)在2個(gè)顧客之間的載重約束；式（8）表示無(wú)人機(jī)從倉(cāng)庫(kù)出發(fā)時(shí)的載重為所經(jīng)顧客的送貨量之和；式（9）表示無(wú)人機(jī)返回倉(cāng)庫(kù)的載重為所經(jīng)顧客的寄貨量之和；針對(duì)時(shí)間窗的約束，式（10）（11）表示節(jié)點(diǎn)與節(jié)點(diǎn)之間的到達(dá)時(shí)間的關(guān)系；針對(duì)電能的約束，式（12）表示無(wú)人機(jī)在顧客點(diǎn)的電能均應(yīng)小于最大電能E；式（13）表示無(wú)人機(jī)在2個(gè)顧客之間的飛行能耗剩余值之差等于其飛行過(guò)程中產(chǎn)生的能耗之和；式（14）表示無(wú)人機(jī)離開(kāi)顧客i時(shí)的電能必須保證其到達(dá)顧客j。

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

針對(duì)各種啟發(fā)式算法的特點(diǎn)，本文使用基于GA對(duì)所提模型進(jìn)行優(yōu)化求解?；贕A與LNS的各自特點(diǎn)，在GA 中引入LNS 作為局部搜索算子，提出基于IGA的物流無(wú)人機(jī)協(xié)同配送算法

2.1 初始解的構(gòu)造

在遺傳算法中，初始解的構(gòu)造是操作算子的基礎(chǔ)，其使用實(shí)數(shù)進(jìn)行編碼，規(guī)則如下。

1）將顧客隨機(jī)排列，按照序列依次添加客戶點(diǎn)。

2）判斷添加的顧客點(diǎn)是否滿足無(wú)人機(jī)載重約束和顧客時(shí)間窗約束。若不滿足，則判斷是否能夠直接添加倉(cāng)庫(kù)；若可以直接添加倉(cāng)庫(kù)，則添加倉(cāng)庫(kù)。

3）在判斷無(wú)人機(jī)滿足載重和顧客時(shí)間窗約束后，繼續(xù)判斷是否滿足能耗要求。若能耗要求被滿足，則直接將顧客點(diǎn)加入解碼序列之中。

4）當(dāng)該路徑不符合載重約束或者能耗約束，則儲(chǔ)存該條路徑，同時(shí)新增無(wú)人機(jī)架次。

重復(fù)上述步驟，直到將每個(gè)顧客點(diǎn)都加入編碼之中。考慮倉(cāng)庫(kù)會(huì)隨著顧客分布而變化，因而在該解碼序列中，倉(cāng)庫(kù)先不加入。在解碼時(shí)，使用最近鄰插入法，單獨(dú)獲取每1條路線的所屬倉(cāng)庫(kù)，進(jìn)一步計(jì)算目標(biāo)函數(shù)值。

直接編碼法[20-21]是將充電樁直接編入染色體編碼中。在本模型中，即將無(wú)人機(jī)經(jīng)過(guò)的所有顧客和充電樁都編入染色體編碼中，但考慮到倉(cāng)庫(kù)的特性，不將其編入染色體編碼，而將其以1 個(gè)符號(hào)表示。該編碼流程較為直觀，考慮了場(chǎng)景中各個(gè)元素，無(wú)須后期再插入充電樁。但是該方法也存在缺陷，最優(yōu)的充電樁位置會(huì)隨著算法的迭代而改變，甚至?xí)霈F(xiàn)配送路線無(wú)法滿足約束條件。

最近插入法[22]表現(xiàn)為充電樁編碼不參與直接編碼。在編碼中，只編入倉(cāng)庫(kù)和顧客的編碼。在解碼時(shí)，再考慮向配送方案中結(jié)合能耗需求選擇最合適的充電樁。解碼后的配送方案是否滿足載重約束以及時(shí)間窗約束，還需進(jìn)一步判斷。該編碼中，插入位置為沒(méi)有充足電能的位置，無(wú)法在全局層面實(shí)現(xiàn)插入最優(yōu)。

基于最近插入法提出綜合插入法，即考慮到插入位置的全局最優(yōu)，即不局限于向電能不足處插入充電樁，而是從整條路徑出發(fā)，選擇最合適的插入位置和充電樁。

2.2 局部搜索

考慮到遺傳算法在求解模型的過(guò)程中收斂速度較慢，為提高算法搜索速度，在遺傳算法的基礎(chǔ)上加入局部搜索算子。本文引用了LNS的相關(guān)概念，通過(guò)移出和重新插入2 個(gè)過(guò)程，對(duì)染色體進(jìn)行局部搜索。LNS包含破壞（Destroy）算子和修復(fù)（Repair）算子。破壞算子的作用是采用相關(guān)性原則從當(dāng)前個(gè)體中移除若干個(gè)顧客；修復(fù)算子的作用是在滿足載重和時(shí)間窗約束的前提下，將移除的顧客插回到使車輛行駛總距離增加最少的位置。若修復(fù)后的個(gè)體成本小于破壞前的個(gè)體成本，則用修復(fù)后的個(gè)體替代破壞前的個(gè)體。

2.3 算法流程

IGA 流程為：隨機(jī)生成初始種群，再進(jìn)行選擇、變異、交叉和局部搜索。IGA的流程如圖1所示。

圖1 IGA流程Fig.1 IGA process

3 仿真及結(jié)果分析

3.1 仿真測(cè)試pm

為驗(yàn)證模型和算法的有效性，結(jié)合算法對(duì)模型進(jìn)行優(yōu)化求解。為了能夠直觀地展示本文仿真試驗(yàn)結(jié)果，本節(jié)以顧客數(shù)量為50 的配送優(yōu)化方案為例。其中，顧客位置按照均勻分布隨機(jī)生成，送貨量在小于無(wú)人機(jī)最大載重范圍內(nèi)隨機(jī)生成，服務(wù)時(shí)間窗參考Solomn 數(shù)據(jù)C101 進(jìn)行設(shè)定。本模型中，參數(shù)設(shè)置如表2所示。顧客、倉(cāng)庫(kù)和移動(dòng)充電樁分布如圖2所示。

圖2 倉(cāng)庫(kù)和充電樁分布圖Fig.2 Distribution of warehouse and charging station

表2 模型參數(shù)值Tab.2 Model parameter value

本模型使用IGA和GA同時(shí)對(duì)模型進(jìn)行求解獲取最優(yōu)配送成本。為尋找最佳任務(wù)分配方案，取20次重復(fù)仿真實(shí)驗(yàn)中算法適應(yīng)度值最小的1 次實(shí)驗(yàn)結(jié)果，繪制其對(duì)應(yīng)的迭代曲線如圖3 所示。從圖3 可以看出，通過(guò)對(duì)比算法獲取最優(yōu)配送成本，該算法在初期就顯示出較快的收斂速度。在迭代200次時(shí)便已經(jīng)得到了較好的結(jié)果，表現(xiàn)出了較強(qiáng)的搜索能力。圖3中，IGA獲取的最優(yōu)配送經(jīng)濟(jì)成本為3 023元，GA為3 264元，IGA 較GA 顯著降低了配送經(jīng)濟(jì)成本（降低了7.38%）?？梢哉f(shuō)，IGA在降低物流配送成本方面具有明顯的作用。經(jīng)檢驗(yàn)，各架無(wú)人機(jī)均滿足自身能耗和載重約束要求，進(jìn)一步驗(yàn)證了算法的有效性。獲取種群平均配送成本變化值，如圖4所示，平均成本在前期下降之后，相對(duì)穩(wěn)定?？梢缘贸?，該算法對(duì)于種群的優(yōu)化效果是顯著的。

圖3 經(jīng)濟(jì)成本優(yōu)化過(guò)程Fig.3 Economic cost optimization process

圖4 平均成本變化圖Fig.4 Changes in average cost

在此條件下，進(jìn)一步獲取種群的平均配送距離變化值，如圖5所示。

圖5 平均配送距離變化圖Fig.5 Change in average distribution distance

由于在優(yōu)化過(guò)程中配送距離并非首要優(yōu)化目標(biāo)，因而在優(yōu)化過(guò)程中的浮動(dòng)相對(duì)較大，這是因?yàn)橛绊懪渌徒?jīng)濟(jì)成本的因素不只有配送距離，還有違反時(shí)間窗總時(shí)長(zhǎng)，但同時(shí)配送距離可以直接影響到配送經(jīng)濟(jì)成本。隨著迭代次數(shù)地增長(zhǎng)，種群平均配送距離呈現(xiàn)隨著迭代過(guò)程逐漸下降且逐漸趨于平穩(wěn)的過(guò)程。

3.2 Solomn數(shù)據(jù)驗(yàn)證

為驗(yàn)證上述方法的有效性，用所提方法IGA 對(duì)Solomn數(shù)據(jù)集進(jìn)行仿真測(cè)試。在此測(cè)試中，考慮到數(shù)據(jù)集顧客需求與原設(shè)定無(wú)人機(jī)最大載重不相符，故設(shè)定無(wú)人機(jī)最大載重為60 kg，測(cè)試10 次取其平均值記錄于表3。通過(guò)求解不同規(guī)模算例發(fā)現(xiàn)，在同一個(gè)算例系列中，隨著顧客點(diǎn)比例增大，無(wú)人機(jī)的配送成本呈上升趨勢(shì)。通過(guò)無(wú)人機(jī)的使用量發(fā)現(xiàn)，同一個(gè)算例系列中，隨著顧客點(diǎn)比例增大，無(wú)人機(jī)數(shù)量有所增長(zhǎng)。通過(guò)將IGA 與GA 的求解結(jié)果進(jìn)行對(duì)照，進(jìn)一步驗(yàn)證了所提算法的有效性。同時(shí)，在數(shù)量較少的算例中，各個(gè)算法求解的最優(yōu)成本幾乎一致，隨著顧客數(shù)量增多，IGA求解效果更加顯著，即該算法獲取的最優(yōu)配送成本。

表3 Solomn數(shù)據(jù)驗(yàn)證結(jié)果Tab.3 Verification results of solomn data

4 結(jié)論

本文基于城市區(qū)域無(wú)人機(jī)配送場(chǎng)景，構(gòu)建了以經(jīng)濟(jì)成本最小為目標(biāo)函數(shù)的多機(jī)協(xié)同任務(wù)分配模型。為提高GA 的尋優(yōu)能力，在GA 的基礎(chǔ)上加入LNS 局部搜索算子，進(jìn)而提出IGA 對(duì)所提模型進(jìn)行尋優(yōu)求解。仿真實(shí)驗(yàn)表明，基于IGA的物流無(wú)人機(jī)協(xié)同配送算法可以有效實(shí)現(xiàn)多目標(biāo)優(yōu)化，適合解決城市環(huán)境下多倉(cāng)庫(kù)的任務(wù)分配問(wèn)題。同時(shí)，為進(jìn)一步明確算法的有效性，通過(guò)引入Solomn進(jìn)行測(cè)試，仿真結(jié)果顯示，所提IGA可以有效降低物流配送成本。