基于現代優化算法對RGV動態調度問題的研究

王晨旭 漆映彤 盛瑋桐

摘 要：研究軌道式自動引導車（RGV）的動態調度問題對自動化倉庫領域以及物流系統具有重要的意義。本文重點考慮了兩道工序的物料加工作業情況，基于現代優化算法建立了動態調度模型，給出了最優的調度方案。針對兩道工序的物料加工作業情況，本文以基于現代優化算法中的遺傳算法對其進行求解，并且在編碼過程中摒棄了常用的一維編碼，進行了二重結構編碼，接著再結合數據進行了模型實用性和算法有效性的檢驗，得到此種情況下三組數據產出的成品個數分別為159，161，165，系統作業效率較高，結論為該模型較為合理。

關鍵詞：遺傳算法;RGV;動態調度

引言

智能加工系統是通過充分利用各種機械，運輸設備，計算機系統和綜合作業協調等技術手段，更精準，高效的完成加工物流的相關作業和內容。軌道自動導引車RGV擁有價格低廉，靈活和方便的特點，它能方便地與各種數控機床，機器人等加工設備實現連接，進行作業，提高工作效率，因此被廣泛應用于智能加工系統。在智能加工系統的運輸系統中，軌道式自動引導車RGV的效率是瓶頸，因此RGV的動態調度是關鍵。

1. 模型準備

RGV是一種無人駕駛、能在固定軌道上自由運行的智能車。它根據指令能自動控制移動方向和距離，并自帶一個機械手臂、兩只機械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業任務。圖1為一個示意圖，它表示一個智能加工系統，且這個加工系統由8臺計算機數控機床、1輛軌道式自動引導車、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設備組成。

根據經驗，無論是幾臺CNC的協同運作，對其進行調度的核心是用時最短，也就是效率最高，還可以理解為走的路徑最短。因此此種情況便可以理解成存在一些約束條件的情況下，將一款產品從一個地方運輸到另一個地方，而目標函數則可以看成所有的運送過程中最晚完成運送的時間。然后再用遺傳算法對此問題就行求解，最后將數據帶進模型進行檢驗，并求得此時的最優調度策略以及系統的作業效率。

2 .RGV動態調度模型建立及求解

遺傳算法解決的關鍵步驟便是編碼，編碼不僅決定了個體基因的排列方式，決定了GA搜索的復雜程度和困難程度，也決定了最終求解的精度。

本文只考慮含有一個RGV小車的情況，由于兩道工序中的協作任務是成對出現的，常規的一維編碼（二進制編碼）便難以解決此問題，因此在這里可以使用二重編碼。如下所示：

即可以將1和3號CNC進行搭配，2和4號CNC進行搭配，6和7號CNC進行搭配，5和8號CNC進行搭配。

Step1：產生初始化的種群。

群體的初始化值一般隨機生成，初始值最好可以在解空間中均勻采樣;而對于非二進制的編碼程序還必須要思考所產生的染色體是否在可行域內。

Step2：個體的目標函數和適應度值的計算：目標函數為運送完一組出入貨任務所用的總時間。

Step3：選擇、交叉、變異。

首先選擇要用的算子以及選擇操作。常用的個體選擇概率的方法有按比例的適應度分配以及基于排序的適應度分配。

按比例的適應度分配也可稱為蒙特卡洛算法，它通過利用各個個體適應度的概率決定它后代遺留的可能性。若某個體為p，它的適應度為fp ，那么被選中的幾率為：

顯然，若個體的選擇概率較大，則能夠被更多次的選中，而它的遺傳因子也將不斷在種群中擴大。

但是在基于排序的適應度分配中，適應度僅僅取決于一個個體在一個種群中的地位，并非實際目標值。

其次，進行交叉操作。對于常用的二進制編碼，我們可以使用均勻交叉，單點交叉以及多點交叉等方法。

最后，進行變異操作。常用的變異操作有二進制變異法、實值變異法。

對于上述模型本文采用matlab遺傳算法工具箱進行計算。再將相關數據代入模型進行檢驗，得到三組數據下分別產出的成品個數為159，161，165。得出結論為該模型實用性較強，算法較為有效。

結論：

與傳統的優化算法不一樣，本文的算法是基于現代優化算法而來的，這種啟發式算法可以大大節省運算的時間，并且可以將模型進行簡化，相比于一般的規劃類問題較為簡便。遺傳算法因其具有良好的全局搜索能力，可以快速地將將空間中的全體解搜索出，不會陷入局部出現死循環，且其使用概率機制進行迭代，具有隨機性，結論更加客觀可靠。

參考文獻：

[1]張劍秋.基于馬爾科夫排隊模型的流水車間調度問題研究[D].蘭州理工大學，2017.

[2]司守奎，張兆亮.數學建模算法與應用[M].北京：國防工業出版社，2017.

[3]余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應用[J].計算機工程與應用，2006（03）：86-89.