基于混合優化算法的RGV動態調度策略方案

陳恩宏　劉陳帥　賈學勇

摘 要：本文以智能物料加工系統中軌道式自動引導車（RGV）的最優動態調度問題為研究背景，建立了基于動態規劃—粒子群耦合算法的單工序調度模型，并結合自適應遺傳算法得出多道工序的動態調度方案，通過軟件仿真驗證了模型的合理性和有效性 。對于一道工序的RGV動態調度問題，建立動態規劃—粒子群算法模型。首先選取8小時內RGV移動的總距離最短作為目標函數，根據RGV同一時間只能完成一個任務，數控機床（CNC）在某一時間只能加工一個物料以及RGV執行任務的順序等原則確定約束條件。然后利用動態規劃算法以時間軸為劃分原則，將整個調度過程轉化為若干個子過程，各子過程之間狀態函數相互關聯，最后結合粒子群算法尋找各子過程的最優軌跡即可得出基于RGV移動總距離最短的單目標優化的動態調度策略。為了解決兩道工序的RGV動態調度問題，本文首先建立自適應遺傳模型，對多目標函數進行優化，并提出額外作業效率和修正系數的概念對模型進行完善；然后增加模型的約束條件來達到明確兩道工序時間上的先后性的目的；采用自適應理論對目標函數的權重進行確定，來達到減少遺傳算法迭代次數的目的；最后根據遺傳算法的尋優過程來得出RGV具體的行走軌跡，進而得到效率較高的動態調度策略。

關鍵詞：動態調度 動態規劃—粒子群 自學習遺傳算法

模擬仿真

1. 引言

簡易的智能加工系統由數控機床（CNC）、軌道式自動引導車（RGV）、引導車直線軌道等其他附屬設備組成，其中RGV是一種自動沿用軌道的自動運行，在軌道兩側傳送帶用于上料、下料，RGV可通過移動到數控機床（CNC）旁，使用引導車自身帶有的機械手臂、兩只機械手爪和物料清洗槽，完成上、下料和物料清洗。

物料的加工作業大致可分為兩種情況，一是由一臺CNC就可以完成，二是由兩臺CNC完成，且兩臺機器的刀具不同。

2.基于兩道工序的RGV動態調度模型

RGV對CNC上料需求的選擇若僅僅依靠就近原則，可能會造成多臺CNC的空閑和RGV長時間停止等待任務的情況，這種簡單的調度方式效率低，因此，基于兩道工序加工物料的RGV需考慮多個目標函數。

2.1模型的準備

將GRV作業過程中任意時刻的狀態進行量化，以便后續約束條件和目標函數的建立。根據表格中GRV系統作業參數，得出物料加工的第一、二道工序基本相等，所以將8個CNC平均分為兩部分，1#、3#、5#、7#可完成物料加工的第一道工序，中，；表示第個物料在任一個CNC上開始加工的時刻，表示第個物料開始加工第二道工序的時刻，。

其中，約束條件（7）表示一個物料的第一道工序完成總成第二道之前，目標函數（8）表示RGV在工作時間8小時內執行次指令時移動總路程的最小值；系統作業效率，目標函數（12）表示RGV作業過程的最短總路徑和最大作業效率。

2.2自學習遺傳算法模型的建立

自學習遺傳算法避免傳統遺傳算法局部搜索的不敏感，可解決多個目標函數的優化問題，算法中引入遺傳算子和妥協解自學習，提高了遺傳算法的局部收斂速度。

1.編碼、變異和交叉遺傳

遺傳染色體的編碼方式采用二進制編碼方法，對一輛RGV工作狀態和作業進度進行編碼，組成染色體，具體編碼為：；

直線往復式RGV進行作業時，實時自主變化的是作業任務點，隨之變化的是RGV的移動路線，在遺傳變異中，采用多點交叉法，交叉位置為RGV小車等待狀態=0，交叉點數服從泊松分布：

（14）

2.自適應交叉、變異概率

等研究人員提出改變算法遺傳變異中交叉概率和變異概率都不變的條件，提出遺傳適應度自動進行改變和優化，其中交叉概率，變異概率計算公式為：

其中，為種群最大、最小交叉概率；為種群最大、最小變異概率； 為種群的最大適應值；為每代種群的平均適應值；為兩個個體中較大的適應度值。

減少時，種群中個體的適應度高于平均適應值，較小時，進行遺傳變異時，將被保留下來，否則將被淘汰。

3.自適應函數

由于軌道往復式小車的在不同時間的作業情況可能出現重復，引入知識專家種群模塊，當出現相同的路徑選擇時直接調用庫中之前生成的種群收斂性最優解，不僅提高迭代效率，在隨機種群的不斷生成中，更新知識專家庫。妥協方法是通過不斷訓練，隨著子代數的不斷增加，染色體發生遺傳和變異趨向穩定，最終得出與實際中與理想條件最接近的最優解。

總 結

動態規劃—粒子群算法在優化實現上迭代計算比遺傳算法容易，并且在優化的結果上相較于動態規劃計算結果精度顯著提高，該結合算法不易陷入局部最優，保證了全局優化結果的有效性，試用于大量難以全面研究的領域，例如航空航天領域、大型水庫蓄水量管理等等，可其中的部分粒子劃分為若干個階段，以局部粒子的最優取向得出全局的發展趨勢。

本文中定義的RGV的作業時間是除原地等待以外所有的有效時間，在確保全局路徑在一定值的情況下，還需要借助效率目標函數進行最優趨向引導，自適應遺傳算法可同時設立多個目標函數，求解各個目標函數在執行決策中的權重，能夠準確的得出RGV動態調度策略。并且CNC出現故障對于RGV路徑和作業時間的影響不同，通過公式得出理論修正系數也不同，多個目標函數與其不同的修正系數匹配得到實際RGV調度策略和系統作業效率。

參考文獻

[1] 江唯，何非，童一飛，李東波. 基于混合算法的環形軌道RGV系統調度優化研究[J]. 計算機工程與應用，2016，52（22）：242-247.

[2] 王曉寧. 直線往復式軌道穿梭車避讓策略仿真研究[D].北京郵電大學，2012.

[3] 吳孟達. 數學建模教程[M]. 高等教育出版社， 2011.

[4] 唐猛. 自動小車存取系統建模及調度優化研究[D].武漢大學，2015.

[5] 聶峰. 自動化立體倉庫穿梭車系統控制方法與優化調度研究[D].太原理工大學，2009.