基于遺傳算法對環(huán)形輸送線調(diào)度優(yōu)化研究

章俊哲，李金村，徐 健，吳宗毅，王 鵬

（1.北京機(jī)械工業(yè)自動(dòng)化研究所，北京 100120；2.北京機(jī)械工業(yè)自動(dòng)化研究所有限公司，北京 100120；3.北自所（北京）科技發(fā)展有限公司，北京 100120）

0 引言

在當(dāng)今全球化和市場化的潮流下，物流對于促進(jìn)世界經(jīng)濟(jì)、貿(mào)易和電子商務(wù)的發(fā)展有著巨大的意義。輸送線是物流倉儲(chǔ)中心的重要組成部分。托盤和貨物都需要經(jīng)過輸送線送至目的地，輸送線的效率和穩(wěn)定性決定了整個(gè)系統(tǒng)的效率。輸送線就像是人體中的血管，對整個(gè)系統(tǒng)起到了至關(guān)重要的作用。

隨著物流規(guī)模的擴(kuò)大，很多學(xué)者開始對其中的環(huán)節(jié)進(jìn)行研究和優(yōu)化。賀道坤等人為了解決環(huán)形輸送線揀選問題，利用條碼識(shí)別的方法對不同工件進(jìn)行分揀[1]。王鵬等人為了解決紙箱自動(dòng)輸送的效率能夠滿足生產(chǎn)需求，對PLC控制程序進(jìn)行了優(yōu)化[2]。劉煥牢等人為了解決生產(chǎn)線效率和人工等問題，對輸送線的機(jī)械結(jié)構(gòu)進(jìn)行了分析，使得系統(tǒng)實(shí)現(xiàn)了全自動(dòng)化且節(jié)約了人力[3]。以往的學(xué)者對輸送線的研究基本上都在于對機(jī)械結(jié)構(gòu)和控制程序的方面，很少有對于輸送線調(diào)度程序方面進(jìn)行優(yōu)化。

本文根據(jù)約束松弛條件對輸送線系統(tǒng)建立數(shù)學(xué)模型，再通過遺傳算法對系統(tǒng)進(jìn)行研究。利用仿真，找到系統(tǒng)的最優(yōu)解，根據(jù)比較得到遺傳算法對系統(tǒng)的優(yōu)化效果。

1 遺傳算法介紹

1.1 遺傳算法概述

遺傳算法是基于達(dá)爾文進(jìn)化論和孟德爾的遺傳學(xué)說所推理出來的。遺傳算法模擬自然界中生物繁衍和進(jìn)化的過程，將有利種群的特征得到延續(xù)，由此發(fā)展出的全局概念法[4]。遺傳算法借鑒生物進(jìn)化中的一些思想，通過生成種群、自然選擇、交叉、變異等操作，增強(qiáng)想要得到的屬性。

遺傳算法其中包括幾個(gè)重要的條件：

1）個(gè)體指帶有特征的實(shí)物，生物學(xué)中也成為染色體。個(gè)體通常的表現(xiàn)方式為二進(jìn)制串和符號(hào)串等。

2）基因是染色體中的某些特征單位，代表了個(gè)體的獨(dú)有特性。

3）種群是由所有個(gè)體組成的群體。在遺傳算法中，群體的規(guī)模一般設(shè)置為10～100之間。

4）適應(yīng)度是指個(gè)體對于約束條件的適應(yīng)情況。能夠更好適應(yīng)約束條件的個(gè)體，有更高的概率進(jìn)行遺傳，將基因傳遞給下一代。

5）編碼是指將現(xiàn)實(shí)問題的解映射到遺傳空間。

6）解碼是指將遺傳空間的解映射到現(xiàn)實(shí)問題。

7）遺傳算子是遺傳算法模擬生物進(jìn)化的重要手段。其中分為三種：選擇算子、交叉算子和變異算子[5]。

1.2 遺傳算法的基本流程

1）設(shè)置遺傳所需要的具體參數(shù)。

2）將現(xiàn)實(shí)問題映射至遺傳空間，進(jìn)行編碼。

3）生成初始化種群。

4）找到適應(yīng)度函數(shù)進(jìn)行計(jì)算，根據(jù)計(jì)算出的個(gè)體適應(yīng)度，選出合適的個(gè)體進(jìn)入下一代。

5）交叉變異。

6）不斷地迭代，直到滿足算法的終止條件。將種群中適應(yīng)度最高的解輸出，作為最優(yōu)解。

2 實(shí)例分析

2.1 系統(tǒng)概述

圖1是A廠的環(huán)形輸送線示意圖，主要設(shè)備為輥筒輸送機(jī)。

圖1 A廠環(huán)形輸送線系統(tǒng)示意圖

圖1左側(cè)為入環(huán)形輸送線端口，右側(cè)為拆垛區(qū)域。托盤由輸送線輸送至拆垛區(qū)域。每個(gè)拆垛區(qū)域由機(jī)器人和輸送線組成，分別有一個(gè)入滿托盤口和出空托盤口。托盤在拆垛完成以后，空托盤經(jīng)過環(huán)形輸送線運(yùn)送至出口?？胀斜P匯入輸送線不會(huì)影響滿托盤的輸送節(jié)拍。

2.2 環(huán)形輸送線調(diào)度模型建立

本章將針對環(huán)形線體系統(tǒng)的托盤調(diào)度問題進(jìn)行研究，對于傳統(tǒng)的輸送線而言，托盤是否進(jìn)入線體和送出線體僅僅依靠人為設(shè)置好的去向去分配，托盤會(huì)按照均分進(jìn)入或者送出輸送線的原則進(jìn)行分配。這種方法不會(huì)根據(jù)實(shí)際情況進(jìn)行調(diào)節(jié)，從而導(dǎo)致整體效率下降。

本文將用遺傳算法對環(huán)形輸送線貨物的調(diào)度系統(tǒng)進(jìn)行優(yōu)化。該系統(tǒng)的布置示意圖如圖2所示。

圖2 環(huán)形輸送線系統(tǒng)示意圖

圖2中，Ei表示入環(huán)形輸送線的端口，Uj表示出環(huán)形輸送線的端口。為了簡化系統(tǒng)便于研究問題，該系統(tǒng)的約束松弛條件如下：

1）線體為單向運(yùn)行（逆時(shí)針），不能反轉(zhuǎn)。

2）每段輸送線只能存放一個(gè)托盤。

3）輸送線被分配任務(wù)以后，到達(dá)相應(yīng)的出入端口，立即執(zhí)行，不存在等待時(shí)間。

4）每送出14個(gè)托盤被視為一個(gè)調(diào)度任務(wù)周期。

5）輸送線在運(yùn)行過程中，若發(fā)生故障，則停止系統(tǒng)的調(diào)度，不會(huì)對整體系統(tǒng)的調(diào)度優(yōu)化過程造成影響。

6）L1、L2和L3入環(huán)形輸送線端口的貨物視為無窮，進(jìn)入輸送線順序按照分配進(jìn)入。

托盤一次作業(yè)包括進(jìn)入線體、輸送、托盤送出線體三個(gè)過程，三個(gè)過程所用時(shí)間為：

上式中，T為輸送機(jī)完成一次輸送作業(yè)所需的時(shí)間，tw為托盤運(yùn)行在輸送線上花費(fèi)的時(shí)間，它包括托盤加減速ta，托盤勻速行走時(shí)間tc和托盤等待向前輸送時(shí)間tp。tl為托盤出入線體的輸送時(shí)間（定值）。由以上公式可以推出，tw決定了整個(gè)系統(tǒng)的運(yùn)行時(shí)間。而tw和托盤在輸送過程中是否出現(xiàn)堵塞相關(guān)。線體堵塞越嚴(yán)重，輸送時(shí)間就越長。想要優(yōu)化整個(gè)系統(tǒng)的效率，可以從減少堵塞次數(shù)這方面解決問題。

根據(jù)提出的解決方案，建立相應(yīng)的數(shù)學(xué)模型：

式(3)中，Bc（q）為第n個(gè)托盤內(nèi)由于前方輸送機(jī)堵塞而等待的次數(shù)，即

約束條件：

2.3 改進(jìn)單親遺傳算法設(shè)計(jì)

2.3.1 染色體編碼

將托盤的隊(duì)列進(jìn)行編碼，具體編碼方式如下：

編碼方式中的Xik表示第k個(gè)托盤在第i周期進(jìn)入線體的起始端口，Yik表示第k個(gè)托盤在第i周期被送出線體的目的端口。例如0103表示托盤先在E1口進(jìn)入線體，再去U3被送出線體，進(jìn)入拆垛區(qū)域，即托盤完成本次作業(yè)。

2.3.2 初始化種群

種群規(guī)模過大或過小對實(shí)驗(yàn)效果均不好，故設(shè)置種群規(guī)模為50。單個(gè)染色體形成的具體方法為：

托盤進(jìn)環(huán)形線體端口為：P1，…，Pk，…，Pk+i，…；

托盤出環(huán)形線體端口為：Q1，…，Qk，…，Qk+i，…；

從托盤進(jìn)環(huán)形線體端口中隨機(jī)選取Pk賦給從托盤出環(huán)形線體端口中隨機(jī)選取Qk賦給再從托盤進(jìn)環(huán)形線體端口中隨機(jī)選取Pk+i賦給從托盤出環(huán)形線體端口中隨機(jī)選取Qk+i賦給直到形成合格的染色體為止。

2.3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是判斷種群中個(gè)體好壞的標(biāo)準(zhǔn)，根據(jù)以上分析可得到相應(yīng)的目標(biāo)函數(shù)：

堵塞次數(shù)最少：

為了解決目標(biāo)問題，將適應(yīng)度函數(shù)定義為在一個(gè)周期內(nèi)找到問題。本章將把問題用一個(gè)適應(yīng)度函數(shù)表示：

其實(shí)把問題簡化為了找到F的最小值，即在一個(gè)調(diào)度周期內(nèi)的擁堵次數(shù)的最小值。我們將具體說明適應(yīng)度值的計(jì)算過程。

隨機(jī)生成一組染色體：

0205，0107，0304，0202，0304，0106，0303，0306，0101，0107，0205，0305，0306，0102

堵塞次數(shù)如下計(jì)算：

例如0205，0107這樣的基因串就會(huì)有堵塞的情況，前托盤先在2號(hào)入口進(jìn)線體，去5號(hào)出口送出托盤。后托盤在1號(hào)入口進(jìn)入線體，去7號(hào)出口送出托盤，若前托盤走過1號(hào)端口則在送出托盤的過程中，會(huì)導(dǎo)致后托盤堵塞一次。若前托盤沒走過1號(hào)端口則在1號(hào)端口送托盤的過程中，會(huì)導(dǎo)致前托盤堵塞一次。故不管出現(xiàn)什么情況，均會(huì)導(dǎo)致堵塞一次。0107，0304這樣的基因串不會(huì)出現(xiàn)堵塞，前托盤先在1號(hào)入口進(jìn)線體，去7號(hào)出口送出托盤。后托盤在3號(hào)入口進(jìn)入線體，去4號(hào)出口送出托盤，故不會(huì)堵塞?？梢缘玫疆?dāng)時(shí)，會(huì)使托盤擁堵一次。

2.3.4 遺傳算子設(shè)計(jì)

本文選擇算子采用混合選擇的方法，即采用保留優(yōu)秀個(gè)體和輪盤賭法結(jié)合。具體操作如下：

第一步隨機(jī)生成染色體，將適應(yīng)度大于平均適應(yīng)度的個(gè)體去除，保留下適應(yīng)度小于平均適應(yīng)度的個(gè)體。保留下來的個(gè)體進(jìn)入下一代；

第二步利用輪盤賭法將去除的個(gè)體進(jìn)行選擇，與第一步中保留下來的個(gè)體組成下一代種群。

得到的種群在利用基因重組的方法進(jìn)行單點(diǎn)換位算子，對每代染色體個(gè)體中進(jìn)行m次單點(diǎn)換位，計(jì)算模型如下：

式(7)中ceil是向上取整，fmin是種群中個(gè)體的最小適應(yīng)度，favg是種群的平均適應(yīng)度，fi是要單點(diǎn)換位的個(gè)體的適應(yīng)度，M為定值，即最大次數(shù)，設(shè)為5。

2.3.5 終止條件

在遺傳算法中，通常由兩種終止條件：第一種是得到最優(yōu)解以后算法終止。第二種是迭代至設(shè)置的值以后算法終止。本文采用第二種方法，設(shè)置迭代次數(shù)為500次。

3 仿真分析

3.1 仿真建立

通過上面分析，通過MATLAB進(jìn)行編程，可以得到詳細(xì)的算法，本文將以改進(jìn)的單親遺傳算法對貨物調(diào)度系統(tǒng)模型進(jìn)行優(yōu)化，具體步驟入圖3所示。

圖3 遺傳算法MATLAB設(shè)計(jì)流程圖

3.2 仿真數(shù)據(jù)分析

利用MATLAB進(jìn)行仿真。利用上文中的方法進(jìn)行數(shù)據(jù)仿真，進(jìn)行分析。

1）隨機(jī)生成一個(gè)調(diào)度周期內(nèi)的作業(yè)，如下：

托盤進(jìn)環(huán)形線體作業(yè)：01，03，02，01，02，03，02，01，03，02，01，02，03，02；

托盤出環(huán)形線體作業(yè)：05，06，02，03，01，07，04，06，02，05，01，07，01，03；

2）隨機(jī)生成初始化種群，如下：

0105，0306，0202，0103，0201，0307，0204，0106，0302.，0205，0101，0207，0301，0203。

按照算法計(jì)算可得到堵塞次數(shù)為7 次。利用MATLAB軟件進(jìn)行仿真，得到最優(yōu)解個(gè)體如圖4所示。

圖4 第一次調(diào)度周期最優(yōu)個(gè)體

最優(yōu)解個(gè)體的堵塞次數(shù)為2次。

其中一個(gè)最劣解個(gè)體堵塞次數(shù)為9次，具體如圖5所示。

圖5 第一次調(diào)度周期最劣個(gè)體

圖6和圖7分別為最優(yōu)解隨進(jìn)化代數(shù)的變化趨勢和平均值隨進(jìn)化代數(shù)的變化趨勢。從圖6可以看出最優(yōu)解的堵塞次數(shù)在20代左右出現(xiàn)變化，進(jìn)化到180代左右收斂得到了種群中的最優(yōu)解個(gè)體。圖7的變化趨勢與圖6基本一致，也是在180代左右收斂最佳。

圖6 最優(yōu)解隨進(jìn)化代數(shù)的變化趨勢

圖7 平均堵塞次數(shù)隨進(jìn)化代數(shù)的變化趨勢

利用上述方法將得到第二次周期，第三次周期的變化趨勢，進(jìn)行比較，如表1所示。

表1 優(yōu)化前后堵塞次數(shù)

由表1可以根據(jù)仿真優(yōu)化前后得出環(huán)形線經(jīng)過本文設(shè)計(jì)的遺傳算法模型，減少一個(gè)周期內(nèi)的堵塞次數(shù)，提升輸送線系統(tǒng)效率。

4 結(jié)語

本文提出了一種基于遺傳算法規(guī)劃環(huán)形輸送線系統(tǒng)的方法，并針對環(huán)形輸送線系統(tǒng)的瓶頸進(jìn)行分析。通過對系統(tǒng)進(jìn)行分析，得出適應(yīng)度函數(shù)，從而設(shè)計(jì)出改良單親遺傳算法。通過仿真驗(yàn)證遺傳算法運(yùn)用在該系統(tǒng)的優(yōu)越性，提高了物流效率。

現(xiàn)代化的物流系統(tǒng)還有許多其他的環(huán)節(jié)，例如RGV系統(tǒng)、AGV系統(tǒng)等。這些系統(tǒng)的貨物調(diào)度程序均可以用遺傳算法進(jìn)行優(yōu)化。