付澤鵬， 張幗英

（1.沈陽建筑大學(xué)， 遼寧沈陽 110170； 2.內(nèi)蒙古北方重工集團(tuán)， 內(nèi)蒙古包頭 014033）

0 引言

隨著預(yù)混料工業(yè)的發(fā)展，企業(yè)對預(yù)混料生產(chǎn)效率的要求也越來越高。為了提高預(yù)混料生產(chǎn)線的生產(chǎn)效率，以配料車日生產(chǎn)量為基本目標(biāo)，建立了配料系統(tǒng)的數(shù)學(xué)模型，提出了配料車路徑優(yōu)化的具體方案， 通過改進(jìn)遺傳算法尋優(yōu)計算[1]，得到了配料車最佳路徑并確定了配料系統(tǒng)的優(yōu)化方案。在預(yù)混料的配料控制系統(tǒng)[2]中，配料車是有承上啟下作用的系統(tǒng)核心，它工作效率的高低直接影響整個配料系統(tǒng)的生產(chǎn)效率乃至整個預(yù)混料生產(chǎn)線的性能[3]。本文通過改進(jìn)遺傳算法對配料車的路徑進(jìn)行優(yōu)化，以保證最大工作效率。

1 問題描述與建模

1.1 問題描述

國內(nèi)的預(yù)混料生產(chǎn)企業(yè)，大多是雙配料車配料系統(tǒng)，但均未對配料車路徑進(jìn)行規(guī)劃， 采用按料倉順序依次接料，配料車相遇時，停止等待，或采用兩車輪流作業(yè)等方式，使得一個配料周期達(dá)到10min 以上，生產(chǎn)效率低。 在這種情況下，通過算法優(yōu)化配料車的配料路徑，在避免兩車發(fā)生碰撞的同時，縮短配料周期，具有重要的意義。

本文根據(jù)實際配料系統(tǒng)的情況歸納了兩種優(yōu)化方案，在此基礎(chǔ)上進(jìn)行建模、仿真、比較，最終得出最優(yōu)的優(yōu)化方案。 兩種方案如下：

方案一：同步啟動。兩輛配料車每次配料時同步啟動，相遇時，兩車均可進(jìn)行避讓等待，先完成配料的配料車，等待另一輛完成配料后，再同時出發(fā)，進(jìn)行下一次配料。

方案二：異步啟動。 兩輛配料車在任意時刻啟動，后開始的配料車對正在工作的配料車進(jìn)行避讓等待， 每次都是后啟動的配料車對正在工作的配料車避讓等待，兩車按此規(guī)則配料。

1.2 建模

配料車根據(jù)配方完成接料，卸料過程的時間，是一個配料周期，本文把每日完成的周期數(shù)作為日生產(chǎn)量。 為了避免不相關(guān)因素干擾，本文將一些條件做如下假設(shè)：

配方是配料車要到達(dá)的工位（接料點、卸料點），位置已知；硩車和工位看作一個點，1、2 號配料車間距小于2個工位時視為碰撞；

在工位的停留時間即接料、卸料時間，與物料重量、成分相關(guān)；

配料車速度分三個檔，即快速、勻速和慢速。 距離目標(biāo)工位超過10m，采用快速檔行駛，距離小于1m 時，采用慢速檔，其他采用勻速檔。

1.2.1 方案一

兩輛配料車最大周期的最小值是最小配料周期Tm，生產(chǎn)量Ck最大，所以目標(biāo)函數(shù)為：

其中，T1和T2是1、2 號車的配料周期；Td—工作時間。

對于路徑優(yōu)化的配料周期可以描述為， 配料車按配方走完所有工位的行走時間及工位的停留時間， 加上避讓和等待時間。 若k 值代表1、2 號配料車，有n 個接料工位和始末兩個卸料工位的配方路徑集合記為：

1.2.2 方案二

兩輛配料車的配料周期Tk都最小，得到總生產(chǎn)量Ck最大，故目標(biāo)函數(shù)為：

配料車行走時間tij，約束條件同公式（5）、式（7）。

由于2 號車的配料路徑已確定，1 號車每次向下一個工位行走時都進(jìn)行判斷。 根據(jù)產(chǎn)生等待避讓時間的情況得到1 號配料車在i 工位的等待和避讓時間為

2 改進(jìn)遺傳算法

配料車路徑優(yōu)化問題屬于復(fù)雜路徑優(yōu)化問題， 遺傳算法具有獨特的算法形式和運(yùn)行機(jī)理[4]，在復(fù)雜路徑優(yōu)化問題的求解中有著明顯的優(yōu)勢[5]，有效解決了其解空間不連續(xù)、解領(lǐng)域表達(dá)困難等問題，故在本文中用遺傳算法來求解路徑優(yōu)化的模型。

傳統(tǒng)遺傳算法執(zhí)行效率通常不高，且容易出現(xiàn)過早收斂的問題。 提高配料系統(tǒng)效率必須提高執(zhí)行效率和計算結(jié)果的準(zhǔn)確性，盡量避免過早收斂的問題。傳統(tǒng)遺傳算法的結(jié)構(gòu)是以交叉操作為基礎(chǔ)進(jìn)行的變異操作， 認(rèn)為交叉作用更大，而變異只是一個生物學(xué)背景機(jī)制。對于交叉變異的具體操作，交叉采用均勻交叉、單點交叉、多點交叉等，變異采用Guassian 分布[6-7]或Cauchy 分布[8]的隨機(jī)變異。 后經(jīng)Rudolph 的理論分析[9]，Chellailla 進(jìn)一步把二者結(jié)合起來[10]，但改進(jìn)效果并不明顯。 根據(jù)《混沌學(xué)導(dǎo)論》[11]將生物進(jìn)化看成是系統(tǒng)內(nèi)部隨機(jī)性加上反饋的特點，根據(jù)以上特點本文對基于求解路徑規(guī)劃的遺傳算法進(jìn)行改進(jìn)[12]，既確保算法收斂精度，又避免算法早熟。

本文從算法結(jié)構(gòu)到具體的遺傳操作都進(jìn)行了改進(jìn)，具體改進(jìn)方式如下：

（1）算法結(jié)構(gòu)。本文將遺傳算法中的變異、交叉分開操作，使得遺傳算法可以通過并行計算來提高實現(xiàn)的效率。

（2）交叉操作。交叉操作按父代個體的適應(yīng)度函數(shù)值或者目標(biāo)函數(shù)值大小，進(jìn)行“大對大、小對小”原則配對。然后由混沌序列確定交叉點的位置，進(jìn)行交叉操作。這種單點交叉對原解改動很小， 可以減少遺傳算法在組合優(yōu)化應(yīng)用中產(chǎn)生的尋優(yōu)抖振問題，提高算法收斂精度。

（3）變異操作。 變異操作由幾個隨機(jī)整數(shù)確定變異的基因位置，利用混沌序列得到數(shù)值作為新的基因值，進(jìn)而得到變異后的染色體。這樣采用較大強(qiáng)度的多個基因變異正好解決了單一的單點交叉很容易使算法早熟的問題。

算法的流程如圖1 所示。

圖1 遺傳算法流程圖

3 案例分析

以某企業(yè)預(yù)混料生產(chǎn)線為例，該生產(chǎn)線的兩個配料車根據(jù)配方按料倉從左到右依次接料，兩車等待避讓時間很長，生產(chǎn)效率低下。

該配料系統(tǒng)有46 個雙列結(jié)構(gòu)的料倉，6 個卸料口。料倉兩兩并排共用一個下料口，占用一個工位，料倉編號1～23，卸料口編號為24～29。 其中9～15 號料倉和26、27 號卸料口屬于公共配料區(qū)。兩輛配料車分別生產(chǎn)兩種不同物料，且均不超過公共配區(qū)去接料，不在公共區(qū)卸料，在各自區(qū)域的卸料口輪流下料。 其結(jié)構(gòu)見圖2。

圖2 預(yù)混料生產(chǎn)線簡圖

已知如下條件：

（1）工位位置：由現(xiàn)場傳感器測得；

（2）配方：以企業(yè)最常用的兩種配方為例，1、2 號車配方集合分別為[25，1，4，6，8，9，11，12，13，15，24]，[28，9，10，11，12，13，15，17，18，20，29]；

（3）停留時間：1、2 號車對應(yīng)配方工位的停留時間集合分別為[0，26，28，20，35，23，36，25，15，21，45]，[0，9，20，11，15，20，15，29，16，25，30，30]；

（4）行駛速度：配料車三個速度檔為60m/min、40m/min、10m/min；

（5）仿真參數(shù)：種群大小初值20，迭代次數(shù)200。

運(yùn)用Matlab 編程進(jìn)行如下仿真實驗。

方案一： 通過仿真計算得到的兩車配料車路徑和最優(yōu)解周期與進(jìn)化代數(shù)見圖3，圖4。

圖3 配料車路徑圖

圖4 每代最優(yōu)解與進(jìn)化代數(shù)

由仿真結(jié)果得到的兩車最優(yōu)路徑分別為：[25，7，5，4，8，11，12，13，15，1，24]和[28，9，10，11，15，12，13，20，17，18，29]。配料周期為397.1s。計算周期取20 次的平均值用于本文的方案對比，平均值為396.6s。

方案二： 假設(shè)某次配料中，2 號配料車未完成的路徑集合為[12，9，15，11，17，18，28]時，1 號車開始配料。 通過仿真得到如圖5，圖6 所示。

圖5 配料車路徑圖

圖6 每代最優(yōu)解與進(jìn)化代數(shù)

由仿真結(jié)果得到的1 號車最優(yōu)路徑為：[25，5，7，8，15，13，12，11，4，1，24]。 配料周期387.0s。

在下次2 號配料車配料中，1 號車未完成的路徑集合為[13，12，11，4，1，24]。 仿真得到如圖7，圖8 所示。

圖7 配料車路徑圖

圖8 每代最優(yōu)解與進(jìn)化代數(shù)

圖8 Ⅰ型和Ⅱ型控制器誤差Fig.8 Error ofⅠandⅡcontroller

由仿真結(jié)果得到的2 號車最優(yōu)路徑為：[28，20，15，13，12，11，10，9，17，18，29]，周期時間317.8s。

由于方案二每次配料都需要重新規(guī)劃路徑，計算周期取10 次的平均值用于本文的方案對比， 仿真得到的兩輛配料車10 次配料周期取平均值分別為389.7s 和318.6s。

算法仿真得到的最優(yōu)解，與原方案相比配料周期縮短了30%左右， 同步方案兩種物料生產(chǎn)量均約為73 批/天，異步方案兩種物料生產(chǎn)量分別約為74 批/天和90 批/天。

從配料車路徑圖可以看出， 通過算法優(yōu)化避免了相遇問題，使同步方案避讓靈活的優(yōu)勢并沒有作用，反而在等待同步啟動的過程中花費更多的時間。相比之下，異步方案時間利用充分，啟停靈活，更適合應(yīng)用在規(guī)劃路徑方案中。

4 結(jié)論

基于改進(jìn)遺傳設(shè)計的方案均能減小配料周期， 提高配料系統(tǒng)生產(chǎn)效率。 異步方案比同步方案在效率和便捷性方面都更佳。 本文設(shè)計的配料車路徑優(yōu)化方案對企業(yè)提高生產(chǎn)率有一定參考價值。