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

陳佩峰　全成斌

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

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

中圖分類號： TN711?34； TP391 文獻標識碼： 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)貨物的加載/卸載位置會經(jīng)常發(fā)生擁堵問題[1?2]。擁擠會造成傳輸延遲和生產(chǎn)效率降低，因此很多研究都專注于OTC系統(tǒng)的調度問題優(yōu)化，同時也關注導引車系統(tǒng)的自動化控制。此類問題的研究可分為三類[3?5]：操作方法的研究，如集分區(qū)制定和菌落優(yōu)化；基于Petri網(wǎng)的離散事件模型方法研究；控制理論方法研究。

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

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

1 時間?序列建模

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

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

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

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

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

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

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

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

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

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

2.2 有限自動機方法

有限自動機（Finite Automaton，DFA）中的節(jié)點表示在離散時間活躍的離散動力學模型。

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

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

3.1 調度算法模型

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

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

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

4 實驗分析

本文實驗對象為圖1所示的彎道模型。

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

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

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

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

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

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

5 結 語

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

參考文獻

[1] 高文海，李明芳，曹樹貴，等.基于物聯(lián)網(wǎng)和數(shù)據(jù)挖掘的橋式起重機運行狀態(tài)預警系統(tǒng)[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].重型機械，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] 楊健維，何正友，減天磊.基于方向性加權模糊Petri網(wǎng)的電網(wǎng)故障診斷方法[J].中國電機工程學報，2010，30（34）：42?49.

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

[15] 劉春霞，田蕓.高?？蒲心芰Φ膮f(xié)同IWD粗糙集一塊神經(jīng)網(wǎng)絡評估模型[J].計算機工程與科學，2016，38（3）：486?493.endprint