基于DFA?Petri網(wǎng)模型的橋式起重車輛IWD優(yōu)化調(diào)度

陳佩峰　全成斌

摘 要： 為了提高車間橋式起重車輛（OTC）運(yùn)行的有效調(diào)度，實(shí)現(xiàn)最短運(yùn)輸時(shí)間目標(biāo)，提出基于DFA?Petri網(wǎng)模型的OTC系統(tǒng)車輛IWD優(yōu)化調(diào)度算法。首先，對OTC系統(tǒng)車輛的時(shí)間?序列模型進(jìn)行描述，并利用Petri網(wǎng)模型方法來簡化優(yōu)化約束，利用有限自動(dòng)機(jī)（DFA）方法實(shí)現(xiàn)OTC系統(tǒng)狀態(tài)空間二進(jìn)制輸入的降維，降低模型復(fù)雜度；其次，構(gòu)建基于DFA?Petri網(wǎng)的OTC系統(tǒng)車輛優(yōu)化調(diào)度模型，并利用智能水滴算法（IWD）進(jìn)行調(diào)度優(yōu)化；最后，通過仿真實(shí)驗(yàn)，驗(yàn)證了所提模型在調(diào)度時(shí)間指標(biāo)上的優(yōu)勢，體現(xiàn)了所提方法的車輛調(diào)度實(shí)時(shí)性。

關(guān)鍵詞： 橋式起重車輛； 有限自動(dòng)機(jī)； Petri網(wǎng)； 智能水滴算法

中圖分類號： TN711?34； TP391 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）22?0110?06

Abstract： In order to improve the operation scheduling efficiency of overhead travelling cranes （OTCs） at the workshop and achieve the goal of the shortest transit time， the IWD optimization algorithm of the OTC system vehicle scheduling based on DFA?Petri net model is proposed. First， the time?series model of the OTC system vehicle is described， the Petri net model is used to simplify the optimization constraints， and the finite automaton is used to realize the dimensionality reduction of the binary input in OTC system state space， which can decrease the complexity of the model. Second， the vehicle optimization scheduling model of the OTC system based on DFA?Petri net is constructed， and the intelligent water drop algorithm is used to optimize the scheduling. The advantage of the proposed model in the scheduling time index was verified in the simulation experiment， which reflects the real?time performance of vehicle scheduling of the proposed method.

Keywords： overhead travelling crane； finite automaton； Petri net； intelligent water drop algorithm

0 引 言

在橋式起重車輛（Overhead Travelling Cranes，OTC）系統(tǒng)貨物的加載/卸載位置會(huì)經(jīng)常發(fā)生擁堵問題[1?2]。擁擠會(huì)造成傳輸延遲和生產(chǎn)效率降低，因此很多研究都專注于OTC系統(tǒng)的調(diào)度問題優(yōu)化，同時(shí)也關(guān)注導(dǎo)引車系統(tǒng)的自動(dòng)化控制。此類問題的研究可分為三類[3?5]：操作方法的研究，如集分區(qū)制定和菌落優(yōu)化；基于Petri網(wǎng)的離散事件模型方法研究；控制理論方法研究。

文獻(xiàn)[6]研究了大型機(jī)場行李處理系統(tǒng)的車輛交通流目標(biāo)編碼問題，并基于離散時(shí)間狀態(tài)空間模型將無沖突路由問題轉(zhuǎn)化為線性規(guī)劃（LP）問題。文獻(xiàn)[7]研究每個(gè)OTC系統(tǒng)的時(shí)間序列行為，并將離散時(shí)間狀態(tài)空間模型的同步調(diào)度和無沖突路由轉(zhuǎn)化為二進(jìn)制整數(shù)線性規(guī)劃問題。文獻(xiàn)[8]在文獻(xiàn)[7]的研究基礎(chǔ)上提出了一種基于MPC的調(diào)度方法，實(shí)現(xiàn)了比文獻(xiàn)[7]更快的調(diào)度優(yōu)化速度。

本文研究目標(biāo)是從不同的角度對OTC系統(tǒng)優(yōu)化問題進(jìn)行簡化，實(shí)現(xiàn)更快的優(yōu)化效率。在OTC系統(tǒng)車輛的時(shí)間?序列模型研究基礎(chǔ)上，利用Petri網(wǎng)模型[9]簡化優(yōu)化約束，然后利用有限自動(dòng)機(jī)方法[10]實(shí)現(xiàn)OTC系統(tǒng)狀態(tài)空間二進(jìn)制輸入的降維，降低模型復(fù)雜度，并基于智能水滴算法（Intelligent Water Drop algorithm，IWD）實(shí)現(xiàn)了OTC系統(tǒng)的模型優(yōu)化[11]。

1 時(shí)間?序列建模

本文考慮無向OTC系統(tǒng)的優(yōu)化調(diào)度問題，該系統(tǒng)具有如下特征：OTC系統(tǒng)車輛為單軌運(yùn)輸線路，互不越界；存在軌道路口，即軌道交匯點(diǎn)。

此外，給出如下假設(shè)條件。在貨物運(yùn)輸?shù)拈_始階段，OTC系統(tǒng)車輛從停車場出發(fā)，并且每個(gè)OTC車輛的速度是恒定的。系統(tǒng)的總運(yùn)輸時(shí)間定義為當(dāng)所有OTC車輛到達(dá)指定區(qū)域的時(shí)間。所涉及的路由問題是根據(jù)運(yùn)輸任務(wù)找到合適的路徑，以減少總的運(yùn)輸時(shí)間，并且具有FOUP位置加載/卸載功能。

無向OTC系統(tǒng)的時(shí)間序列建模方法如下。圖1和圖2為OTC系統(tǒng)模型[12]，并介紹了OTC車輛的時(shí)序行為模型[ss=1，2，…，S]。其中[S]為OTC車輛數(shù)量，指數(shù)vs是OTC車輛識別號碼。

圖1給出的是OTC系統(tǒng)的彎道模型示例。在這種情況下，OTC系統(tǒng)的軌道分為22個(gè)部分。本文稱這些部分為“鏈接[i]”，[i=1，2，…，22]。其中圖1中的鏈接2，8，14和20為停車場。endprint

圖2為一個(gè)OTC系統(tǒng)鏈接的內(nèi)部結(jié)構(gòu)。通過設(shè)定關(guān)口[uvslij]，每個(gè)鏈接可分成幾部分。通過對關(guān)口[uvslij]的開/關(guān)狀態(tài)進(jìn)行設(shè)定，可實(shí)現(xiàn)對OTC系統(tǒng)車輛行為的有效控制。

2 基于有限自動(dòng)機(jī)的Petri網(wǎng)求解

2.1 OTC系統(tǒng)時(shí)序?Petri網(wǎng)沖突模型

Petri網(wǎng)是一種由兩種節(jié)點(diǎn)構(gòu)成的有向，加權(quán)二分圖[13]，包含庫所（Place）、變遷（Transition）、有向弧（Connection）和令牌（Token）四部分，如圖3所示。

在上述時(shí)序模型中，[P=p1，p2，…，p5]為庫所（Place）、[t=t1，t2，t3]為變遷（Transition），圖中黑點(diǎn)為令牌（Token），分別對應(yīng)于問題區(qū)域、關(guān)口和車輛。特別是，這里總是認(rèn)為每個(gè)鏈接弧的權(quán)重均屬于{0，1}，并且不存在多個(gè)邊。

在這種情況下，庫所?變遷的關(guān)系可由事件矩陣表示，它為每個(gè)輸入（從變遷到庫所）和輸出弧（從庫所到變遷）分配一個(gè)非負(fù)整數(shù)（權(quán)重）。則輸入弧的入射矩陣和每輛車的輸出弧可表示為：[B+∈0，1n×m]和[B-∈0，1n×m]，并且其滿足：

2.2 有限自動(dòng)機(jī)方法

有限自動(dòng)機(jī)（Finite Automaton，DFA）中的節(jié)點(diǎn)表示在離散時(shí)間活躍的離散動(dòng)力學(xué)模型。

假設(shè)1：有限自動(dòng)機(jī)給出一個(gè)連通有向圖，其中每個(gè)弧的兩端連接到一些節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)至少有一個(gè)輸入弧和至少一個(gè)輸出弧。若該假設(shè)滿足，則以[A]進(jìn)行標(biāo)記。根據(jù)有限自動(dòng)機(jī)的輸入弧和輸出弧的關(guān)系，如圖4所示，可給出系統(tǒng)的隱式結(jié)構(gòu)形式[14]：

3 基于IWD的OTC車輛調(diào)度優(yōu)化

3.1 調(diào)度算法模型

3.2 模型優(yōu)化步驟

該模型可通過優(yōu)化計(jì)算方法進(jìn)行優(yōu)化，本文采用智能水滴算法，則基于IWD的OTC車輛調(diào)度優(yōu)化過程如下：

Step1：設(shè)定智能水滴算法的種群規(guī)模為NP，種群維數(shù)為D，設(shè)置初始泥土含量[ini_soili，j]，水滴初始速度[ini_velIWD]，設(shè)定IWD算法的初始搜索區(qū)域大小為

4 實(shí)驗(yàn)分析

本文實(shí)驗(yàn)對象為圖1所示的彎道模型。

實(shí)驗(yàn)硬件設(shè)置：Intel i5?6200U 2.5 GHz，8 GB ddr3 1600，WIN7旗艦版操作系統(tǒng)，對比求解器采用IBMILOG CPLEX 12.6，對比模型采用時(shí)序模型，則經(jīng)過組合共有4種對比形式：IBMILOG CPLEX 12.6+本文模型、IBMILOG CPLEX 12.6+時(shí)序模型、IWD+本文模型和IWD+時(shí)序模型。

在圖1中，每個(gè)鏈接有兩個(gè)區(qū)域，但每個(gè)停車鏈接有4個(gè)區(qū)域，即[n=52]和[m=58]，進(jìn)而可得原秩[B]為[51]，易得：

根據(jù)圖5可知，對于選取的三種不同的對比方法，在車輛調(diào)度運(yùn)行效率上，IWD+本文模型的計(jì)算方法要明顯優(yōu)于選取的對比算法。例如，在IWD+本文模型與IWD+時(shí)序模型對比中，前者在車輛調(diào)度運(yùn)行效率上要優(yōu)于選取的對比算法，這表明在模型改進(jìn)上，采用的Petri網(wǎng)模型和有限自動(dòng)機(jī)，實(shí)現(xiàn)了預(yù)想的約束簡化優(yōu)化和二進(jìn)制輸入的有效降維。在IWD+本文模型與IBMILOG CPLEX 12.6+本文模型對比中，前者車輛調(diào)度運(yùn)行效率更優(yōu)，表明采取的IWD算法相對傳統(tǒng)的解算器具有更優(yōu)異的優(yōu)化效率。

根據(jù)圖6所示的車輛數(shù)為2，6時(shí)的對比情況，可知在采用IWD優(yōu)化算法前提下，采用本文模型的收斂曲線精度要優(yōu)于選取時(shí)序模型的收斂曲線精度，并且最終的收斂值與圖5所示基本對應(yīng)，這表明本文模型可有效實(shí)現(xiàn)模型的簡化，起到提升模型優(yōu)化效果的作用。

表3給出采用IBMILOG CPLEX 12.6+本文模型、IBMILOG CPLEX 12.6+時(shí)序模型、IWD+本文模型和IWD+時(shí)序模型四種情形下的車輛路線交點(diǎn)沖突率和計(jì)算時(shí)間對比情況。

根據(jù)表3數(shù)據(jù)可知，在算法計(jì)算時(shí)間上，IWD+本文模型所需要的算法計(jì)算時(shí)間最少，表明算法的計(jì)算效率最好，這主要是算法中采用的Petri網(wǎng)模型和有限自動(dòng)機(jī)，實(shí)現(xiàn)了預(yù)想的約束簡化優(yōu)化和二進(jìn)制輸入的有效降維及算法模型的有效簡化，提高了優(yōu)化計(jì)算效率。在沖突率指標(biāo)中，IWD+本文模型的沖突率最低為15.3%左右，沖突率降低可實(shí)現(xiàn)資源調(diào)度過程的節(jié)約，有助于節(jié)省資源，提高車輛的執(zhí)行效率。

5 結(jié) 語

本文提出基于DFA?Petri網(wǎng)模型的OTC系統(tǒng)車輛IWD優(yōu)化調(diào)度算法，提高車間橋式起重車輛運(yùn)行的調(diào)度效率，利用Petri網(wǎng)模型方法來簡化優(yōu)化約束，利用有限自動(dòng)機(jī)方法實(shí)現(xiàn)OTC系統(tǒng)狀態(tài)空間二進(jìn)制輸入的降維，降低模型復(fù)雜度，并利用智能水滴算法進(jìn)行調(diào)度優(yōu)化，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提方法的有效性。實(shí)驗(yàn)過程發(fā)現(xiàn)，算法在沖突率方面雖然相對于對比策略更低，但是算法仍然具有改進(jìn)的空間，下一步將重點(diǎn)針對降低車輛調(diào)度沖突率和計(jì)算時(shí)間進(jìn)行研究。

參考文獻(xiàn)

[1] 高文海，李明芳，曹樹貴，等.基于物聯(lián)網(wǎng)和數(shù)據(jù)挖掘的橋式起重機(jī)運(yùn)行狀態(tài)預(yù)警系統(tǒng)[J].礦山機(jī)械，2014，42（2）：41?44.

[2] LE A T. Adaptive sliding mode control of overhead cranes with varying cable length [J]. Journal of mechanical science & technology， 2013， 27（3）： 885?893.

[3] 唐方雄，丁克勤，魏化中，等.基丁ANSYS/FE?safe的橋式起重主梁疲勞壽命分析[J].重型機(jī)械，2015（3）：62?65.

[4] LIU P F， XING L J， LIU Y L， et al. Strength analysis and optimal design for main girder of double?trolley overhead traveling crane using finite element method [J]. Journal of failure analysis and prevention， 2014， 14（1）： 76?86.endprint

[5] JOLEVSKI D， BEGO O. Model predictive control of gantry/bridge crane with anti?sway algorithm [J]. Journal of mechanical science & technology， 2015， 29（2）： 827?834.

[6] RANJBARI L， Shirdel A H， ASLAHI?SHAHRI M， et al. Designing precision fuzzy controller for load swing of an overhead crane [J]. Neural computing & applications， 2015， 26（7）： 1555?1560.

[7] BOSCHETTI G， CARACCIOLO R， RICHIEDEI D. A non?time based controller for load swing damping and path?tracking in robotic cranes [J]. Journal of intelligent & robotic systems， 2014， 76（2）： 201?217.

[8] HUANG Bangfu， TIAN Naiyuan， SHI Zhe， et al. Material flow control technology of ironmaking and steelmaking interface [J]. Journal of Central South University， 2014， 21（9）： 3559?3567.

[9] BOUNEB M， SAIDOUNI D E， ILIE J M. A reduced maximality labeled transition system generation for recursive Petri nets [J]. Formal aspects of computing， 2015， 27（5?6）： 951?973.

[10] STEFANYUK V L. The behavior of a finite?state automaton in a fuzzy environment： theory and applications [J]. Scientific and technical information processing， 2015， 42（6）： 426?431.

[11] HAGH M T， EBRAHIMIAN H， GHADIMI N. Hybrid intelligent water drop bundled wavelet neural network to solve the islanding detection by inverter?based DG [J]. Frontiers in energy， 2015， 9（1）： 75?90.

[12] GARC?A A A， BOBADILLA I G， FIGUEROA G A， et al. Virtual reality training system for maintenance and operation of high?voltage overhead power lines [J]. Virtual reality， 2016， 20（1）： 27?40.

[13] 楊健維，何正友，減天磊.基于方向性加權(quán)模糊Petri網(wǎng)的電網(wǎng)故障診斷方法[J].中國電機(jī)工程學(xué)報(bào)，2010，30（34）：42?49.

[14] 謝正衛(wèi)，翟瑩，鄧培民，等.概率有限狀態(tài)自動(dòng)機(jī)的代數(shù)性質(zhì)[J].2013，50（12）：2691?2698.

[15] 劉春霞，田蕓.高校科研能力的協(xié)同IWD粗糙集一塊神經(jīng)網(wǎng)絡(luò)評估模型[J].計(jì)算機(jī)工程與科學(xué)，2016，38（3）：486?493.endprint