基于改進(jìn)人工蜂群與Floyd算法的多機(jī)器人運(yùn)輸路徑規(guī)劃

盧天翼

（武漢理工大學(xué)機(jī)電工程學(xué)院，湖北 武漢 430070）

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

1 算法概述

Floyd算法是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，其目標(biāo)是尋找從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑。而有文獻(xiàn)介紹了Floyd算法在O2O配送路線優(yōu)化方面的應(yīng)用。

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

2 融合算法

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

2.1 機(jī)器人模型假設(shè)

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

設(shè)定負(fù)責(zé)配送的機(jī)器人數(shù)量為Q（Q∈N*），運(yùn)輸前指定起點(diǎn)，規(guī)定Q個機(jī)器人同時出發(fā)，遍歷目標(biāo)點(diǎn)后返回指定起點(diǎn)。運(yùn)輸過程中無物資損耗與機(jī)械損壞，無不確定因素干擾。

在運(yùn)輸過程中，各機(jī)器人的運(yùn)輸速度ve（0＜ve≤5 m/s）一定，不考慮因轉(zhuǎn)彎、停留和卸貨導(dǎo)致的時間延遲。全程單向行進(jìn)，中途不折返，設(shè)定歷經(jīng)其所有目標(biāo)點(diǎn)的所需時間為te。

單次行進(jìn)的限定：機(jī)器人每一次的行進(jìn)方向規(guī)定為從當(dāng)前目標(biāo)點(diǎn)指向其周圍的存在直接路徑的下一目標(biāo)點(diǎn)，每一次的行進(jìn)路徑長度為存在直接路徑的兩個目標(biāo)點(diǎn)之間的距離。若當(dāng)前目標(biāo)點(diǎn)與預(yù)行進(jìn)點(diǎn)之間不存在直接路徑，則無法行進(jìn)。

2.2 環(huán)境模型假設(shè)

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

2.3 融合算法全局優(yōu)化

獲取地圖M，確定M中目標(biāo)點(diǎn)（節(jié)點(diǎn)）數(shù)量G（G∈N*）與所有節(jié)點(diǎn)集（含拐點(diǎn)）V{vx，1≤x≤U}以及負(fù)責(zé)配送的機(jī)器人數(shù)量Q（Q≤G，∈N*）。

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

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

隨機(jī)生成初始種群，并結(jié)合距離矩陣Dv計(jì)算每個個體的適應(yīng)度值。排序擇優(yōu)，挑選出最優(yōu)的一批個體形成蜜源Foods。

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

3 改進(jìn)ABC算法的搜索過程

3.1 “靠近”策略

已知種群f（NP，D+Q）的個體長度為D+Q。對于第i個個體f（i，:），它的目標(biāo)點(diǎn)序列為αi（1≤i≤D，∈N*），機(jī)器人序列為β（1≤β≤Q，∈N*）。那么，當(dāng)?shù)趇個個體f（i，:）中的第β個運(yùn)輸機(jī)器人的特征值為f（i，D+β）時，它的目標(biāo)點(diǎn)序f（i，αm:αn）則滿足下式：

式（1）表明了機(jī)器人β的特征值決定了它的目標(biāo)點(diǎn)數(shù)量。個體中機(jī)器人總數(shù)量為Q，則都應(yīng)滿足式（1）。

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

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

3.2 優(yōu)化點(diǎn)序

在分別實(shí)現(xiàn)向前、后段“靠近”的基礎(chǔ)上，將第i個個體f（i，:）中所有運(yùn)輸機(jī)器人的特征值f（i，D+β）（1≤β≤Q）進(jìn)行排序。從排序結(jié)果里篩選出最長路徑點(diǎn)序?qū)?yīng)的第βmax個機(jī)器人及其點(diǎn)序和，最短路徑點(diǎn)序?qū)?yīng)的第βm i n個機(jī)器人及其點(diǎn)序

然后，對個體中最長路徑點(diǎn)序的機(jī)器人的目標(biāo)點(diǎn)數(shù)進(jìn)行“縮減”操作，即確定最長路徑的點(diǎn)序末位目標(biāo)點(diǎn)將其移至最短路徑點(diǎn)序的目標(biāo)點(diǎn)列末位，其后點(diǎn)序依次遞推。同時第βmax個機(jī)器人的特征值變?yōu)閒（i，D+βmax）－1，第βmin個機(jī)器人的特征值變?yōu)閒（i，D+βmin）+1，繼而形成新的點(diǎn)序排列。

4 實(shí)例驗(yàn)證與分析

以G=48的某小區(qū)地圖為例，目標(biāo)點(diǎn)與拐點(diǎn)總數(shù)為U（U=89）。經(jīng)過多組實(shí)驗(yàn)（每組實(shí)驗(yàn)運(yùn)行50次），最優(yōu)值為953.7的概率最大。5個機(jī)器人運(yùn)輸?shù)狞c(diǎn)序和路徑如圖1所示。

圖1 機(jī)器人路徑圖

5 結(jié)束語

針對Floyd算法無法擬定無向圖的點(diǎn)序以及傳統(tǒng)人工蜂群算法易陷入尋優(yōu)過程中的局部極值，導(dǎo)致收斂速度慢等問題，提出了一種結(jié)合改進(jìn)人工蜂群和Floyd算法的多機(jī)器人的運(yùn)輸路徑規(guī)劃的融合算法。并且基于小區(qū)配送的路徑規(guī)劃實(shí)例，證明了該算法具備高效性與可行性，動態(tài)優(yōu)化路徑的效果顯著，全局搜索能力強(qiáng)，能較好地滿足路徑規(guī)劃的理想要求。