基于DFA?Petri网模型的桥式起重车辆IWD优化调度
陈佩峰 全成斌
摘 要： 为了提高车间桥式起重车辆（OTC）运行的有效调度，实现最短运输时间目标，提出基于DFA?Petri网模型的OTC系统车辆IWD优化调度算法。首先，对OTC系统车辆的时间?序列模型进行描述，并利用Petri网模型方法来简化优化约束，利用有限自动机（DFA）方法实现OTC系统状态空间二进制输入的降维，降低模型复杂度；其次，构建基于DFA?Petri网的OTC系统车辆优化调度模型，并利用智能水滴算法（IWD）进行调度优化；最后，通过仿真实验，验证了所提模型在调度时间指标上的优势，体现了所提方法的车辆调度实时性。
关键词： 桥式起重车辆； 有限自动机； Petri网； 智能水滴算法
中图分类号： 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）系统货物的加载/卸载位置会经常发生拥堵问题[1?2]。拥挤会造成传输延迟和生产效率降低，因此很多研究都专注于OTC系统的调度问题优化，同时也关注导引车系统的自动化控制。此类问题的研究可分为三类[3?5]：操作方法的研究，如集分区制定和菌落优化；基于Petri网的离散事件模型方法研究；控制理论方法研究。
文献[6]研究了大型机场行李处理系统的车辆交通流目标编码问题，并基于离散时间状态空间模型将无冲突路由问题转化为线性规划（LP）问题。文献[7]研究每个OTC系统的时间序列行为，并将离散时间状态空间模型的同步调度和无冲突路由转化为二进制整数线性规划问题。文献[8]在文献[7]的研究基础上提出了一种基于MPC的调度方法，实现了比文献[7]更快的调度优化速度。
本文研究目标是从不同的角度对OTC系统优化问题进行简化，实现更快的优化效率。在OTC系统车辆的时间?序列模型研究基础上，利用Petri网模型[9]简化优化约束，然后利用有限自动机方法[10]实现OTC系统状态空间二进制输入的降维，降低模型复杂度，并基于智能水滴算法（Intelligent Water Drop algorithm，IWD）实现了OTC系统的模型优化[11]。
1 时间?序列建模
本文考虑无向OTC系统的优化调度问题，该系统具有如下特征：OTC系统车辆为单轨运输线路，互不越界；存在轨道路口，即轨道交汇点。
此外，给出如下假设条件。在货物运输的开始阶段，OTC系统车辆从停车场出发，并且每个OTC车辆的速度是恒定的。系统的总运输时间定义为当所有OTC车辆到达指定区域的时间。所涉及的路由问题是根据运输任务找到合适的路径，以减少总的运输时间，并且具有FOUP位置加载/卸载功能。
无向OTC系统的时间序列建模方法如下。图1和图2为OTC系统模型[12]，并介绍了OTC车辆的时序行为模型[ss=1，2，…，S]。其中[S]为OTC车辆数量，指数vs是OTC车辆识别号码。
图1给出的是OTC系统的弯道模型示例。在这种情况下，OTC系统的轨道分为22个部分。本文称这些部分为“链接[i]”，[i=1，2，…，22]。其中图1中的链接2，8，14和20为停车场。
图2为一个OTC系统链接的内部结构。通过设定关口[uvslij]，每个链接可分成几部分。通过对关口[uvslij]的开/关状态进行设定，可实现对OTC系统车辆行为的有效控制。
2 基于有限自动机的Petri网求解
2.1 OTC系统时序?Petri网冲突模型
Petri网是一种由两种节点构成的有向，加权二分图[13]，包含库所（Place）、变迁（Transition）、有向弧（Connection）和令牌（Token）四部分，如图3所示。
在上述时序模型中，[P=p1，p2，…，p5]为库所（Place）、[t=t1，t2，t3]为变迁（Transition），图中黑点为令牌（Token），分别对应于问题区域、关口和车辆。特别是，这里总是认为每个链接弧的权重均属于{0，1}，并且不存在多个边。
在这种情况下，库所?变迁的关系可由事件矩阵表示，它为每个输入（从变迁到库所）和输出弧（从库所到变迁）分配一个非负整数（权重）。则输入弧的入射矩阵和每辆车的输出弧可表示为：[B+∈0，1n×m]和[B-∈0，1n×m]，并且其满足：
2.2 有限自动机方法
有限自动机（Finite Automaton，DFA）中的节点表示在离散时间活跃的离散动力学模型。
假设1：有限自动机给出一个连通有向图，其中每个弧的两端连接到一些节点，每个节点至少有一个输入弧和至少一个输出弧。若该假设满足，则以[A]进行标记。根据有限自动机的输入弧和输出弧的关系，如图4所示，可给出系统的隐式结构形式[14]：
3 基于IWD的OTC车辆调度优化
3.1 调度算法模型
3.2 模型优化步骤
该模型可通过优化计算方法进行优化，本文采用智能水滴算法，则基于IWD的OTC車辆调度优化过程如下：
Step1：设定智能水滴算法的种群规模为NP，种群维数为D，设置初始泥土含量[ini_soili，j]，水滴初始速度[ini_velIWD]，设定IWD算法的初始搜索区域大小为
4 实验分析
本文实验对象为图1所示的弯道模型。
实验硬件设置：Intel i5?6200U 2.5 GHz，8 GB ddr3 1600，WIN7旗舰版操作系统，对比求解器采用IBMILOG CPLEX 12.6，对比模型采用时序模型，则经过组合共有4种对比形式：IBMILOG CPLEX 12.6+本文模型、IBMILOG CPLEX 12.6+时序模型、IWD+本文模型和IWD+时序模型。
在图1中，每个链接有两个区域，但每个停车链接有4个区域，即[n=52]和[m=58]，进而可得原秩[B]为[51]，易得：
根据图5可知，对于选取的三种不同的对比方法，在车辆调度运行效率上，IWD+本文模型的计算方法要明显优于选取的对比算法。例如，在IWD+本文模型与IWD+时序模型对比中，前者在车辆调度运行效率上要优于选取的对比算法，这表明在模型改进上，采用的Petri网模型和有限自动机，实现了预想的约束简化优化和二进制输入的有效降维。在IWD+本文模型与IBMILOG CPLEX 12.6+本文模型对比中，前者车辆调度运行效率更优，表明采取的IWD算法相对传统的解算器具有更优异的优化效率。
根据图6所示的车辆数为2，6时的对比情况，可知在采用IWD优化算法前提下，采用本文模型的收敛曲线精度要优于选取时序模型的收敛曲线精度，并且最终的收敛值与图5所示基本对应，这表明本文模型可有效实现模型的简化，起到提升模型优化效果的作用。
表3给出采用IBMILOG CPLEX 12.6+本文模型、IBMILOG CPLEX 12.6+时序模型、IWD+本文模型和IWD+时序模型四种情形下的车辆路线交点冲突率和计算时间对比情况。
根据表3数据可知，在算法计算时间上，IWD+本文模型所需要的算法计算时间最少，表明算法的计算效率最好，这主要是算法中采用的Petri网模型和有限自动机，实现了预想的约束简化优化和二进制输入的有效降维及算法模型的有效简化，提高了优化计算效率。在冲突率指标中，IWD+本文模型的冲突率最低为15.3%左右，冲突率降低可实现资源调度过程的节约，有助于节省资源，提高车辆的执行效率。
5 结 语
本文提出基于DFA?Petri网模型的OTC系统车辆IWD优化调度算法，提高车间桥式起重车辆运行的调度效率，利用Petri网模型方法来简化优化约束，利用有限自动机方法实现OTC系统状态空间二进制输入的降维，降低模型复杂度，并利用智能水滴算法进行调度优化，实验结果验证了所提方法的有效性。实验过程发现，算法在冲突率方面虽然相对于对比策略更低，但是算法仍然具有改进的空间，下一步将重点针对降低车辆调度冲突率和计算时间进行研究。
参考文献
[1] 高文海，李明芳，曹树贵，等.基于物联网和数据挖掘的桥式起重机运行状态预警系统[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.
[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网的电网故障诊断方法[J].中国电机工程学报，2010，30（34）：42?49.
[14] 谢正卫，翟莹，邓培民，等.概率有限状态自动机的代数性质[J].2013，50（12）：2691?2698.
[15] 刘春霞，田芸.高校科研能力的协同IWD粗糙集一块神经网络评估模型[J].计算机工程与科学，2016，38（3）：486?493.
摘 要： 为了提高车间桥式起重车辆（OTC）运行的有效调度，实现最短运输时间目标，提出基于DFA?Petri网模型的OTC系统车辆IWD优化调度算法。首先，对OTC系统车辆的时间?序列模型进行描述，并利用Petri网模型方法来简化优化约束，利用有限自动机（DFA）方法实现OTC系统状态空间二进制输入的降维，降低模型复杂度；其次，构建基于DFA?Petri网的OTC系统车辆优化调度模型，并利用智能水滴算法（IWD）进行调度优化；最后，通过仿真实验，验证了所提模型在调度时间指标上的优势，体现了所提方法的车辆调度实时性。
关键词： 桥式起重车辆； 有限自动机； Petri网； 智能水滴算法
中图分类号： 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）系统货物的加载/卸载位置会经常发生拥堵问题[1?2]。拥挤会造成传输延迟和生产效率降低，因此很多研究都专注于OTC系统的调度问题优化，同时也关注导引车系统的自动化控制。此类问题的研究可分为三类[3?5]：操作方法的研究，如集分区制定和菌落优化；基于Petri网的离散事件模型方法研究；控制理论方法研究。
文献[6]研究了大型机场行李处理系统的车辆交通流目标编码问题，并基于离散时间状态空间模型将无冲突路由问题转化为线性规划（LP）问题。文献[7]研究每个OTC系统的时间序列行为，并将离散时间状态空间模型的同步调度和无冲突路由转化为二进制整数线性规划问题。文献[8]在文献[7]的研究基础上提出了一种基于MPC的调度方法，实现了比文献[7]更快的调度优化速度。
本文研究目标是从不同的角度对OTC系统优化问题进行简化，实现更快的优化效率。在OTC系统车辆的时间?序列模型研究基础上，利用Petri网模型[9]简化优化约束，然后利用有限自动机方法[10]实现OTC系统状态空间二进制输入的降维，降低模型复杂度，并基于智能水滴算法（Intelligent Water Drop algorithm，IWD）实现了OTC系统的模型优化[11]。
1 时间?序列建模
本文考虑无向OTC系统的优化调度问题，该系统具有如下特征：OTC系统车辆为单轨运输线路，互不越界；存在轨道路口，即轨道交汇点。
此外，给出如下假设条件。在货物运输的开始阶段，OTC系统车辆从停车场出发，并且每个OTC车辆的速度是恒定的。系统的总运输时间定义为当所有OTC车辆到达指定区域的时间。所涉及的路由问题是根据运输任务找到合适的路径，以减少总的运输时间，并且具有FOUP位置加载/卸载功能。
无向OTC系统的时间序列建模方法如下。图1和图2为OTC系统模型[12]，并介绍了OTC车辆的时序行为模型[ss=1，2，…，S]。其中[S]为OTC车辆数量，指数vs是OTC车辆识别号码。
图1给出的是OTC系统的弯道模型示例。在这种情况下，OTC系统的轨道分为22个部分。本文称这些部分为“链接[i]”，[i=1，2，…，22]。其中图1中的链接2，8，14和20为停车场。
图2为一个OTC系统链接的内部结构。通过设定关口[uvslij]，每个链接可分成几部分。通过对关口[uvslij]的开/关状态进行设定，可实现对OTC系统车辆行为的有效控制。
2 基于有限自动机的Petri网求解
2.1 OTC系统时序?Petri网冲突模型
Petri网是一种由两种节点构成的有向，加权二分图[13]，包含库所（Place）、变迁（Transition）、有向弧（Connection）和令牌（Token）四部分，如图3所示。
在上述时序模型中，[P=p1，p2，…，p5]为库所（Place）、[t=t1，t2，t3]为变迁（Transition），图中黑点为令牌（Token），分别对应于问题区域、关口和车辆。特别是，这里总是认为每个链接弧的权重均属于{0，1}，并且不存在多个边。
在这种情况下，库所?变迁的关系可由事件矩阵表示，它为每个输入（从变迁到库所）和输出弧（从库所到变迁）分配一个非负整数（权重）。则输入弧的入射矩阵和每辆车的输出弧可表示为：[B+∈0，1n×m]和[B-∈0，1n×m]，并且其满足：
2.2 有限自动机方法
有限自动机（Finite Automaton，DFA）中的节点表示在离散时间活跃的离散动力学模型。
假设1：有限自动机给出一个连通有向图，其中每个弧的两端连接到一些节点，每个节点至少有一个输入弧和至少一个输出弧。若该假设满足，则以[A]进行标记。根据有限自动机的输入弧和输出弧的关系，如图4所示，可给出系统的隐式结构形式[14]：
3 基于IWD的OTC车辆调度优化
3.1 调度算法模型
3.2 模型优化步骤
该模型可通过优化计算方法进行优化，本文采用智能水滴算法，则基于IWD的OTC車辆调度优化过程如下：
Step1：设定智能水滴算法的种群规模为NP，种群维数为D，设置初始泥土含量[ini_soili，j]，水滴初始速度[ini_velIWD]，设定IWD算法的初始搜索区域大小为
4 实验分析
本文实验对象为图1所示的弯道模型。
实验硬件设置：Intel i5?6200U 2.5 GHz，8 GB ddr3 1600，WIN7旗舰版操作系统，对比求解器采用IBMILOG CPLEX 12.6，对比模型采用时序模型，则经过组合共有4种对比形式：IBMILOG CPLEX 12.6+本文模型、IBMILOG CPLEX 12.6+时序模型、IWD+本文模型和IWD+时序模型。
在图1中，每个链接有两个区域，但每个停车链接有4个区域，即[n=52]和[m=58]，进而可得原秩[B]为[51]，易得：
根据图5可知，对于选取的三种不同的对比方法，在车辆调度运行效率上，IWD+本文模型的计算方法要明显优于选取的对比算法。例如，在IWD+本文模型与IWD+时序模型对比中，前者在车辆调度运行效率上要优于选取的对比算法，这表明在模型改进上，采用的Petri网模型和有限自动机，实现了预想的约束简化优化和二进制输入的有效降维。在IWD+本文模型与IBMILOG CPLEX 12.6+本文模型对比中，前者车辆调度运行效率更优，表明采取的IWD算法相对传统的解算器具有更优异的优化效率。
根据图6所示的车辆数为2，6时的对比情况，可知在采用IWD优化算法前提下，采用本文模型的收敛曲线精度要优于选取时序模型的收敛曲线精度，并且最终的收敛值与图5所示基本对应，这表明本文模型可有效实现模型的简化，起到提升模型优化效果的作用。
表3给出采用IBMILOG CPLEX 12.6+本文模型、IBMILOG CPLEX 12.6+时序模型、IWD+本文模型和IWD+时序模型四种情形下的车辆路线交点冲突率和计算时间对比情况。
根据表3数据可知，在算法计算时间上，IWD+本文模型所需要的算法计算时间最少，表明算法的计算效率最好，这主要是算法中采用的Petri网模型和有限自动机，实现了预想的约束简化优化和二进制输入的有效降维及算法模型的有效简化，提高了优化计算效率。在冲突率指标中，IWD+本文模型的冲突率最低为15.3%左右，冲突率降低可实现资源调度过程的节约，有助于节省资源，提高车辆的执行效率。
5 结 语
本文提出基于DFA?Petri网模型的OTC系统车辆IWD优化调度算法，提高车间桥式起重车辆运行的调度效率，利用Petri网模型方法来简化优化约束，利用有限自动机方法实现OTC系统状态空间二进制输入的降维，降低模型复杂度，并利用智能水滴算法进行调度优化，实验结果验证了所提方法的有效性。实验过程发现，算法在冲突率方面虽然相对于对比策略更低，但是算法仍然具有改进的空间，下一步将重点针对降低车辆调度冲突率和计算时间进行研究。
参考文献
[1] 高文海，李明芳，曹树贵，等.基于物联网和数据挖掘的桥式起重机运行状态预警系统[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.
[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网的电网故障诊断方法[J].中国电机工程学报，2010，30（34）：42?49.
[14] 谢正卫，翟莹，邓培民，等.概率有限状态自动机的代数性质[J].2013，50（12）：2691?2698.
[15] 刘春霞，田芸.高校科研能力的协同IWD粗糙集一块神经网络评估模型[J].计算机工程与科学，2016，38（3）：486?493.
