基于人工免疫算法和模擬退火TSP的城市物流空中配送模式優(yōu)化研究

陳建鋒　郭子龍　白林柱　汪承杰　郭旻昊　趙偉

摘 要：本文針對城市區(qū)域內(nèi)物流配送系統(tǒng)，研究了基于人工免疫算法和模擬退火TSP的方法的優(yōu)化配送模式。以城市建成區(qū)為例，利用初選的34個空中載運(yùn)地面基站，確定各備選基站負(fù)責(zé)范圍內(nèi)人口數(shù)量，結(jié)合具有GPS定位遠(yuǎn)程控制功能的空中載運(yùn)工具，建立了11個空中載運(yùn)地面站點(diǎn)，以所選站點(diǎn)為基礎(chǔ)，結(jié)合模擬退火TSP規(guī)劃方法確定配送中心空中載運(yùn)工具飛行路徑，可達(dá)到中心空中載運(yùn)工具與各站點(diǎn)空中載運(yùn)工具系統(tǒng)性結(jié)合配送的目的。根據(jù)模式的需求，建立了空中載運(yùn)工具遠(yuǎn)程控制系統(tǒng)和站點(diǎn)交叉協(xié)調(diào)系統(tǒng)，可實(shí)現(xiàn)物流配送時間最短、多點(diǎn)同時、提高配送效率的目標(biāo)。

關(guān)鍵詞：空中載運(yùn)；物流配送；免疫算法；模擬退火TSP

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1003-5168（2018）05-0015-04

Optimization of Urban Logistics Air Distribution Model Based on

Artificial Immune Algorithm and Simulated Annealing TSP

CHEN Jianfeng GUO Zilong BAI Linzhu WANG Chengjie GUO Minhao ZHAO Wei

（College of Electrical and Mechanical Engineering， Henan University of Science and Technology，Luoyang Henan 471003）

Abstract： Aiming at the logistics distribution system in urban area， this paper studies the optimized distribution mode based on artificial immune algorithm and simulated annealing TSP method.Taking the urban built-up area as an example， using the first selected 34 air carrier ground base stations to determine the population number of the selected base stations in charge of the range， and combined with the air carrying tools with GPS positioning remote control function， 11 air carrying ground stations are established， based on the selected sites and combined with the simulated annealing TSP planning method. The flight path of the aerial vehicle of the distribution center can achieve the purpose of the systematic combination of the central air transport tools and the air transportation tools of the stations.According to the demand of the model， the remote control system of the air carrier and the cross coordination system of the site are set up， which can realize the shortest and multi point at the same time and improve the efficiency of distribution.

Keywords： air borne vehicle；urban logistics distribution；immune algorithm；simulated annealing TSP

1 研究背景

當(dāng)前，我國大部分城市區(qū)域內(nèi)物流配送模式采用共同配送和區(qū)域配送等多種方式，以車輛為主要運(yùn)輸工具，不僅對城市交通的管理有較大影響，而且在高峰時間段，受地面交通影響較大。隨著城市交通管理的加強(qiáng)，對小型配送車輛管制也越來越嚴(yán)格。而現(xiàn)有的城市物流配送模式采用分級、分點(diǎn)配送，針對性不強(qiáng)，配送效率較低，時效性較差，不能較好地滿足客戶要求。

城市物流空中配送是一個較新的行業(yè)，是隨著零售業(yè)和電子商務(wù)發(fā)展及人們購物習(xí)慣的改變而產(chǎn)生的現(xiàn)代服務(wù)業(yè)，是眾多消費(fèi)品流通供應(yīng)鏈和工業(yè)品銷售供應(yīng)鏈的重要組成部分。但由于缺乏系統(tǒng)性，國內(nèi)在此領(lǐng)域研究較少，現(xiàn)有的同類研究主要利用單一的免疫算法或模擬退火算法來解決物流配送問題，計算誤差較大。本文結(jié)合這兩種算法提出基于空中載運(yùn)工具的城市物流配送模式，精確物流配送站點(diǎn)，致力于打造立體化城市物流配送體系，充分利用空中資源進(jìn)行物流配送，從而提升物流配送效率。

2 基于人工免疫算法優(yōu)化飛行器站點(diǎn)

2.1 問題描述

在新型城市配送模式下，對空中載運(yùn)地面站點(diǎn)的選址模型做出如下假設(shè)：①每個站點(diǎn)的總規(guī)模量由其服務(wù)范圍內(nèi)的需求量確定，并能滿足需求點(diǎn)需求；②任何一個需求點(diǎn)的需求僅由其對應(yīng)站點(diǎn)供應(yīng)；③選定空中載運(yùn)地面站點(diǎn)后，站點(diǎn)所覆蓋區(qū)域內(nèi)的需求點(diǎn)由該站點(diǎn)內(nèi)單獨(dú)的空中載運(yùn)工具配送；④各個需求點(diǎn)的需求量與人數(shù)成正比；⑤備選站點(diǎn)已知，在備選方案中尋優(yōu)。

基于上述假設(shè)，建立如下模型，在滿足飛行距離上限的條件下，需要從[n]個需求點(diǎn)中找出空中載運(yùn)地面站點(diǎn)，并向各需求點(diǎn)配送物品。利用重心法確定站點(diǎn)的最佳位置點(diǎn)，目標(biāo)函數(shù)是各需求點(diǎn)的需求量與空中載運(yùn)地面站點(diǎn)到需求點(diǎn)的距離值的乘積之和的最小值[1-3]：

[ minF=i∈Nj∈Mi?idijZij] （1）

約束條件為：

[j∈MinZij=1]，[i∈N] （2）

[Zij≤hj]，[i∈N]，[j∈Mi] （3）

[j∈Minhj=p] （4）

[Zij，hj∈0，1，][i∈N，][j∈Mi] （5）

其中，[ N={1，2，…，n}]是所有需求點(diǎn)的序號集合；[Mi]為到需求點(diǎn)[i]的距離小于[s]的備選配送中心集合，[i∈n，Mi?N，][wi]表示需求點(diǎn)的需求量，[dij]表示從需求點(diǎn)[i]到離其最近的配送中心[j]的距離；[Zij]為0～1的變量，當(dāng)其為1時，表示需求點(diǎn)[j]被選為配送中心；[s]為新建配送中心離由其服務(wù)的需求點(diǎn)的距離上限。

2.2 基于人工免疫算法優(yōu)化地面站點(diǎn)

2.2.1 算法流程。①抗原識別。目標(biāo)函數(shù)和約束條件即為抗原。②產(chǎn)生初始抗體群。隨機(jī)產(chǎn)生[n]個個體并從記憶庫中提取[m]個個體構(gòu)成初始群體，其中[m]為記憶庫中個體的數(shù)量。③抗體評價。在本算法中，對個體的評價是以個體的期望繁殖率[P]為標(biāo)準(zhǔn)的。④形成父代群體。將初始群體按期望繁殖率[P]進(jìn)行降序排列，并取前[n]個個體構(gòu)成夫代群體，同時取前[m]個個體存入記憶庫中。⑤判斷是否滿足結(jié)束條件，是則結(jié)束；反之，則繼續(xù)下一步操作。⑥新群體的產(chǎn)生?；诓襟E④的計算結(jié)果對抗體群體進(jìn)行選擇、交叉、變異操作得到新群體，再從記憶庫中取出記憶的個體，共同構(gòu)成新一代群體[3]。

2.2.2 親和力計算

2.2.2.1 抗體與抗原間親和力?？贵w與抗原之間的親和力用于表示抗體對抗原的識別程度，筆者針對上述空中載運(yùn)地面站點(diǎn)模型設(shè)計親和力函數(shù)：

[Av=1Fv=1i∈Nj∈Mi?idijZij-Ci∈Nminj∈MinZij-1，0] （6）

其中，[Fv]為目標(biāo)函數(shù)；分母中第二項表示對違反距離約束的解給予懲罰，[C]取一個比較大的正數(shù)。

2.2.2.2 抗體濃度。抗體的濃度[Cv]即群體中相似抗體所占的比例：

[Cv=1Nj∈NSv，s] （7）

其中，[N]為抗體總數(shù)，[Sv，s=1，Sv，s>T0，其他]；[T]為預(yù)先設(shè)定的一個閾值。

2.2.2.3 期望繁殖概率。在群體中，每個個體的期望繁殖概率由抗體和抗原間親和力[Av]和抗體濃度[Cv]兩部分共同決定。個體適應(yīng)度越高，則期望繁殖概率越大；個體濃度越大，則期望繁殖概率越小。這樣既鼓勵了適應(yīng)度高的個體，同時抑制了濃度高的個體，從而確保了個體多樣性。

人工免疫算法具有魯棒性好、并行搜索能力強(qiáng)等優(yōu)點(diǎn)，十分適合于求解本文中地面站點(diǎn)選擇問題，但存在易陷入局部最優(yōu)、早熟等不足。為此，本文將引入模擬退火算法對需求站點(diǎn)進(jìn)行路徑優(yōu)化[4-6]。

2.3 基于模擬退火優(yōu)化的飛行器路徑研究

①初始化、初始解，設(shè)置控制參數(shù)初始溫度[T0]、結(jié)束溫度[Tend]、降溫速率[q]。

②新解的生成，通過對當(dāng)前解[S1]進(jìn)行變換，產(chǎn)生新的路徑數(shù)組，即新解。

③若路徑長度函數(shù)為[fS]，則當(dāng)前解的路徑為[f（S1）]，新解的路徑為[f（S2）]，路徑差為[df=fS2-fS1]，則Metropolis準(zhǔn)則為[7]：

[P=1，df<0exp（-dfT），df≥0] （8）

如果[df<0]，則以概率1接受新的路徑；否則以概率[exp-df/T]接受新的路徑。

④降溫，利用降溫速率[q]進(jìn)行降溫：

[Tn+1=qTn] （9）

若[T模擬退火算法在變量較多的情況下，存在迭代次數(shù)過多、求解時間過長和運(yùn)算速度過慢等問題。通過人工免疫算法對需求點(diǎn)進(jìn)行選擇確定地面配送站點(diǎn)，減少了目標(biāo)變量的數(shù)目。模擬退火算法在此基礎(chǔ)上，對站點(diǎn)進(jìn)行路徑規(guī)劃，減少迭代次數(shù)，縮短運(yùn)算時間，提高效率。

3 城市配送模式下空中載運(yùn)地面站點(diǎn)選擇及路徑規(guī)劃

3.1 地面配送站點(diǎn)選定

以某城市建成區(qū)為例（見圖1），設(shè)定34個備選基站。人工免疫算法具體參數(shù)設(shè)定如下：選取種群規(guī)模為50，變異概率取0.4，交叉概率取0.5，迭代次數(shù)取200。

從圖2可知，對基站1、2、4、7、10、13、15、21、23、27和29分別設(shè)立一個站點(diǎn)，這11個站點(diǎn)分別負(fù)責(zé)其覆蓋區(qū)域的物流配送，尋優(yōu)進(jìn)化過程如圖3所示，實(shí)現(xiàn)代表最優(yōu)適應(yīng)度，點(diǎn)劃線代表平均適應(yīng)度。由圖3可以看出，進(jìn)化到50代時，最優(yōu)適應(yīng)度不再變化，人工免疫算法能快速收斂到最優(yōu)解，能有效解決配送中心選址優(yōu)化問題。

3.2 地面配送站點(diǎn)路徑規(guī)劃

在進(jìn)行站點(diǎn)之間物流配送路徑的優(yōu)化時，給定任意需求站點(diǎn)即能找到空中載運(yùn)工具飛行的最短路徑，假設(shè)34個基站均有物流配送需求，配送中心的空中載運(yùn)工具需要從站點(diǎn)23出發(fā)走過每個站點(diǎn)然后回到站點(diǎn)23。以此為例規(guī)劃空中載運(yùn)工具路徑，如圖4所示。

由圖4可以看出最短路徑為23→15→13→10→7→4→2→1→29→27→21→23。當(dāng)基站有需求時，由中心站點(diǎn)空中載運(yùn)工具配送綜合物資，只需在中心站點(diǎn)網(wǎng)絡(luò)平臺上輸入需求站點(diǎn)坐標(biāo)即可得到中心空中載運(yùn)工具的最短路徑。利用互聯(lián)網(wǎng)技術(shù)和空中載運(yùn)工具，結(jié)合得到的最短路徑，實(shí)現(xiàn)空中短距離物流配送。

4 結(jié)語

本文對空中載運(yùn)工具的物流配送模式進(jìn)行了研究，是針對當(dāng)前城市內(nèi)部物流配送遇到的問題提出的一種新型的模式。其優(yōu)點(diǎn)是時效性強(qiáng)、效率高；利用空中運(yùn)輸優(yōu)勢，能提升整體的配送效率，并在一定程度上緩解城市交通壓力，減小現(xiàn)有小型配送車輛的不規(guī)范使用度。同時，論文所提出的新的物流配送模式的推廣與應(yīng)用將打破現(xiàn)有模式的發(fā)展障礙，從而打造立體化城市物流配送體系。該配送模式是對城市物流未來發(fā)展的構(gòu)想，由于政策和技術(shù)的限制，目前難以實(shí)現(xiàn)應(yīng)用及推廣。這就需要政府的政策支持、行業(yè)協(xié)會技術(shù)的突破和企業(yè)的大力支持，才能創(chuàng)建良好的發(fā)展環(huán)境，實(shí)現(xiàn)互惠互利，達(dá)到“共贏”的目的 。

參考文獻(xiàn)：

[1]陳亞東，許傳偉，周祥華.電力物資配送中心選址優(yōu)化研究[J].技術(shù)與方法，2015（6）：188-190.

[2]李雪竹.基于免疫螢火蟲算法的RFID倉儲車輛動態(tài)調(diào)度[J].計算機(jī)工程與運(yùn)用，2014（6）：235-239.

[3]周梅芳，葉洪濤.基于免疫算法的物流配送中心選址[J].廣西工學(xué)院學(xué)報，2012（3）：77-80.

[4]楊成順.多旋翼飛行器建模與飛行控制技術(shù)研究[D].南京：南京航空航天大學(xué)，2013.

[5]駱博，張舒瑜.基于模糊PID控制傾轉(zhuǎn)旋翼飛行器載重分析[J].工業(yè)設(shè)計，2015（11）：164-187.

[6]王旭坪，阮俊虎，張凱，等.有模糊時間窗的車輛調(diào)度組合干擾管理研究[J].管理科學(xué)學(xué)報，2012（6）：2-15.

[7]田昀，梁海龍.基于模擬退火算法的物流配送路徑優(yōu)化問題分析[J].交通科技與經(jīng)濟(jì)，2013，15（5）：85-88.