基于物流路径网络的复杂离散制造系统物流建模仿真方法

摘要

本发明公开一种基于物流路径网络的复杂离散制造系统物流建模仿真方法，包括以下步骤，首先将各类物流路径统一映射为无向图；将各类物流设备统一映射为执行器集；将物流路径上分布的各个离散控制点统一映射为虚拟服务节点集，构成物流路径网络模型；基于所述物流路径网络模型，将车间物流关系映射成物流路径网络集，从物流路径网络集中任取两个点，分别记作初始点和目标点，求出作初始点到目标点的一条最短物流路径；根据规划的最短物流路径，求出执行物流任务运输距离最短的执行器。本发明提出了物流路径网络模型，对复杂系统中的物流设备、物流路径和物流控制逻辑进行了统一建模，为规划高效经济的物流调度路径提供了有效的技术支撑。

说明书

技术领域

本发明涉及离散制造系统建模仿真技术领域，具体为一种基于物流路径网络的复杂离散制造系统物流建模仿真方法。

背景技术

以复杂航空结构件制造为代表的离散制造系统物流关系十分复杂，主要体现在(1)物流设备多种多样，如AGV、机器人、传送带、堆垛机等。(2)物流路径布置形式多种多样，如直线型、环型、网络型等。(3)控制逻辑多种多样，例如AGV可以自动循迹，堆垛机一般只能沿固定导轨行驶。现有物流建模方法多集中于单一物流设备、单一物流路径下的建模仿真，如AGV的物流调度、AGV路径规划等，尚且缺乏针对多种物流设备、多种物流路径、多种物流控制逻辑下的统一建模、统一路径规划和物流调度方法。

发明内容

针对上述问题，本发明的目的在于提供一种对复杂离散制造系统的多种物流设备、多种物流布置形式、多种物流控制逻辑进行统一的建模仿真方法。技术方案如下：

一种基于物流路径网络的复杂离散制造系统物流建模仿真方法，包括以下步骤：

S1：建立物流路径网络模型：

将各类物流路径统一映射为无向图G；将物流设备绑定到相应物流路径上，将各类物流设备统一映射为执行器集E_Set；将物流路径上分布的各个离散控制点统一映射为虚拟服务节点集VSN_Set，虚拟服务节点包括不同路径不同执行器之间的物质交互点，并通过虚拟服务节点定义不同路径间不同执行器间的交互逻辑和交互位置；从而构成物流路径网络模型；

S2：映射车间物流关系：

基于所述物流路径网络模型，将车间物流关系映射成物流路径网络集LPN_Set，并确定不同物流路径之间的交互点；

S3：根据物流路径网络进行路径规划：

从物流路径网络集LPN_Set中任取两个点，分别记作初始点O_i(x_i,y_i)和目标点O_j(x_j,y_j)，求出从O_i到O_j的一条最短物流路径LP(O_i,O_j)；

S4：基于物流路径网络进行物流调度：

将物流任务记作T＝{F：O_i→O_j}，含义为：将待搬运物F从点O_i运输到点O_j；根据规划的最短物流路径，求出执行该物流任务T运输距离最短的执行器E(O)。

进一步的，所述物流路径网络模型的代数定义为：

LPN＝<E_Set,G,VSN_Set>

所述无向图G＝(V,E′,W)，V表示图的顶点，且V＝{“端点”，“交点”}，E′表示图的边，W表示边的权重；

物流路径的几何属性由顶点邻接矩阵G(V_i，V_j)来描述，且

W_ij＝Distance(V_i,V_j)

其中，V_i，V_j表示无向图的顶点，a_ij表示顶点V_i与V_j的邻接关系，W_ij表示顶点V_i与V_j的最短距离。

更进一步的，所述求出从O_i到O_j的一条最短物流路径LP(O_i,O_j)的具体方法为：

首先判断O_i和O_j是否位于同一物流路径网络上；

若O_i和O_j位于同一物流路径网络上，则为单源最短路径问题，根据Dijkstra算法得到一条最短路径LP(O_i,O_j)；

若O_i和O_j位于不同物流路径网络上，假设O_i位于LPN_i，O_j位于LPN_j，且LPN_i和LPN_j通过交互点P_i和P_j联通；则分解为两个单源最短路径问题，分别求解O_i到P_i的一条最短物流路径LP₁(O_i,P_i)和P_j到O_j的一条最短物流路径LP₂(P_j,O_j)，两次调用Dijkstra算法得到最短路径LP(O_i,O_j)＝LP₁(O_i,P_i)+LP₂(P_j,O_j)。

所述求出执行该物流任务T运输距离最短的执行器E(O)的具体方法为：

首先读取物流任务T＝{F：O_i→O_j}，判断O_i和O_j是否位于同一物流路径网络上；

若O_i和O_j位于同一物流路径网络上，遍历该物流路径网络的执行器集E_Set，得到状态为空闲的可选执行器集E(Idle)_Set；

再遍历可选执行器集E(Idle)_Set，以任一执行器E_i的当前位置P(E_i)为源点，待搬运物的当前位置O_i为目标点，依次调用Dijkstra算法，找到使物流路径LP(P_i,O_i)最短的执行器E(O)；将物流任务T分派给E(O)；

若O_i和O_j位于不同物流路径网络上，假设O_i位于LPN_i，O_j位于LPN_j，且LPN_i和LPN_j通过交互点P_i和P_j联通；则物流任务T分解为两个子任务T₁＝{F：O_i→P_i}和T₂＝{F：P_j→O_j}；

遍历LPN_i的执行器集E_Set_i，得到状态为空闲的可选执行器集E(Idle)_Set_i；再遍历E(Idle)_Set_i，以执行器E_i的当前位置P(E_i)为源点，待搬运物初始位置O_i为目标点，依次调用Dijkstra算法，找到使物流路径LP(O_i,P_i)最短的执行器E(O)₁；将物流任务T₁分派给执行器E(O)₁；

遍历LPN_j的执行器E_Set_j，得到状态为空闲的可选执行器集E(Idle)_Set_j；再遍历E(Idle)_Set_j，以执行器E_j的当前位置P(E_j)为源点，待搬运物初始位置P_j为目标点，依次调用Dijkstra算法，找到使物流路径LP(P_j,O_j)最短的执行器E(O)₂；将物流任务T₂分派给执行器E(O)₂。

本发明的有益效果是：本发明提出了物流路径网络模型，对复杂系统中的多种物流设备、多种物流路径和多种物流控制逻辑进行了统一建模，并给出了代数规范，为更快速进行物流布局设计和分析以及规划更高效更经济的物流调度路径提供了有效的技术支撑。

附图说明

图1为物流路径网络建模仿真步骤流程图。

图2为基于LPN的路径规划算法流程图。

图3为基于LPN的物流调度算法流程图。

图4为本发明实施例中某结构件加工车间布局示意图。

图5为本发明实施例中基于LPN的某结构件加工车间物流统一建模实施图。

具体实施方式

下面结合附图对本发明做进一步详细说明。如图1所示，一种基于物流路径网络的复杂离散制造系统物流建模仿真方法具体步骤为：

步骤S1、物流路径网络建模

将复杂离散制造系统中的各类物流设备统一映射为执行器(Executor，E)，将物流设备绑定到相应物流路径上，并用执行器集E_Set来描述物流设备集。将车间各种布置形式的物流路径统一用无向多连通图描述，记为G(V,E′,W)，并用顶点邻接矩阵G(V_i,V_j)来描述物流的几何属性。将物流路径上分布的离散控制点统一映射为虚拟服务节点(VirtualService>

虚拟服务节点包括不同路径不同执行器之间的物质交互点和服务单元与执行器的物质交互点两种，通过虚拟服务节点定义服务单元和执行器的交互逻辑和交互位置、不同路径间不同执行器间的交互逻辑和交互位置。

关于服务单元：将生产活动抽象为“服务”，包括缓冲服务和加工服务，此处的加工为广义的加工，涉及所有与生产工艺相关的活动，如机械加工、装配、检测、包装等。服务单元是由七元组或其子集组成的、通过虚拟服务节点关联起来的一个子系统。

物流路径网络(Logistics Path Network，LPN)模型的代数定义为：

LPN＝<E_Set,G,VSN_Set> (1)

其中：

E_Set：执行器(Executor，E)集，将物流设备统一映射成执行器，接收物流任务并执行，统一了各类物流设备。

G：无向多联通图，令G＝(V,E′,W)，其中V表示图的顶点，V＝{“端点”，“交点”}，E′表示图的边，W表示边的权重。通过顶点邻接矩阵G(V_i,V_j)来描述物流路径。

VSN_Set:虚拟服务节点(Virtual Service Node，VSN)集，通过虚拟服务节点一方面定义了路径上与生产设备的交互点，另一方面通过虚拟服务节点定义了不同路径网络的交互点。

步骤S2、车间物流关系映射

将车间物流关系映射成物流路径网络集(LPN_Set)，并定义不同物流路径之间的交互点(虚拟服务节点的一种)。

步骤S3、基于物流路径网络的路径规划

所讨论的路径规划问题可以详细描述为，从物流路径网络集(LPN_Set)中任取两个点，分别为初始点O_i(x_i,y_i)和目标点O_j(x_j,y_j)，求从O_i到O_j的一条最短物流路径LP(O_i,O_j)。

其具体流程如图2所示，首先任取点O_i和O_j，判断O_i和O_j是否位于同一LPN上。

若O_i和O_j位于同一LPN上，则为单源最短路径问题，根据Dijkstra算法【E.W.Dijkstra,A>i,O_j)。

若O_i和O_j位于不同LPN上，假设O_i位于LPN_i，O_j位于LPN_j，且LPN_i和LPN_j通过点P_i和点P_j联通；则可分解为两个单源最短路径问题，分别求解LP₁(O_i,P_i)和LP₂(P_j,O_j)，两次调用Dijkstra算法可得到最短路径LP(O_i,O_j)＝LP₁(O_i,P_i)+LP₂(P_j,O_j)。

步骤S4、基于物流路径网络的物流调度

所讨论的物流调度问题可以详细描述为，已知车间物流路径网络集(LPN_Set)和物流任务T＝{F：O_i→O_j}，其中物流任务T含义为：将待搬运物F，从点O_i运输到点O_j；求将执行该物流任务T运输距离最短的执行器E(O)。

其具体流程如图3所示，首先读取物流任务T＝{F：O_i→O_j}，判断O_i和O_j是否位于同一LPN上。

若O_i和O_j位于同一LPN上，遍历LPN的执行器集E_Set,得到状态为空闲的可选执行器集E(Idle)_Set；再遍历E(Idle)_Set，以执行器E_i的当前位置P(E_i)为源点，待搬运物的当前位置O_i为目标点，依次调用Dijkstra算法，找到使物流路径LP(P_i,O_i)最短的执行器E(O)；最后将物流任务T分派给E(O)。

若O_i和O_j位于不同LPN上，假设O_i位于LPN_i，O_j位于LPN_j，且LPN_i和LPN_j通过点P_i和点P_j联通；则物流任务T可分解为两个子任务T₁＝{F：O_i→P_i}和T₂＝{F：P_i→O_j}。

遍历LPN_i的执行器集E_Set_i，得到状态为空闲的可选执行器集E(Idle)_Set_i；再遍历E(Idle)_Set_i，以执行器E_i的当前位置P(E_i)为源点，待搬运物初始位置O_i为目标点，依次调用Dijkstra算法，找到使物流路径LP(P_i,O_i)最短的执行器E(O)₁；将物流任务T₁分派给执行器E(O)₁；

并遍历LPN_j的执行器E_Set_j，得到状态为空闲的可选执行器集E(Idle)_Set_j；再遍历E(Idle)_Set_j，以执行器E_j的当前位置P(E_j)为源点，待搬运物初始位置P_j为目标点，依次调用Dijkstra算法，找到使物流路径LP(P_j,O_j)最短的执行器E(O)₂；将物流任务T₂分派给执行器E(O)₂。

以下结合一个具体案例，简要介绍本发明的具体实施过程。如图4所示，某结构件加工车间分为6个区域，分别为立体仓库区(A#1)、装卸区(A#2)、数控加工区(A#3)、数控加工区(A#4)、柔性生产线(A#5)、柔性生产线(A#6)；物流设备分为1台出入库AGV、3台物料AGV、1台带导轨机器人和1台带导轨堆垛机；物流路径包括网络型的AGV路径、直线型带导轨机器人路径、直线型带导轨堆垛机路径，各路径之间通过交互点联通。其中立体仓库区(A#1)与装卸区(A#2)通过出入库AGV路径联通，由出入库AGV运送物料；装卸区(A#2)与数控加工区(A#3)、数控加工区(A#4)通过物料AGV路径联通，由3台物料AGV运送物料；数控加工区(A#3)、数控加工区(A#4)与柔性生产线(A#5)通过物料AGV路径联通，柔性生产线(A#5)内部由带导轨机器人运送物料；数控加工区(A#3)、数控加工区(A#4)与柔性生产线(A#6)通过物料AGV路径联通，由柔性生产线(A#6)内部带导轨堆垛机运送物料。

以该车间较为复杂的物料AGV路径P2为例，物流路径网络建模实施过程如下：

其如图5所示，3台物料AGV分别映射为执行器E₁，E₂和E₃，得到执行器集E_Set₂＝{E_i|1≤i≤3}，并绑定到物料AGV路径上。将网络型的物料AGV路径P₂用无向图描述，记为G₂(V,E′,W)，P₂共有顶点8个(其中端点2个，交点6个)，得到其顶点邻接矩阵G₂(V₈,V₈)。将物流路径上分布的离散控制点统一映射为虚拟服务节点(Virtual>2＝{{VSN₃},{VSN_i|11≤i≤23}}，其中VSN₃为P₂与P₁的交互点，VSN₂₂为P₂与P₄的交互点，VSN₂₃为P₂与P₄的交互点，其余11个VSN为执行器与服务单元进行物质交互的服务点。

物料AGV路径P₂的物流路径网络模型LPN₂的具体代数建模结果如下：

LPN₂＝<G₂,E_ext_Set₂,VSN_Set₂>

其中

E_Set₂＝{E_i|1≤i≤3}

mapping:AGV_i→E_i

VSN_Set₂＝{{VSN₃},{VSN_i|11≤i≤23}}

以图4所示车间为例，其车间物流关系映射结果如下：

LPN_Set＝{LPN_i|1<i<4}，其中4条路径(P₁至P₄)之间的交互点为：P₁和P₂的交互点为VSN₃和VSN₄；P₂和P₃的交互点为VSN₂₂和VSN₂₄；P₂和P₄的交互点为VSN₂₃和VSN₇。

基于图5所描述的LPN模型，其路径规划具体实施过程如下：

假设取起始点VSN₁和目标点VSN₅，求从VSN₁到VSN₅的一条最短物流路径LP(VSN₁,VSN₅)。由图5可知，VSN₁和VSN₅均位于LPN₁上，故为单源最短路径问题，根据Dijkstra算法【E.W.Dijkstra,A>1,VSN₅)＝{VSN₁,VSN₂,VSN₆，VSN₅}。

又假设取起始点VSN₁和目标点VSN₁₈，求从VSN₁到VSN₁₈的一条最短物流路径LP(VSN₁,VSN₁₈)。由图5可知，VSN₁位于LPN₁上，而VSN₁₈均位于LPN₂上，且LPN₁和LPN₂通过交互点VSN₃和VSN₄联通，则可分解为两个单源最短路径问题，分别求解LP₁(VSN₁,VSN₄)和LP₂(VSN₃,VSN₁₈)，两次调用Dijkstra算法可得到最短路径LP(VSN₁,VSN₁₈)＝LP₁(VSN₁,VSN₄)+LP₂(VSN₃,VSN₁₈)；最后得到具体最短路径为LP(VSN₁,VSN₁₈)＝{VSN₁,VSN₂,VSN₆，VSN₅，VSN₄,VSN₂₁,VSN₂₀，VSN₁₉，VSN₁₈}。

基于图5所描述的LPN模型，其物流调度具体实施过程如下：

假设现有物流任务T＝{F：VSN₁→VSN₅}，由图5可知，VSN₁和VSN₅均位于LPN₁上，且LPN₁上绑定了执行器集E_Set₁且E_Set₁＝{E₁|E₁＝{出入库AGV}}，遍历E_Set₁，若E₁空闲，则将T分配给E₁；若E₁状态不为空闲，则该物流任务挂起，等待执行。

又假设有物流任务T＝{F：VSN₁→VSN₁₈}，由图5可知，VSN₁位于LPN₁上，而VSN₁₈均位于LPN₂上，且LPN₁和LPN₂通过交互点VSN₃和VSN₄联通，则物流任务T可分解为两个子任务T₁＝{F：VSN₁→VSN₄}和T₂＝{F：VSN₃→VSN₁₈}。

遍历LPN₁的执行器集E_Set₁且E_Set₁＝{E₁|E₁＝{出入库AGV}}，遍历E_Set₁，若E₁空闲，则将T分配给E₁；若E₁状态不为空闲，则该物流任务挂起，等待执行。

遍历LPN₂的执行器E_Set₂且E_Set₂＝{E_i|E_i＝{物料AGV_i}(1≤i≤3)}，假设物料AGV₁和物料AGV₂状态为空闲，物料AGV₃状态为非空闲；则得到状态为空闲的可选执行器集E(Idle)_Set₂＝{E₁，E₂|E₁＝物料AGV₁，E₂＝物料AGV₂}；再遍历E(Idle)_Set₂，分别以执行器E₁(E₂)的当前位置P_E1(P_E2)为源点，待搬运物初始位置P_F为目标点，依次调用Dijkstra算法，得到物流路径LP(P_E1,P_F)和物流路径LP(P_E2,P_F)，若LP(P_E1,P_F)≤LP(P_E2,P_F)，则将物流任务T₂分配给E₁(物料AGV₁)；若LP(P_E1,P_F)>LP(P_E2,P_F)，则将物流任务T₂分配给E2(物料AGV₂)。

以上实施例仅对本发明的方法进行解释、说明，而非对其进行限制。凡是参照该实施例进行的修改和变更的行为，均在本申请的保护范围之内。