佟 剛，陳子超，王 鋒，周國(guó)慶

（1.沈陽(yáng)航空航天大學(xué)，遼寧 沈陽(yáng) 110136；2.沈陽(yáng)航空航天大學(xué)通用航空重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng) 110136）

1 引言

隨著電子商務(wù)的快速發(fā)展，國(guó)內(nèi)物流產(chǎn)業(yè)呈現(xiàn)較快增長(zhǎng)。據(jù)資料顯示，2016年，全國(guó)社會(huì)物流總額為229.7萬(wàn)億元；2017年，全國(guó)社會(huì)物流總額252.8萬(wàn)億元，同比上漲10.06%，增長(zhǎng)速度比2016年提高0.6個(gè)百分點(diǎn)[1]。物流業(yè)已然成為國(guó)民經(jīng)濟(jì)發(fā)展的朝陽(yáng)產(chǎn)業(yè)，而隨著現(xiàn)代交通技術(shù)和信息技術(shù)的快速發(fā)展，物流行業(yè)逐漸由傳統(tǒng)以海陸運(yùn)輸方式為主轉(zhuǎn)換為現(xiàn)代海陸空立體運(yùn)輸方式，因此發(fā)展自動(dòng)化、智能化的現(xiàn)代物流配送體系是當(dāng)今物流行業(yè)迫切需要解決的問(wèn)題。其中城市區(qū)域及偏遠(yuǎn)山區(qū)的無(wú)人機(jī)物流方式因其快速方便、不受地面交通及地形影響、實(shí)用性強(qiáng)等優(yōu)點(diǎn)，成為了現(xiàn)代物流發(fā)展的新趨勢(shì)。

無(wú)人機(jī)物流系統(tǒng)以系統(tǒng)工程為依據(jù)，將現(xiàn)代信息技術(shù)作為系統(tǒng)核心，整合行業(yè)資源，優(yōu)化配送過(guò)程，提高無(wú)人機(jī)物流系統(tǒng)的經(jīng)濟(jì)性和實(shí)用性。目前無(wú)人機(jī)物流系統(tǒng)的實(shí)際應(yīng)用主要存在以下問(wèn)題：多目標(biāo)之間的航線規(guī)劃與約束條件的確定。無(wú)人機(jī)物流系統(tǒng)航線規(guī)劃是保證商品在配送過(guò)程中高效運(yùn)行的關(guān)鍵，主要涉及到調(diào)度、行程安排和任務(wù)路線三個(gè)問(wèn)題。與旅行商問(wèn)題類似，無(wú)人機(jī)物流系統(tǒng)航線規(guī)劃問(wèn)題為尋找最優(yōu)路徑。

無(wú)人機(jī)物流系統(tǒng)路徑規(guī)劃為多無(wú)人機(jī)協(xié)同路徑規(guī)劃，可有效提高無(wú)人機(jī)配送效率。文獻(xiàn)[2]將多無(wú)人機(jī)協(xié)同問(wèn)題轉(zhuǎn)換為車輛路徑規(guī)劃問(wèn)題，依此建立多無(wú)人機(jī)協(xié)同搜索系統(tǒng)。文獻(xiàn)[3]提出在多旅行商問(wèn)題模型中引入聚類算法進(jìn)行路徑優(yōu)化。文獻(xiàn)[4]利用Du‐bins曲線找到有效節(jié)點(diǎn)，結(jié)合A*搜索算法來(lái)圓滑任務(wù)路徑。

這里區(qū)別于傳統(tǒng)單目標(biāo)路徑規(guī)劃算法[5]，提出針對(duì)無(wú)人機(jī)物流系統(tǒng)，引入多目標(biāo)優(yōu)化算法來(lái)進(jìn)行路徑規(guī)劃，將單個(gè)物流無(wú)人機(jī)的路徑距離和各個(gè)物流無(wú)人機(jī)路徑距離的總和同時(shí)作為約束條件，保證在配送路徑總和最小的基礎(chǔ)上，單個(gè)物流無(wú)人機(jī)的路徑距離也最短，得到最優(yōu)路徑，從而使得無(wú)人機(jī)物流系統(tǒng)更具經(jīng)濟(jì)性。同時(shí)在多目標(biāo)優(yōu)化的基礎(chǔ)上，結(jié)合遺傳算法的全局搜索能力，有效的避免了尋優(yōu)過(guò)程中出現(xiàn)局部最優(yōu)解，從而保證系統(tǒng)解的多樣性[6?7]。

2 無(wú)人機(jī)物流系統(tǒng)及建模

2.1 無(wú)人機(jī)物流系統(tǒng)

無(wú)人機(jī)物流系統(tǒng)是指以無(wú)人機(jī)為主要運(yùn)輸載體，實(shí)現(xiàn)商品從集散點(diǎn)向投遞點(diǎn)配送而進(jìn)行的規(guī)劃、實(shí)施和控制的過(guò)程。無(wú)人機(jī)物流系統(tǒng)主要包括無(wú)人機(jī)干支線運(yùn)輸系統(tǒng)、區(qū)域級(jí)無(wú)人機(jī)配送系統(tǒng)、無(wú)人機(jī)應(yīng)急系統(tǒng)和無(wú)人機(jī)即時(shí)充電系統(tǒng)，其中地區(qū)級(jí)無(wú)人機(jī)配送系統(tǒng)為該系統(tǒng)研究的重點(diǎn)。無(wú)人機(jī)物流系統(tǒng)的優(yōu)點(diǎn)：

（1）配送距離短

物流無(wú)人機(jī)不會(huì)受到地形及地面交通的影響，升空后可直接點(diǎn)對(duì)點(diǎn)直線配送，大大節(jié)省配送時(shí)間。

（2）運(yùn)營(yíng)成本低廉

物流無(wú)人機(jī)在配送時(shí)具有較低的運(yùn)營(yíng)成本，根據(jù)京東運(yùn)營(yíng)報(bào)告，在系統(tǒng)搭建完成后，商品配送成本將會(huì)下降（40～50）%。

（3）配送迅捷

無(wú)人機(jī)物流系統(tǒng)擺脫了傳統(tǒng)地面運(yùn)輸?shù)木窒扌裕傻孛孢\(yùn)輸轉(zhuǎn)換為立體運(yùn)輸，對(duì)配送效率有較大提升。

（4）實(shí)用性強(qiáng)

根據(jù)京東物流報(bào)告顯示，85%的快遞商品重量在2.7kg左右，適合采用無(wú)人機(jī)進(jìn)行配送，從而有效降低運(yùn)營(yíng)成本。

2.2 無(wú)人機(jī)物流系統(tǒng)建模

無(wú)人機(jī)物流系統(tǒng)主要承擔(dān)商品在配送點(diǎn)之間的配送工作，有M個(gè)配送無(wú)人機(jī)往返于N個(gè)配送點(diǎn)之間[8?9]。

對(duì)于投遞點(diǎn)及無(wú)人機(jī)物流系統(tǒng)的選擇主要考慮以下幾點(diǎn)：（1）為簡(jiǎn)化模型，假設(shè)該系統(tǒng)只有一個(gè)集散站，并且每個(gè)配送無(wú)人機(jī)以此為每次配送路徑的起點(diǎn)和終點(diǎn)。（2）當(dāng)該系統(tǒng)內(nèi)含有N個(gè)配送點(diǎn)（包括1 個(gè)集散點(diǎn)和N－1 個(gè)配送點(diǎn)）和M個(gè)物流無(wú)人機(jī)時(shí)，要保證N＞M[10]；（3）在一次配送環(huán)節(jié)中，默認(rèn)每個(gè)配送點(diǎn)（除集散點(diǎn)之外）只會(huì)被訪問(wèn)一次[11]；（4）N個(gè)配送點(diǎn)之間的物流無(wú)人機(jī)配送航線是固定的，當(dāng)兩條航線有交點(diǎn)時(shí)，分別以不同的航線高度避免碰撞；（5）每個(gè)物流無(wú)人機(jī)的飛行速度是恒定不變的，不受搭載貨物重量的影響；（6）同時(shí)約束每個(gè)物流無(wú)人機(jī)的配送距離與所有物流無(wú)人機(jī)的配送距離的總和為最小。

這里所建立的無(wú)人機(jī)物流系統(tǒng)的空間位置，如圖1所示。模型由一個(gè)集散點(diǎn)和九個(gè)配送點(diǎn)組成，同時(shí)由五個(gè)物流無(wú)人機(jī)在各配送點(diǎn)之間進(jìn)行配送任務(wù)。

圖1 無(wú)人機(jī)物流系統(tǒng)空間位置Fig.1 Spatial Location of UAV Logistics System

約束與判斷條件的數(shù)學(xué)表達(dá)式為：

目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式為：

3 遺傳算法

遺傳算法起源于20世紀(jì)70年代，基本思想是依據(jù)達(dá)爾文生物進(jìn)化論和孟德?tīng)栠z傳學(xué)說(shuō)，通過(guò)計(jì)算機(jī)來(lái)模擬生物進(jìn)化過(guò)程中的優(yōu)勝劣汰，得出想要的最優(yōu)解[12]。其中基因?qū)?yīng)優(yōu)化求解中的變量組合，一個(gè)解或解集代表著生物種群中的某一個(gè)體。

通過(guò)種群個(gè)體之間的繁衍，對(duì)基因進(jìn)行交叉和變異來(lái)改變個(gè)體的表現(xiàn)型（目標(biāo)函數(shù)）。通過(guò)模擬自然法則中的優(yōu)勝劣汰將符合環(huán)境要求的表現(xiàn)型的個(gè)體保留，若干代之后，種群得以生存于該環(huán)境，從而得到問(wèn)題的全局最優(yōu)解。遺傳算法的一般流程，如圖2所示。

圖2 遺傳算法流程圖Fig.2 Flow Chart of Genetic Algorithm

3.1 基因型編碼

定義作為起點(diǎn)和終點(diǎn)的集散點(diǎn)的基因代碼為0，N－1個(gè)配送點(diǎn)的基因代碼依次為1，2，…，N－1，在此基礎(chǔ)上，增加M－1個(gè)虛擬集散點(diǎn)，依次編碼為N，…，N＋M－2，虛擬集散點(diǎn)的作用是m號(hào)物流無(wú)人機(jī)配送任務(wù)的結(jié)束和m＋1號(hào)物流無(wú)人機(jī)配送任務(wù)的開(kāi)始。將上述的基因代碼組成一條染色體，即是所有的物流無(wú)人機(jī)配送航線。將模型帶入上述基因型編碼規(guī)則，即可得模型的基因型編碼表，如表1所示。

表1 模型基因型編碼表Tab.1 Model Genotype Coding Table

隨機(jī)生成一條代表無(wú)人機(jī)物流系統(tǒng)的染色體，如圖3所示。

圖3 無(wú)人機(jī)物流系統(tǒng)的隨機(jī)染色體Fig.3 Stochastic Chromosomes of UAV Logistics System

從該條染色體可以得知五架物流無(wú)人機(jī)的航線為：

1號(hào)物流無(wú)人機(jī)：0—6—4—0；

2號(hào)物流無(wú)人機(jī)：0—7—9—0；

3號(hào)物流無(wú)人機(jī)：0—3—8—1—0；

4號(hào)物流無(wú)人機(jī)：0—2—0；

5號(hào)物流無(wú)人機(jī)：0—5—0。

但是在種群初始化和變異交叉的過(guò)程中，可能會(huì)出現(xiàn)以下的情況，這些情況不符合實(shí)際情況，所以需要舍棄或重新編譯染色體，因此需要在程序中引入檢測(cè)機(jī)制，避免此種情況的發(fā)生，提高算法的運(yùn)算效率。

錯(cuò)誤情況一：染色體首位或末位基因型編碼即為虛擬集散點(diǎn)基因型編碼，此種情況會(huì)使得第一架或最后一架物流無(wú)人機(jī)空飛，降低無(wú)人機(jī)物流系統(tǒng)的配送效率，如圖4所示。

圖4 錯(cuò)誤情況一染色體示意圖Fig.4 Error?1 Case?Chromosome Schematic

錯(cuò)誤情況二：染色體相鄰兩位基因型編碼同時(shí)為虛擬集散點(diǎn)基因型編碼，此種情況會(huì)使某一架物流無(wú)人機(jī)空飛，降低無(wú)人機(jī)物流系統(tǒng)的配送效率，如圖5所示。

圖5 錯(cuò)誤情況二染色體示意圖Fig.5 Error?2 Case?Chromosome Schematic

3.2 種群規(guī)模的選擇

考慮到優(yōu)化求解過(guò)程中的求解速度和避免局部自由解，一般將種群規(guī)模控制在5N左右，這樣會(huì)加速遺傳算法優(yōu)化求解的收斂速度。

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

自然界中的種群競(jìng)爭(zhēng)往往是由兩個(gè)方面組成的：種群內(nèi)部的斗爭(zhēng)與種群和環(huán)境的斗爭(zhēng)。在無(wú)人機(jī)物流系統(tǒng)的優(yōu)化求解中，不存在種群內(nèi)部斗爭(zhēng)[13?14]。因此，只需考慮種群與環(huán)境的斗爭(zhēng)即可。在本模型中，將每一條染色體通過(guò)解碼器解碼后，可直接代入第二節(jié)中的目標(biāo)函數(shù)中得到函數(shù)值，以此作為適應(yīng)性評(píng)分，即適應(yīng)度函數(shù)為目標(biāo)函數(shù)。

3.4 自然選擇

在遺傳算法中，最常用的選擇方法為輪盤賭法和排名法。

輪盤賭法是通過(guò)種群中每個(gè)個(gè)體的適應(yīng)度與種群總的適應(yīng)度的比值大小來(lái)選擇優(yōu)秀個(gè)體。比值越大，則說(shuō)明個(gè)體越能適應(yīng)環(huán)境，存活下來(lái)的可能性越高。數(shù)學(xué)表達(dá)式為：

式中：Pi—第i個(gè)個(gè)體的淘汰概率；Fi—第i個(gè)個(gè)體的適應(yīng)度函數(shù)值；∑F—種群適應(yīng)度函數(shù)值的總和。

排名法是將種群個(gè)體按照各自適應(yīng)度值的大小按照一定規(guī)則來(lái)進(jìn)行排名，排名越高，則證明在環(huán)境中適應(yīng)性越好，越容易存活。數(shù)學(xué)表達(dá)式為：

式中：Pi—第i個(gè)個(gè)體的淘汰概率；Ri—第i個(gè)個(gè)體的適應(yīng)度函數(shù)值排名；5N—種群規(guī)模。

兩種方法相比，輪盤賭法的算法設(shè)計(jì)較為復(fù)雜且速度較快，但存在使算法喪失解的多樣性和造成早熟的風(fēng)險(xiǎn)。而排名法則很好的避免這種風(fēng)險(xiǎn)，因此在這里的模型中采用排名法作為自然選擇的方法。

3.5 交叉操作

交叉是遺傳算法中極為重要的操作，可以使得后代能夠有效繼承父代的優(yōu)良特性，保證種群的穩(wěn)定性，朝著最優(yōu)解的方向進(jìn)化。傳統(tǒng)的交叉操作是在種群中隨機(jī)選擇兩個(gè)個(gè)體，然后在染色體結(jié)構(gòu)中隨機(jī)選擇一部分，兩隨機(jī)個(gè)體將該部分的基因型編碼進(jìn)行互換，產(chǎn)生新的子代個(gè)體。傳統(tǒng)交叉操作示意圖，如圖6所示。

圖6 傳統(tǒng)交叉操作示意圖Fig.6 Schematic Diagram of Traditional Crossover Operation

從圖6的操作結(jié)果可知，傳統(tǒng)的交叉操作會(huì)導(dǎo)致個(gè)體染色體內(nèi)出現(xiàn)重復(fù)的配送點(diǎn)基因型編碼，這與第二節(jié)中的（3）號(hào)假設(shè)相沖突，因此重新定義交叉規(guī)則。

在交叉過(guò)程中，引入目標(biāo)函數(shù)來(lái)作為交叉操作的約束條件，具體操作如下文所示。在初始種群中隨機(jī)選擇某一個(gè)體，然后隨機(jī)抽取另外一個(gè)個(gè)體，兩個(gè)個(gè)體的基因型編碼，如圖7所示。1號(hào)染色體所代表的無(wú)人機(jī)物流系統(tǒng)總的配送距離為163，最長(zhǎng)的單個(gè)物流無(wú)人機(jī)的配送距離為41；2號(hào)染色體所代表的無(wú)人機(jī)物流系統(tǒng)總的配送距離為177，最長(zhǎng)的單個(gè)物流無(wú)人機(jī)的配送距離為47。

圖7 隨機(jī)抽取初始種群中的兩個(gè)個(gè)體Fig.7 Random Selection of Two Individuals in Initial Population

以1號(hào)染色體的首位基因型編碼作為交叉后代個(gè)體母本，對(duì)2號(hào)染色體的首位基因型編碼進(jìn)行操作，從右到左循環(huán)移動(dòng)2號(hào)染色體中的基因型編碼，直到兩條染色體的首位基因型編碼一致。交叉結(jié)果，如圖8所示。

圖8 首位基因交叉操作示意圖Fig.8 A Schematic Map of the First Gene Crossover Operation

確定第二位基因型編碼。由圖1確定1號(hào)染色體首位基因型編碼和第二位基因型編碼之間的距離與2號(hào)染色體首位基因型編碼和第二位基因型編碼之間的距離，記為d（3，2）＝6和d（3，8）＝10，因此有d（3，8）＞d（3，2）。為了滿足單個(gè)物流無(wú)人機(jī)的配送距離最短的約束條件，交叉后代個(gè)體的第二位基因型編碼確定為2。

同理，交叉后代個(gè)體的其他位基因型編碼也利用此種交叉操作，得到一條全新的個(gè)體染色體，如圖9所示。交叉操作之后產(chǎn)生的后代個(gè)體所代表的無(wú)人機(jī)物流系統(tǒng)總的配送距離為161，最長(zhǎng)的單個(gè)物流無(wú)人機(jī)的配送距離為40?？梢钥吹?，交叉操作之后可以有效降低總的配送距離和單個(gè)物流無(wú)人機(jī)的配送距離。

圖9 交叉后代個(gè)體染色體示意圖Fig.9 Individual Chromosome Map of Cross Progeny

3.6 變異操作

變異操作的優(yōu)劣將會(huì)直接影響最終解與全局最優(yōu)解之間的差距，可以有效增加種群的多元性，避免交叉操作可能產(chǎn)生的局部最優(yōu)解。

基因突變是染色體上某一位基因型編碼的改變。變異操作會(huì)使得該條染色體變成它的等位染色體，會(huì)引起染色體的表現(xiàn)型改變。這里所采用的變異規(guī)則為隨機(jī)選擇某一位配送點(diǎn)基因型編碼，然后在該染色體內(nèi)再隨機(jī)抽取某一位配送點(diǎn)基因型編碼，兩者互換位置，形成子代，變異操作示意圖，如圖10所示。

圖10 變異操作示意圖Fig.10 Sketch of Mutation Operation

3.7 染色體的解碼

染色體的基因型編碼組合代表著優(yōu)化問(wèn)題的解，但在求解的過(guò)程中，染色體不能直接參與計(jì)算，需要進(jìn)行解碼。在此模型中，解碼矩陣dco為配送點(diǎn)之間的距離矩陣，其中(idco，jdco)元素的含義為配送點(diǎn)idco與配送點(diǎn)jdco之間的配送距離。

以圖3中隨機(jī)生成的染色體為例，進(jìn)行解碼計(jì)算。第一步獲得染色體中第一架物流無(wú)人機(jī)航線距離矩陣D1，其中(iD，jD)元素為1的含義為系統(tǒng)內(nèi)某一物流無(wú)人機(jī)的配送路徑為iD點(diǎn)到j(luò)D點(diǎn)，該染色體的的航線距離矩陣D1，如圖11所示。

圖11 隨機(jī)染色體可達(dá)距離矩陣D1Fig.11 Rando m Chromosome Reachable Distance Matrix D1

同理可得其余四架物流無(wú)人機(jī)的航線距離矩陣D2、D3、D4和D5，最后可得到該條染色體總的航線距離矩陣D。

第二步將航線距離矩陣依次與解碼矩陣元素相乘，求解矩陣的元素和，得出各物流無(wú)人機(jī)的配送距離和總的配送距離，并依此計(jì)算適應(yīng)度函數(shù)的值。

4 程序設(shè)計(jì)與優(yōu)化結(jié)果

通過(guò)第三節(jié)遺傳算法設(shè)計(jì)，得到無(wú)人機(jī)物流系統(tǒng)模型的某些參數(shù)值，如表2所示。

表2 遺傳算法中的參數(shù)值Tab.2 Parameter Values in Genetic Algorithms

圖12和圖13表明，在500次迭代過(guò)程中，這里所設(shè)計(jì)的遺傳算法優(yōu)化后的結(jié)果為無(wú)人機(jī)物流系統(tǒng)配送距離總和為121，單個(gè)物流無(wú)人機(jī)最大配送距離為42。表3 表明，與傳統(tǒng)遺傳算法相比，這里所采用的算法，從無(wú)人機(jī)物流系統(tǒng)配送距離和單個(gè)物流無(wú)人機(jī)最大配送距離來(lái)看，得出的結(jié)果更加高效，更加符合實(shí)際情況。

圖12 無(wú)人機(jī)物流系統(tǒng)配送距離總和Fig.12 Total Distribution Distance of UAV Logistics System

表3 傳統(tǒng)優(yōu)化算法與這里優(yōu)化算法的對(duì)比Tab.3 Comparisons between the Traditional Optimization Algorithm and the Optimization Algorithm in this Paper

算法程序編寫(xiě)過(guò)程略結(jié)果，如圖13所示。

圖13 單個(gè)物流無(wú)人機(jī)最大配送距離Fig.13 Maximum Distribution Distance of Single Logistics UAV

5 結(jié)論

針對(duì)現(xiàn)代物流系統(tǒng)的特點(diǎn)，引入遺傳算法對(duì)多個(gè)物流無(wú)人機(jī)在多配送目標(biāo)之間的配送航線進(jìn)行優(yōu)化，尋求最優(yōu)路徑。

通過(guò)對(duì)傳統(tǒng)遺傳算法的修改，采用單個(gè)物流無(wú)人機(jī)的航線距離和無(wú)人機(jī)物流系統(tǒng)航線距離的總和作為約束條件，將問(wèn)題轉(zhuǎn)換為多目標(biāo)優(yōu)化，使得優(yōu)化后的航線距離更短。考慮到實(shí)際配送目標(biāo)的情況，引入檢測(cè)程序，對(duì)不符合的實(shí)際情況的方案進(jìn)行重新編譯或舍棄，得到更多的優(yōu)良后代個(gè)體。

仿真結(jié)果表明：利用遺傳算法對(duì)無(wú)人機(jī)物流系統(tǒng)航線進(jìn)行多目標(biāo)優(yōu)化能夠?qū)φ麄€(gè)系統(tǒng)的航線距離和單個(gè)物流無(wú)人機(jī)的航線距離進(jìn)行縮短。從而提高了無(wú)人機(jī)物流系統(tǒng)的配送效率和物流無(wú)人機(jī)的利用效率，為現(xiàn)代無(wú)人機(jī)物流行業(yè)發(fā)展提供了保障和支持。