鄭譽煌， 卜國富， 聶永怡

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

0 引言

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

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

1 模型分析

1.1 倉庫布局模型

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

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

設M個移動機器人把N處提取點的貨物全部搬運，第j個移動機器人所走過的路徑長度是Lj，則所需平均耗時是

圖1 參考布局

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

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

1.2 所需移動機器人數(shù)量分析

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

目標：

約束：

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

1.3 CVRP 模型

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

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

目標：

約束：

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

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

2.1 遺傳算法求解

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

隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時在計算上用枚舉法很難求出最優(yōu)解. 對這類復雜的問題，人們已經(jīng)意識到應把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一. 實踐證明，遺傳算法對于組合優(yōu)化中的NP 問題非常有效. 本文解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)任務的貨物提取點參數(shù). 第一層基于遺傳算法獲得本次工作任務所需要的最少移動機器人數(shù)M0. 第二層在基于遺傳算法獲得本次工作任務的M0 個移動機器人的最優(yōu)移動路徑. 由于遺傳算法的特點，或許會出現(xiàn)某個移動機器人所需要移動路徑為0 的情況，即不需要M0 個移動機器人即可完成本次工作任務. 分層優(yōu)化調(diào)度算法最后輸出的是完成本次工作任務的實際需要移動機器人數(shù)和這些機器人的運行路徑.

2.3 實驗驗證

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

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

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

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

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

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

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

圖7 實際負荷與移動機器人容量之比

表2 實際負荷與移動機器人容量之比的實驗結果表

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

3 結語

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