面向智能制造車間的自動導(dǎo)引車調(diào)度優(yōu)化算法研究

崔占鵬，王永軍

（1.鄭州工商學(xué)院 信息工程學(xué)院，鄭州 451400；2.河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，焦作 454000）

0 引言

制造業(yè)作為國民經(jīng)濟的重要支柱，代表著一個國家的科學(xué)技術(shù)和產(chǎn)業(yè)力量。在激烈的市場競爭和不斷更新的情況下，現(xiàn)代制造面對著單件、小批量、個性化定制等多種生產(chǎn)形式，提出了敏捷制造、準(zhǔn)時制造、智能制造等模式。自動導(dǎo)引車具有半自動化和全自動兩種運輸作業(yè)，它能使物料的搬運和裝卸實現(xiàn)自動化[1]。目前，自動導(dǎo)引車已被廣泛地用于自動化倉儲、物流搬運、智能制造車間等各個方面。為滿足智能制造車間的作業(yè)任務(wù)，對于自動導(dǎo)引車的調(diào)度優(yōu)化研究成為了熱點問題。

李西興[2]等采用混合遺傳鯨魚優(yōu)化算法，實現(xiàn)了柔性車間的自動引導(dǎo)車的融合調(diào)度。本文利用了基于工序排序和機械選取兩個問題的二次矢量化編碼方法，給出了以優(yōu)先業(yè)務(wù)為基礎(chǔ)的自動引導(dǎo)車調(diào)度算法。提出了一種基于離散化改進鯨魚優(yōu)化算法的群體初始化方法。采用了基于遺傳算法的交叉和變異運算，結(jié)合了基于局部搜索的方法，實現(xiàn)了融合調(diào)度模型求解。該方法的融合調(diào)度效果較好，但調(diào)度效率較低。蘇少春[3]等采用多目標(biāo)狼群算法，研究了多模型自動導(dǎo)引車的路線優(yōu)選問題。對自動導(dǎo)引車的航向規(guī)劃問題進行了分析，提出了多個最優(yōu)解，并對自動導(dǎo)引車的兩級航跡進行了詳細的設(shè)計。將狼群算法應(yīng)用于非支配狀態(tài)的狼群群體中，采用群體的數(shù)量來維持群體的差異，從而提高了多目標(biāo)的性能，由此實現(xiàn)多模型自動導(dǎo)引車的路線優(yōu)選。該方法能夠有效實現(xiàn)自動導(dǎo)引車運行路線規(guī)劃，但調(diào)度效果有待提高。針對上述問題，提出了面向智能制造車間的自動導(dǎo)引車調(diào)度優(yōu)化算法。

1 智能制造車間自動導(dǎo)引車調(diào)度優(yōu)化算法

1.1 自動導(dǎo)引車調(diào)度優(yōu)化模型構(gòu)建

為有效實現(xiàn)智能制造車間自動導(dǎo)引車調(diào)度優(yōu)化，確保自動導(dǎo)引車行駛距離最短。首先，構(gòu)建自動導(dǎo)引車調(diào)度優(yōu)化模型。

假設(shè)存在一個任務(wù)指定位置集Q?W，W表示任務(wù)點集合，則將該任務(wù)指定位置集的總?cè)蝿?wù)量描述為：

當(dāng)自動導(dǎo)引車完成作業(yè)任務(wù)后，則返回作業(yè)起點，通過本文模型，獲取自動導(dǎo)引車行駛距離最短的路線。假設(shè)變量表示為自動導(dǎo)引車e從任務(wù)點i行駛至任務(wù)點j；變量表示為未行駛到任務(wù)點的情況。由此，可構(gòu)建的自動導(dǎo)引車調(diào)度優(yōu)化模型如下：

目標(biāo)函數(shù)為：

式(2)中，R為自動導(dǎo)引車集合，wij為任務(wù)點i至任務(wù)點j的行駛消耗，其中包括行駛的時間和距離。

約束條件為：

1）自動引導(dǎo)車裝載數(shù)量的約束：

式(3)中，ti表示為任務(wù)點i的總?cè)蝿?wù)量，P表示為自動導(dǎo)引車任務(wù)點具備數(shù)量。

2）每一個任務(wù)點只能進行一次訪問的約束：

3）從作業(yè)起點到任務(wù)點后，無自動導(dǎo)引車重新回到作業(yè)起點的約束：

4）路徑選擇的約束：

通過設(shè)置不同的參數(shù)，可以將自動導(dǎo)引車的優(yōu)化模型轉(zhuǎn)化為組合優(yōu)化問題。假定使用了某輛自動引導(dǎo)車，這個問題可以轉(zhuǎn)化為旅行商問題（TSP）模型。

若附加約束條件g0=GH，GH≤gi≤JH，其中，gi表示為自動導(dǎo)引車達到任務(wù)點的時間，[GH,JH]表示為實現(xiàn)每項任務(wù)的時間范圍。假設(shè)繼續(xù)附加約束其中，Tij為任務(wù)點i與任務(wù)點j之間的運輸時間，為自動導(dǎo)引車e行駛至任務(wù)點i的起始時間，則可獲取包含時間窗的自動導(dǎo)引車調(diào)度優(yōu)化問題的數(shù)學(xué)模型。

1.2 自動導(dǎo)引車調(diào)度優(yōu)化模型求解

在構(gòu)建自動導(dǎo)引車調(diào)度優(yōu)化模型后，采用遞歸神經(jīng)網(wǎng)絡(luò)[4]對自動導(dǎo)引車調(diào)度優(yōu)化模型進行求解。具體步驟如下：

1）相鄰矩陣構(gòu)造：利用網(wǎng)絡(luò)節(jié)點，繪制了自動導(dǎo)引車起始點、經(jīng)過路口和停車點，并用抽象的邊線將各點上的有向路徑相聯(lián)系，提出了一個有向圖表示為：

式(9)中，X為邊數(shù)，Z為節(jié)點數(shù)，C為節(jié)點數(shù)的矩陣。

根據(jù)上述自動導(dǎo)引車調(diào)度優(yōu)化模型可知，需要最優(yōu)目標(biāo)是邊(i,j)的長度和時間，從而構(gòu)造了距離和時間的相鄰矩陣。

2）約束處理：在此基礎(chǔ)上，提出了一種基于遞歸神經(jīng)網(wǎng)絡(luò)的能量函數(shù)的自動導(dǎo)引車調(diào)度優(yōu)化模型，并在各能量方程中加入了一條懲罰項完成約束處理，從而使得約束能量在網(wǎng)絡(luò)中的持續(xù)收斂得到了較好的穩(wěn)定性。

設(shè)定pω為任務(wù)點所需量，ξ,ζ為運輸順序，運輸點為ω,?。

假定每一行和每一列只有1個，而且不包含0行，也就是說，當(dāng)自動導(dǎo)引車經(jīng)過一次任務(wù)點，并且必須經(jīng)過一次時，返回作業(yè)起點的約束為：

假定0行中所有列的數(shù)值之和是B，也就是說，運輸?shù)穆窂綌?shù)目是B，那么，有約束如下：

假定整個矩陣中的每一個單位的總和是V+B，作業(yè)起點的起始數(shù)目是τ，那么，有約束如下：

假定自動導(dǎo)引車的作業(yè)起點是一個物料任務(wù)點，那么，有約束如下：

假定自動導(dǎo)引車有負荷約束，并且每個自動導(dǎo)引車都有裝載極限D(zhuǎn)，當(dāng)滿足極限條件時，將返回任務(wù)點，那么，有約束如下：

3）遞歸神經(jīng)網(wǎng)絡(luò)計算：假定相鄰矩陣中的每個單元都對應(yīng)于一個神經(jīng)元，并設(shè)置了Vωξ是在(ω,ξ)點處的輸出數(shù)值。在此基礎(chǔ)上，首先求出了遞歸神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，并對其進行了能量分析，得到了神經(jīng)元的傳輸和狀態(tài)轉(zhuǎn)換方程，并對其進行了連續(xù)的迭代，得到了網(wǎng)絡(luò)的收斂性。其能量函數(shù)表示為：

當(dāng)?shù)玫侥芰亢瘮?shù)后，由于該神經(jīng)網(wǎng)絡(luò)是以梯度的形式實現(xiàn)，因此，需通過以下形式計算神經(jīng)元的傳遞函數(shù)與狀態(tài)轉(zhuǎn)移方程表示為：

在獲得了能量函數(shù)之后，由于遞歸神經(jīng)網(wǎng)絡(luò)采用了梯度結(jié)構(gòu)，需要表達神經(jīng)元的傳輸函數(shù)和狀態(tài)轉(zhuǎn)換，在(ω,ξ)點處的輸出數(shù)值表示為：

4）調(diào)度優(yōu)化方案制定：通過對遞歸神經(jīng)網(wǎng)絡(luò)的收斂性分析，可以形成以0和1為單位的移位陣列。在該陣列中，自動導(dǎo)引車通過的節(jié)點為1，將各節(jié)點之間的距離和運輸時間相加，可以得到最短的距離和時間。根據(jù)上述條件，可獲得面向智能制造車間的自動導(dǎo)引車調(diào)度優(yōu)化方案。

1.3 自動導(dǎo)引車調(diào)度優(yōu)化實現(xiàn)

在對自動導(dǎo)引車調(diào)度優(yōu)化模型進行求解的基礎(chǔ)上，利用模擬退火算法[5]，實現(xiàn)自動導(dǎo)引車調(diào)度優(yōu)化?；谀M退火算法的自動導(dǎo)引車調(diào)度優(yōu)化算法流程如圖1所示。

圖1 基于模擬退火算法的自動導(dǎo)引車調(diào)度優(yōu)化算法流程

步驟1：對較高溫度T和自動導(dǎo)引車運輸路徑數(shù)目B進行初始化，設(shè)定溫度T的迭代次數(shù)為U；

步驟2：對初始自動導(dǎo)引車運輸路徑數(shù)目擾動產(chǎn)生新解ι;

步驟3：計算自動導(dǎo)引車運輸路徑長度的差為：

步驟4：如果Δ?＜0，接受新路線解ι，否則以為新解的接受概率。

步驟5：當(dāng)?shù)螖?shù)達到U時，新路線解ι沒有接受，則算法結(jié)束，輸出最優(yōu)自動導(dǎo)引車調(diào)度路線；否則T減少，返回步驟2。通過上述步驟，由此實現(xiàn)自動導(dǎo)引車調(diào)度優(yōu)化。

2 實驗分析

2.1 實驗環(huán)境設(shè)置

為了驗證面向智能制造車間的自動導(dǎo)引車調(diào)度優(yōu)化算法的有效性。實驗在Intel(R) Core(TM) i5-4570 CPU @3.20GHz CPU的計算機上測得，在Windows 7系統(tǒng)環(huán)境下，將MATLAB仿真平臺作為實驗環(huán)境。以某智能制造車間的自動導(dǎo)引車作為研究對象，分別采用文獻[2]算法、文獻[3]算法和所提算法進行對比，對上述自動導(dǎo)引車調(diào)度優(yōu)化模型的實現(xiàn)過程進行驗證。

2.2 自動導(dǎo)引車調(diào)度優(yōu)化效果對比分析

為驗證所提算法的自動導(dǎo)引車調(diào)度優(yōu)化效果，基于上述設(shè)置的實驗環(huán)境，選取2個任務(wù)點，得到不同算法從物料運輸點到達任務(wù)點的調(diào)度路線，對比分析結(jié)果如圖2所示。

分析圖2可知，不同算法從物料運輸點到達2個任務(wù)點的調(diào)度路線均有所不同。其中，文獻[2]算法從物料運輸點到達2個任務(wù)點的調(diào)度路線最遠，規(guī)劃后的路徑距離最遠，該調(diào)度路線呈現(xiàn)出曲線形狀。文獻[3]算法從物料運輸點到達2個任務(wù)點的調(diào)度路線明顯短于文獻[2]算法從物料運輸點到達2個任務(wù)點的調(diào)度路線，說明文獻[3]算法在從物料運輸點到達任務(wù)點的調(diào)度路線時，能夠有效縮短調(diào)度路徑。而相對于文獻[2]算法和文獻[3]算法，所提算法從物料運輸點到達2個任務(wù)點的調(diào)度路線最短，且均呈現(xiàn)出直線的形式。由此可知，所提算法的自動導(dǎo)引車調(diào)度優(yōu)化效果較好。

圖2 不同算法從物料運輸點到達任務(wù)點的調(diào)度路線

2.3 自動導(dǎo)引車調(diào)度優(yōu)化路徑長度對比分析

進一步驗證所提算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度，選取5個任務(wù)點進行自動導(dǎo)引車調(diào)度優(yōu)化，得到不同算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度，對比分析結(jié)果如圖3所示。

圖3 不同算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度

分析圖3可知，隨著任務(wù)點的增加，不同算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度隨之增加。當(dāng)任務(wù)點為5個時，文獻[2]算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度為3760m，文獻[3]算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度為5780m。而所提算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度僅為988m。由此可知，所提算法的自動導(dǎo)引車調(diào)度優(yōu)化路徑長度較短。

2.4 自動導(dǎo)引車調(diào)度優(yōu)化效率對比分析

在此基礎(chǔ)上，驗證所提算法的自動導(dǎo)引車調(diào)度優(yōu)化效率，將自動導(dǎo)引車調(diào)度優(yōu)化時間作為評價指標(biāo)，其自動導(dǎo)引車調(diào)度優(yōu)化時間越短，表明算法的自動導(dǎo)引車調(diào)度優(yōu)化效率越高。得到不同算法的自動導(dǎo)引車調(diào)度優(yōu)化時間，對比分析結(jié)果如表1所示。

表1 不同算法的自動導(dǎo)引車調(diào)度優(yōu)化時間

根據(jù)表1可知，隨著任務(wù)點的增加，不同算法的自動導(dǎo)引車調(diào)度優(yōu)化時間隨之增加。當(dāng)任務(wù)點為10個時，文獻[2]算法的自動導(dǎo)引車調(diào)度優(yōu)化時間為46.4s，文獻[3]算法的自動導(dǎo)引車調(diào)度優(yōu)化時間為51.2s，而所提算法的自動導(dǎo)引車調(diào)度優(yōu)化時間僅為38.4s。由此可知，所提算法的自動導(dǎo)引車調(diào)度優(yōu)化時間較短，能夠有效提高自動導(dǎo)引車調(diào)度優(yōu)化效率。

3 結(jié)語

針對智能制造車間存在的自動導(dǎo)引車調(diào)度優(yōu)化路徑長、效果差和效率低下的問題，研究了面向智能制造車間的自動導(dǎo)引車調(diào)度優(yōu)化算法。通過構(gòu)建自動導(dǎo)引車調(diào)度優(yōu)化模型，采用遞歸神經(jīng)網(wǎng)絡(luò)，求解自動導(dǎo)引車調(diào)度優(yōu)化模型。在此基礎(chǔ)上，利用模擬退火算法，實現(xiàn)自動導(dǎo)引車調(diào)度優(yōu)化。所提算法的自動導(dǎo)引車調(diào)度優(yōu)化效果較好，能夠有效提高調(diào)度優(yōu)化效率，縮短自動導(dǎo)引車調(diào)度優(yōu)化路徑長度。