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

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

0 引言

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

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

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

1 遺傳算法介紹

1.1 遺傳算法概述

遺傳算法是基于達(dá)爾文進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)所推理出來(lái)的。遺傳算法模擬自然界中生物繁衍和進(jìn)化的過(guò)程，將有利種群的特征得到延續(xù)，由此發(fā)展出的全局概念法[4]。遺傳算法借鑒生物進(jìn)化中的一些思想，通過(guò)生成種群、自然選擇、交叉、變異等操作，增強(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)度是指?jìng)€(gè)體對(duì)于約束條件的適應(yīng)情況。能夠更好適應(yīng)約束條件的個(gè)體，有更高的概率進(jìn)行遺傳，將基因傳遞給下一代。

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

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

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

1.2 遺傳算法的基本流程

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

2）將現(xiàn)實(shí)問(wèn)題映射至遺傳空間，進(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ū)域。托盤(pán)由輸送線輸送至拆垛區(qū)域。每個(gè)拆垛區(qū)域由機(jī)器人和輸送線組成，分別有一個(gè)入滿托盤(pán)口和出空托盤(pán)口。托盤(pán)在拆垛完成以后，空托盤(pán)經(jīng)過(guò)環(huán)形輸送線運(yùn)送至出口?？胀斜P(pán)匯入輸送線不會(huì)影響滿托盤(pán)的輸送節(jié)拍。

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

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

本文將用遺傳算法對(duì)環(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)形輸送線的端口。為了簡(jiǎn)化系統(tǒng)便于研究問(wèn)題，該系統(tǒng)的約束松弛條件如下：

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

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

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

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

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

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

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

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

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

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

約束條件：

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

2.3.1 染色體編碼

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

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

2.3.2 初始化種群

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

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

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

從托盤(pán)進(jìn)環(huán)形線體端口中隨機(jī)選取Pk賦給從托盤(pán)出環(huán)形線體端口中隨機(jī)選取Qk賦給再?gòu)耐斜P(pán)進(jìn)環(huán)形線體端口中隨機(jī)選取Pk+i賦給從托盤(pán)出環(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)問(wèn)題，將適應(yīng)度函數(shù)定義為在一個(gè)周期內(nèi)找到問(wèn)題。本章將把問(wèn)題用一個(gè)適應(yīng)度函數(shù)表示：

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

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

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

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

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

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

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

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

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

得到的種群在利用基因重組的方法進(jìn)行單點(diǎn)換位算子，對(duì)每代染色體個(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 仿真建立

通過(guò)上面分析，通過(guò)MATLAB進(jìn)行編程，可以得到詳細(xì)的算法，本文將以改進(jìn)的單親遺傳算法對(duì)貨物調(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è)，如下：

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

本文提出了一種基于遺傳算法規(guī)劃環(huán)形輸送線系統(tǒng)的方法，并針對(duì)環(huán)形輸送線系統(tǒng)的瓶頸進(jìn)行分析。通過(guò)對(duì)系統(tǒng)進(jìn)行分析，得出適應(yīng)度函數(shù)，從而設(shè)計(jì)出改良單親遺傳算法。通過(guò)仿真驗(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)化。