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

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

摘 要：本文針對城市區域內物流配送系統，研究了基于人工免疫算法和模擬退火TSP的方法的優化配送模式。以城市建成區為例，利用初選的34個空中載運地面基站，確定各備選基站負責范圍內人口數量，結合具有GPS定位遠程控制功能的空中載運工具，建立了11個空中載運地面站點，以所選站點為基礎，結合模擬退火TSP規劃方法確定配送中心空中載運工具飛行路徑，可達到中心空中載運工具與各站點空中載運工具系統性結合配送的目的。根據模式的需求，建立了空中載運工具遠程控制系統和站點交叉協調系統，可實現物流配送時間最短、多點同時、提高配送效率的目標。

關鍵詞：空中載運；物流配送；免疫算法；模擬退火TSP

中圖分類號：TP18 文獻標識碼：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 研究背景

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

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

2 基于人工免疫算法優化飛行器站點

2.1 問題描述

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

基于上述假設，建立如下模型，在滿足飛行距離上限的條件下，需要從[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}]是所有需求點的序號集合；[Mi]為到需求點[i]的距離小于[s]的備選配送中心集合，[i∈n，Mi?N，][wi]表示需求點的需求量，[dij]表示從需求點[i]到離其最近的配送中心[j]的距離；[Zij]為0～1的變量，當其為1時，表示需求點[j]被選為配送中心；[s]為新建配送中心離由其服務的需求點的距離上限。

2.2 基于人工免疫算法優化地面站點

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

2.2.2 親和力計算

2.2.2.1 抗體與抗原間親和力。抗體與抗原之間的親和力用于表示抗體對抗原的識別程度，筆者針對上述空中載運地面站點模型設計親和力函數：

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

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

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

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

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

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

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

2.3 基于模擬退火優化的飛行器路徑研究

①初始化、初始解，設置控制參數初始溫度[T0]、結束溫度[Tend]、降溫速率[q]。

②新解的生成，通過對當前解[S1]進行變換，產生新的路徑數組，即新解。

③若路徑長度函數為[fS]，則當前解的路徑為[f（S1）]，新解的路徑為[f（S2）]，路徑差為[df=fS2-fS1]，則Metropolis準則為[7]：

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

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

④降溫，利用降溫速率[q]進行降溫：

[Tn+1=qTn] （9）

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

3 城市配送模式下空中載運地面站點選擇及路徑規劃

3.1 地面配送站點選定

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

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

3.2 地面配送站點路徑規劃

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

由圖4可以看出最短路徑為23→15→13→10→7→4→2→1→29→27→21→23。當基站有需求時，由中心站點空中載運工具配送綜合物資，只需在中心站點網絡平臺上輸入需求站點坐標即可得到中心空中載運工具的最短路徑。利用互聯網技術和空中載運工具，結合得到的最短路徑，實現空中短距離物流配送。

4 結語

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

參考文獻：

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

[2]李雪竹.基于免疫螢火蟲算法的RFID倉儲車輛動態調度[J].計算機工程與運用，2014（6）：235-239.

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

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

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

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

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