佟 剛，陳子超，王 鋒，周國慶

（1.沈陽航空航天大學，遼寧 沈陽 110136；2.沈陽航空航天大學通用航空重點實驗室，遼寧 沈陽 110136）

1 引言

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

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

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

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

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

2.1 無人機物流系統(tǒng)

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

（1）配送距離短

物流無人機不會受到地形及地面交通的影響，升空后可直接點對點直線配送，大大節(jié)省配送時間。

（2）運營成本低廉

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

（3）配送迅捷

無人機物流系統(tǒng)擺脫了傳統(tǒng)地面運輸?shù)木窒扌?，由地面運輸轉(zhuǎn)換為立體運輸，對配送效率有較大提升。

（4）實用性強

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

2.2 無人機物流系統(tǒng)建模

無人機物流系統(tǒng)主要承擔商品在配送點之間的配送工作，有M個配送無人機往返于N個配送點之間[8?9]。

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

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

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

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

目標函數(shù)的數(shù)學表達式為：

3 遺傳算法

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

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

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

3.1 基因型編碼

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

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

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

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

從該條染色體可以得知五架物流無人機的航線為：

1號物流無人機：0—6—4—0；

2號物流無人機：0—7—9—0；

3號物流無人機：0—3—8—1—0；

4號物流無人機：0—2—0；

5號物流無人機：0—5—0。

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

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

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

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

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

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

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

3.3 適應度函數(shù)

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

3.4 自然選擇

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

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

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

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

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

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

3.5 交叉操作

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

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

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

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

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

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

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

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

同理，交叉后代個體的其他位基因型編碼也利用此種交叉操作，得到一條全新的個體染色體，如圖9所示。交叉操作之后產(chǎn)生的后代個體所代表的無人機物流系統(tǒng)總的配送距離為161，最長的單個物流無人機的配送距離為40?？梢钥吹剑徊娌僮髦罂梢杂行Ы档涂偟呐渌途嚯x和單個物流無人機的配送距離。

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

3.6 變異操作

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

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

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

3.7 染色體的解碼

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

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

圖11 隨機染色體可達距離矩陣D1Fig.11 Rando m Chromosome Reachable Distance Matrix D1

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

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

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

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

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

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

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

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

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

圖13 單個物流無人機最大配送距離Fig.13 Maximum Distribution Distance of Single Logistics UAV

5 結(jié)論

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

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

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