基于改進人工蜂群與Floyd算法的多機器人運輸路徑規劃

盧天翼

（武漢理工大學機電工程學院，湖北 武漢 430070）

2020年新冠病毒席卷全球，各地物流遲緩，物資處于緊缺狀態，抗疫進度受到較大阻礙。鑒于新冠病毒的傳染性，現采用防疫機器人進行物資配送。通過選擇正確的路徑規劃，能夠有效提高運輸效率，從而實現物資的轉移。

1 算法概述

Floyd算法是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，其目標是尋找從節點i到節點j的最短路徑。而有文獻介紹了Floyd算法在O2O配送路線優化方面的應用。

人工蜂群（ABC）算法是一種源于蜂群采蜜行為的群智能的全局優化算法。蜜蜂根據各自的分工進行不同的活動，并實現蜂群信息的共享和交流，從而找到最好的蜜源，即問題的最優解。文獻[1]采用規則引導的搜索策略及錦標賽選擇策略方法分別探討了人工蜂群算法應用于航空發動機路徑規劃中的三大問題。

2 融合算法

本文通過改進人工蜂群算法對點序進行隨機排列與迭代優化[2]，結合Floyd算法對路徑數據進行高效處理，提高全局搜索性能和收斂速度，為多機器人運輸規劃出用時最短的最優路徑。

2.1 機器人模型假設

考慮到配送的生活物資的多樣性，運輸機器人應具有較大的承載能力W（W≤45 kg）和存儲空間S（S≤0.2 m3）。同時，機器人應裝備GPS定位系統實現配送過程中的精準定位。此外，內部設置紅外、壓力、溫度等傳感器以實現避障功能，外部裝載圖像記錄儀用來反饋運輸過程的清晰畫面，確保運輸安全。

設定負責配送的機器人數量為Q（Q∈N*），運輸前指定起點，規定Q個機器人同時出發，遍歷目標點后返回指定起點。運輸過程中無物資損耗與機械損壞，無不確定因素干擾。

在運輸過程中，各機器人的運輸速度ve（0＜ve≤5 m/s）一定，不考慮因轉彎、停留和卸貨導致的時間延遲。全程單向行進，中途不折返，設定歷經其所有目標點的所需時間為te。

單次行進的限定：機器人每一次的行進方向規定為從當前目標點指向其周圍的存在直接路徑的下一目標點，每一次的行進路徑長度為存在直接路徑的兩個目標點之間的距離。若當前目標點與預行進點之間不存在直接路徑，則無法行進。

2.2 環境模型假設

Floyd算法所需的地圖M中無交通信號燈、無典型障礙阻礙行進。需要配送的目標點數量為G（G∈N*）。根據配送目標的數量，對G作出以下劃分：數量較少，1≤G≤25；數量較多，26≤G≤50；數量很多，G≥51（G∈N*）。此外，包含目標點（節點）和拐點（地圖上的折點）在內的全部節點集為V{vk，k∈N*}。

2.3 融合算法全局優化

獲取地圖M，確定M中目標點（節點）數量G（G∈N*）與所有節點集（含拐點）V{vx，1≤x≤U}以及負責配送的機器人數量Q（Q≤G，∈N*）。

初始化Floyd算法的距離矩陣Ds與路由矩陣Ps，通過Floyd算法計算地圖M中的任意兩個節點vi與vj（1≤i，j≤U，i≠j）之間的最短距離lij和中間結點vk（k≠j），遍歷各點，最終形成所有節點集V的距離矩陣Dv（U×U）和路由矩陣Pv（U×U）。

初始化控制ABC算法的參數，主要包括種群參數與問題變量。其中，種群參數包括種群數量NP、蜜源數量FoodNumber=NP/2、最大搜索次數lmt、最大迭代次數maCycle、概率因子prob（0≤prob≤1），問題變量包括最大運載量mavolume、參數維數D、種群f（NP，D+Q）、適應度值objval（NP，1）和蜜源Foods（FoodNumber，D+Q）。

隨機生成初始種群，并結合距離矩陣Dv計算每個個體的適應度值。排序擇優，挑選出最優的一批個體形成蜜源Foods。

通過人工蜂群算法，不斷迭代，優化個體。若v1為起點，vG為終點，則最后得到每個機器人配送的最優路徑，形如〈v1，v2，…，vG〉。

3 改進ABC算法的搜索過程

3.1 “靠近”策略

已知種群f（NP，D+Q）的個體長度為D+Q。對于第i個個體f（i，:），它的目標點序列為αi（1≤i≤D，∈N*），機器人序列為β（1≤β≤Q，∈N*）。那么，當第i個個體f（i，:）中的第β個運輸機器人的特征值為f（i，D+β）時，它的目標點序f（i，αm:αn）則滿足下式：

式（1）表明了機器人β的特征值決定了它的目標點數量。個體中機器人總數量為Q，則都應滿足式（1）。

基于種群個體組成的特點，現提出一種改進的搜索蜜源的方法：將蜜源的搜索過程定義為個體“靠近”的過程，該“靠近”策略是指待優化個體分別通過向隨機蜜源的前段和后段的“靠近”處理，并以此增加蜜源的相似度。

對于“靠近”過程，有以下限定：①隨機選擇的蜜源不可與需要“靠近”處理的個體相同。②個體向前段“靠近”。隨機選擇的目標點不能為每個運輸機器人配送的首位目標點，也不能為隨機選擇的蜜源中的任一機器人的首位目標點。③個體向后段“靠近”。隨機選擇的目標點不能為每個運輸機器人配送的末位目標點，也不能為隨機選擇的蜜源中任一機器人的末位目標點。

3.2 優化點序

在分別實現向前、后段“靠近”的基礎上，將第i個個體f（i，:）中所有運輸機器人的特征值f（i，D+β）（1≤β≤Q）進行排序。從排序結果里篩選出最長路徑點序對應的第βmax個機器人及其點序和，最短路徑點序對應的第βm i n個機器人及其點序

然后，對個體中最長路徑點序的機器人的目標點數進行“縮減”操作，即確定最長路徑的點序末位目標點將其移至最短路徑點序的目標點列末位，其后點序依次遞推。同時第βmax個機器人的特征值變為f（i，D+βmax）－1，第βmin個機器人的特征值變為f（i，D+βmin）+1，繼而形成新的點序排列。

4 實例驗證與分析

以G=48的某小區地圖為例，目標點與拐點總數為U（U=89）。經過多組實驗（每組實驗運行50次），最優值為953.7的概率最大。5個機器人運輸的點序和路徑如圖1所示。

圖1 機器人路徑圖

5 結束語

針對Floyd算法無法擬定無向圖的點序以及傳統人工蜂群算法易陷入尋優過程中的局部極值，導致收斂速度慢等問題，提出了一種結合改進人工蜂群和Floyd算法的多機器人的運輸路徑規劃的融合算法。并且基于小區配送的路徑規劃實例，證明了該算法具備高效性與可行性，動態優化路徑的效果顯著，全局搜索能力強，能較好地滿足路徑規劃的理想要求。