鄭譽(yù)煌， 卜國(guó)富， 聶永怡

（1.廣東第二師范學(xué)院 教務(wù)處， 廣東 廣州510303；2.廣東第二師范學(xué)院 物理與信息工程系， 廣東 廣州510303）

0 引言

隨著我國(guó)老齡化問(wèn)題日益凸顯，人口紅利逐漸消失，生產(chǎn)方式逐步向智能化轉(zhuǎn)變. 在電子商務(wù)和物流業(yè)空前發(fā)展的今天，倉(cāng)庫(kù)自動(dòng)化是實(shí)現(xiàn)高效物流的關(guān)鍵. 在工業(yè)自動(dòng)化系統(tǒng)中，移動(dòng)機(jī)器人主要用于對(duì)工件或產(chǎn)品進(jìn)行搬運(yùn)、裝卸等操作. 在生產(chǎn)過(guò)程中，工業(yè)物料不斷處于運(yùn)輸、加工、組裝、裝卸、存儲(chǔ)等狀態(tài). 物料流通不暢，會(huì)影響企業(yè)的生產(chǎn)效率，嚴(yán)重的會(huì)導(dǎo)致生產(chǎn)的暫停. 引入移動(dòng)機(jī)器人，解決了當(dāng)前勞動(dòng)力不足的問(wèn)題，高效和準(zhǔn)確完成物料的運(yùn)輸和裝卸任務(wù). 實(shí)際生產(chǎn)場(chǎng)景中，往往需要多臺(tái)移動(dòng)機(jī)器人同時(shí)協(xié)助解決一項(xiàng)任務(wù)，機(jī)器人的調(diào)度系統(tǒng)需要優(yōu)化每個(gè)移動(dòng)機(jī)器人的行走路徑，避免路徑重復(fù)，提高移動(dòng)機(jī)器人的運(yùn)行效率. 當(dāng)前倉(cāng)儲(chǔ)物流面臨著產(chǎn)品批次和貨物種類(lèi)多樣化的挑戰(zhàn)，傳統(tǒng)的移動(dòng)機(jī)器人調(diào)度方法已經(jīng)難以應(yīng)對(duì)這些挑戰(zhàn). 當(dāng)多個(gè)貨物的提貨單同時(shí)到達(dá)時(shí)，如何在減少移動(dòng)機(jī)器人數(shù)量的條件下，盡快把這些貨物提取并搬運(yùn)到目標(biāo)地點(diǎn)是關(guān)鍵問(wèn)題［1］.當(dāng)前的研究主要是采用容量約束的車(chē)輛路徑優(yōu)化模型問(wèn)題（Capacitated Vehicle Routing Problem ，縮寫(xiě)CVRP）處理［2－3］，而且這些算法的移動(dòng)機(jī)器人數(shù)量是一個(gè)常數(shù)，導(dǎo)致在實(shí)際應(yīng)用中受到很大的限制.

為了解決這個(gè)問(wèn)題，本文提出了多移動(dòng)機(jī)器人的分層優(yōu)化調(diào)度算法（Genetic Algorithm－MobileRobot－CVRP，縮寫(xiě)GA－M－CVRP），本算法分為兩個(gè)層次，第一層是基于0－1 規(guī)劃模型，分析了每個(gè)生產(chǎn)任務(wù)所需要的移動(dòng)機(jī)器人數(shù)量； 第二層是基于CVRP 模型，獲得每個(gè)移動(dòng)機(jī)器人的最優(yōu)運(yùn)行路徑. 每層算法的求解都基于遺傳算法. 仿真實(shí)驗(yàn)結(jié)果表明：對(duì)于智能倉(cāng)庫(kù)中的多機(jī)器人調(diào)度和任務(wù)分配問(wèn)題，GA－M－CVRP 算法優(yōu)于現(xiàn)有的算法.

1 模型分析

1.1 倉(cāng)庫(kù)布局模型

不同的倉(cāng)庫(kù)有不同的布局形式，本文采用了文［2－3］的網(wǎng)格n×n式布局，如圖1 所示.

假設(shè)圓形區(qū)域是移動(dòng)機(jī)器人工作起點(diǎn)和提取貨物后交付地點(diǎn)，在矩形區(qū)域中是移動(dòng)機(jī)器人的貨物提取點(diǎn).當(dāng)機(jī)器人被分配任務(wù)時(shí)，移動(dòng)機(jī)器人從圓形區(qū)域出發(fā)，沿著規(guī)劃路徑按順序到矩形區(qū)域提取貨物，最后返回圓形區(qū)域，記圓形區(qū)域是配送中心.在移動(dòng)機(jī)器人取貨和返回的這工作過(guò)程，假設(shè)：1）某一空間內(nèi)有N處貨物提取點(diǎn)，每個(gè)提取點(diǎn)的貨物已經(jīng)打包成標(biāo)準(zhǔn)的包裝箱，每個(gè)提取點(diǎn)的貨物量可以用包裝箱的個(gè)數(shù)描述，每個(gè)提取點(diǎn)的貨物量不完全相同.移動(dòng)機(jī)器人從搬運(yùn)這些貨物開(kāi)始，直至把全部貨物搬運(yùn)到配送中心為止，稱(chēng)為一個(gè)工作任務(wù).在一個(gè)工作任務(wù)內(nèi)，每個(gè)提取點(diǎn)的貨物不會(huì)增加.2）移動(dòng)機(jī)器人每到貨物提取點(diǎn)，必須把這個(gè)提取點(diǎn)的貨物全部一次取走，不能分多次提取.3）不考慮包裝箱與移動(dòng)機(jī)器人車(chē)艙內(nèi)其他包裝箱的碰撞和滾動(dòng)情形，設(shè)某一個(gè)貨物提取點(diǎn)i的貨物量是Si，車(chē)艙的最大容納貨物量是S0.4）在不同批次的工作任務(wù)中，每個(gè)提取點(diǎn)的貨物量是不同的.5）多移動(dòng)機(jī)器人之間沒(méi)有發(fā)生碰撞和沒(méi)有發(fā)生相互道路阻塞，不存在未能完成提貨任務(wù)的移動(dòng)機(jī)器人.6）移動(dòng)機(jī)器人運(yùn)行速度v、提取一個(gè)包裝箱時(shí)間t1和卸貨一個(gè)包裝箱時(shí)間t2是恒定值.

設(shè)M個(gè)移動(dòng)機(jī)器人把N處提取點(diǎn)的貨物全部搬運(yùn)，第j個(gè)移動(dòng)機(jī)器人所走過(guò)的路徑長(zhǎng)度是Lj，則所需平均耗時(shí)是

圖1 參考布局

在同一批生產(chǎn)任務(wù)中，N、Si、t1、t2是不變的，移動(dòng)機(jī)器人搬運(yùn)所需耗時(shí)的可控變量是其所走過(guò)的移動(dòng)機(jī)器人所走過(guò)的路徑總長(zhǎng)，這也是移動(dòng)機(jī)器人在最短時(shí)間內(nèi)完成一次工作任務(wù)的關(guān)鍵.

移動(dòng)機(jī)器人貨物搬運(yùn)關(guān)鍵要解決兩個(gè)問(wèn)題，一是在給定一個(gè)生產(chǎn)任務(wù)后，完成此任務(wù)的移動(dòng)機(jī)器人數(shù)量最小化； 二是對(duì)多移動(dòng)機(jī)器人的路徑進(jìn)行優(yōu)化，以達(dá)到最小運(yùn)行距離.

1.2 所需移動(dòng)機(jī)器人數(shù)量分析

移動(dòng)機(jī)器人數(shù)量M的求解屬于典型的一維裝箱問(wèn)題，可以建立如下0－1 規(guī)劃模型：

目標(biāo)：

約束：

式（2）為0－1 規(guī)劃模型總求解目標(biāo)，即每次工作任務(wù)所需要的移動(dòng)機(jī)器人數(shù)量M最少； 式（3）表示每次搬運(yùn)的提取點(diǎn)貨物量總和不超過(guò)移動(dòng)機(jī)器人的車(chē)艙容量； 式（4）限定了每個(gè)提取點(diǎn)的貨物只能被搬運(yùn)一次.式（5）中yi＝1 表示移動(dòng)機(jī)器人第i次搬運(yùn)時(shí)車(chē)艙有裝入貨物，反之表示移動(dòng)機(jī)器人第i次搬運(yùn)車(chē)艙是空載.式（6）中xij＝1 表示移動(dòng)機(jī)器人第i次搬運(yùn)時(shí)提取點(diǎn)j的貨物裝入車(chē)艙，反之表示提取點(diǎn)j的貨物未裝入車(chē)艙.

1.3 CVRP 模型

CVRP 可以描述為：以車(chē)輛總行駛距離最小為目的，在載運(yùn)貨物不超過(guò)其載重上限的前提下，合理調(diào)度車(chē)輛服務(wù)對(duì)象與運(yùn)輸路徑［4］.

根據(jù)CVRP 的問(wèn)題描述和上述模型假設(shè)，建立移動(dòng)機(jī)器人搬運(yùn)過(guò)程描述：一個(gè)移動(dòng)機(jī)器人從配送中心空載出發(fā)搬運(yùn)N個(gè)貨物提取點(diǎn)，某一個(gè)貨物提取點(diǎn)i的貨物量是Si，移動(dòng)機(jī)器人車(chē)艙的最大容納貨物量S0，而且滿足移動(dòng)機(jī)器人每到貨物提取點(diǎn)，必須把這個(gè)提取點(diǎn)的貨物全部一次取走，不能分多次提??； 每個(gè)貨物提取點(diǎn)的坐標(biāo)位置已知，則其相對(duì)距離可表示為di，j，每個(gè)貨物提取點(diǎn)到配送中心的距離為d0，j； 由于車(chē)艙的限制，移動(dòng)機(jī)器人不能一次搬運(yùn)全部的貨物，一旦車(chē)艙滿載后，要回到配送中心卸貨.移動(dòng)機(jī)器人至少要搬運(yùn)M次，設(shè)nk為第k次運(yùn)送的貨物數(shù)，集合Rk表示第k條路徑，而元素rki中的i表示貨物提取點(diǎn)rki在路徑k中的順序，配送中心為rk0＝0.從而建立如下的移動(dòng)機(jī)器人搬運(yùn)過(guò)程的多目標(biāo)CVRP 數(shù)學(xué)模型.

目標(biāo)：

約束：

式（7）為CVRP 問(wèn)題的總求解目標(biāo)，即移動(dòng)機(jī)器人總行走路徑最短； 式（8）表示每條路徑上的提取點(diǎn)貨物量總和不超過(guò)移動(dòng)機(jī)器人的車(chē)艙容量； 式（9）表示每個(gè)提取點(diǎn)貨物都要被搬運(yùn)到配送中心； 式（10）表示每條路徑的提取點(diǎn)貨物組成； 式（11）限制提取點(diǎn)貨物只能由移動(dòng)機(jī)器人搬運(yùn)一次； 式（12）表示如果移動(dòng)機(jī)器人第k次出發(fā)搬運(yùn)提取點(diǎn)貨物，則sign（nk）＝1，反之沒(méi)有出發(fā).

2 基于遺傳算法的模型求解

2.1 遺傳算法求解

根據(jù)上述分析，多移動(dòng)機(jī)器人分層調(diào)度主要解決兩個(gè)問(wèn)題，一是最少移動(dòng)機(jī)器人數(shù)，二是多移動(dòng)機(jī)器人中的最短總行駛距離.這兩個(gè)問(wèn)題對(duì)應(yīng)數(shù)學(xué)模型分別是0－1 規(guī)劃模型和CVRP 模型. 0－1 規(guī)劃模型和CVRP 模型都是NP 難題，高效的精確算法存在的可能性不大，主要研究是探索智能算法解決，最常見(jiàn)的智能算法包括模擬退火算法（Simulated Annealing）、禁忌搜索算法（Tabu Search）、遺傳算法（Genetic Algorithm）、蟻群算法（Ant Colony） 和神經(jīng)網(wǎng)絡(luò)（Neutral Networks）方法等［4］.

隨著問(wèn)題規(guī)模的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇增大，有時(shí)在計(jì)算上用枚舉法很難求出最優(yōu)解. 對(duì)這類(lèi)復(fù)雜的問(wèn)題，人們已經(jīng)意識(shí)到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一. 實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP 問(wèn)題非常有效. 本文解0－1規(guī)劃模型和CVRP 模型所采用相同參數(shù)的遺傳算法，其求解流程圖［5］如圖2 所示.

圖2 遺傳算法求解流程圖

圖3 分層優(yōu)化調(diào)度算法

2.2 分層優(yōu)化調(diào)度算法

本文所采用的分層優(yōu)化調(diào)度算法（GA－M－CVRP）如圖3所示，首先初始化遺傳算法的參數(shù)和本次生產(chǎn)任務(wù)的貨物提取點(diǎn)參數(shù). 第一層基于遺傳算法獲得本次工作任務(wù)所需要的最少移動(dòng)機(jī)器人數(shù)M0. 第二層在基于遺傳算法獲得本次工作任務(wù)的M0 個(gè)移動(dòng)機(jī)器人的最優(yōu)移動(dòng)路徑. 由于遺傳算法的特點(diǎn)，或許會(huì)出現(xiàn)某個(gè)移動(dòng)機(jī)器人所需要移動(dòng)路徑為0 的情況，即不需要M0 個(gè)移動(dòng)機(jī)器人即可完成本次工作任務(wù). 分層優(yōu)化調(diào)度算法最后輸出的是完成本次工作任務(wù)的實(shí)際需要移動(dòng)機(jī)器人數(shù)和這些機(jī)器人的運(yùn)行路徑.

2.3 實(shí)驗(yàn)驗(yàn)證

由于0－1 規(guī)劃模型和CVRP 模型都是NP 難題，遺傳算法的每次求解不一定能獲得最優(yōu)解. 最優(yōu)解即為保證每臺(tái)移動(dòng)機(jī)器人不超載的情況下，保證全體移動(dòng)機(jī)器人的走過(guò)總路徑最短. 在遺傳算法參數(shù)是本算法中，設(shè)置最大迭代次數(shù)為Max ＝1 000，種群大小pop ＝40，交叉概率p＝0.4，變異概率q＝0.8，S0＝100，Si在（10，20）上均勻分布，即Si～U（10，20）.在每種布局的條件完成1 000 次隨機(jī)的工作任務(wù)，獲得結(jié)果如圖4 所示. 實(shí)驗(yàn)結(jié)果可見(jiàn)，GA－M－CVRP 算法比文［3］提出的GA－CVRP 算法效果要好得多.隨著布局規(guī)模的增加，兩種算法的非最優(yōu)率有所提高，但是GA－M－CVRP 在7×7 提取點(diǎn)布局以?xún)?nèi)的非最優(yōu)率接近為0%，到了10×10 布局非最優(yōu)率超過(guò)10%，而GA－CVRP 所得的非最優(yōu)率幾乎與布局規(guī)模的增大成正比. 采用GA－M－CVRP 算法后的平均減少行駛距離如表1 所示，在不同的布局下，本算法比GACVRP 獲得的平均行駛距離有不同程度的減少，特別是隨著提貨點(diǎn)數(shù)量的增大，算法平均減少行駛距離越多，可見(jiàn)本算法是有效的.

圖4 不同放置點(diǎn)布局的非最優(yōu)率對(duì)比

表1 不同布局的行駛距離分析

針對(duì)10×10 布局，修改遺傳算法參數(shù)中的最大迭代次數(shù)分別為Max ＝1 000、1 500、2 000 和修改種群大小分別為pop ＝40、60、80 下，每個(gè)參數(shù)組合分別完成1 000 次隨機(jī)的工作任務(wù)，所得的非最優(yōu)率結(jié)果如圖5所示. 可見(jiàn)在最大迭代次數(shù)Max ＝1 500 和種群大小pop ＝80 時(shí)，非最優(yōu)率只有0.03 左右. 可以推斷，對(duì)于小于10×10 的布局，非最優(yōu)率會(huì)更小. 值得注意的是，10×10 布局在不同（Max， pop）組合下本算法獲得的所需最少移動(dòng)機(jī)器人數(shù)有一定差異，如圖6 所示. 在Max ＝1 500 和pop ＝60 時(shí)，大部分情況下16 臺(tái)移動(dòng)機(jī)器人足夠滿足完成工作任務(wù). 之所以出現(xiàn)15 臺(tái)或17 臺(tái)移動(dòng)機(jī)器人的情況，是因?yàn)楦鱾€(gè)貨物提取點(diǎn)在10 ～20 個(gè)標(biāo)準(zhǔn)箱子隨機(jī)生成，最大需要機(jī)器人數(shù)20 臺(tái)，最少10 臺(tái).

圖5 10×10 布局時(shí)不同（Max， pop）組合下的非最優(yōu)率

圖6 10×10 布局在不同（Max，pop）組合下每1 000 次實(shí)驗(yàn)所獲最少移動(dòng)機(jī)器人數(shù)直方圖

圖7 是針對(duì)10×10 布局在1 000 次工作任務(wù)實(shí)驗(yàn)中，每次工作任務(wù)的實(shí)際提取貨物量與本次所需要的移動(dòng)機(jī)器人容量總和之比的直方圖. 不同的遺傳算法組合參數(shù)的實(shí)驗(yàn)結(jié)果如表2 所示，這個(gè)比值的均值在0.94左右，比值最小值超過(guò)0.85，最大超過(guò)0.98，說(shuō)明本算法獲得在遺傳算法參數(shù)組合（1 500， 60）上基本達(dá)到較好的效果，保證了移動(dòng)機(jī)器人負(fù)荷能在一定冗余的情況下滿足所需要的提貨量，但不至于出現(xiàn)倉(cāng)位過(guò)度冗余的情況. 圖8 顯示了10×10 布局時(shí)不同（Max， pop）組合下的平均行駛距離分析，可見(jiàn)不同的組合會(huì)影響平均行駛距離的大小，一般Max 和pop 越大，平均行駛距離越小，但Max 和pop 的取值到了一定值后，平均行駛距離的減少量會(huì)不明顯.

圖7 實(shí)際負(fù)荷與移動(dòng)機(jī)器人容量之比

表2 實(shí)際負(fù)荷與移動(dòng)機(jī)器人容量之比的實(shí)驗(yàn)結(jié)果表

圖8 10×10 布局時(shí)不同（Max，pop）組合下的平均行駛距離分析

3 結(jié)語(yǔ)

本文分析了多移動(dòng)機(jī)器人在網(wǎng)格式布局倉(cāng)庫(kù)中搬運(yùn)貨物的特征，分析了多移動(dòng)機(jī)器人在最短時(shí)間內(nèi)完成一次搬運(yùn)工作任務(wù)的關(guān)鍵問(wèn)題，并提出了多移動(dòng)機(jī)器人的分層優(yōu)化調(diào)度算法GA－M－CVRP 解決這個(gè)問(wèn)題. 本算法首先基于0－1 規(guī)劃模型，分析了每個(gè)生產(chǎn)場(chǎng)景所需要的移動(dòng)機(jī)器人數(shù)量，其次基于CVRP 模型獲得每個(gè)移動(dòng)機(jī)器人的最優(yōu)運(yùn)行路徑，0－1 規(guī)劃模型和CVRP 模型的求解均采用遺傳算法以獲得最優(yōu)解. 仿真實(shí)驗(yàn)證明：本算法能較好實(shí)現(xiàn)多移動(dòng)機(jī)器人在最快能完成各個(gè)提前點(diǎn)貨物搬運(yùn)，算法效果優(yōu)于GA－CVRP 求解，并且保證每臺(tái)移動(dòng)機(jī)器人的倉(cāng)位有一定合理的冗余，保證機(jī)器人不會(huì)過(guò)載運(yùn)行，提高貨物搬運(yùn)的效率.本文尚未考慮移動(dòng)機(jī)器人電池容量、載重、各個(gè)提取點(diǎn)貨物在機(jī)器人搬運(yùn)期間隨機(jī)變化的情形，后續(xù)工作可以考慮將這些因素加入調(diào)度算法中進(jìn)一步的分析.