Dynamic Optimization of Simultaneous Dispatching and Conflict-free Routing for Automated Guided Vehicles - Petri Net Decomposition Approach
Dynamic Optimization of Simultaneous Dispatching and Conflict-free Routing for Automated Guided Vehicles - Petri Net Decomposition Approach
复制标题
DOI：
10.1299/jamdsm.4.701
复制
发表时间：
2010-01-01
影响因子：
0.9
通讯作者：
Inuiguchi, Masahiro
中科院分区：
文献类型：
--
作者：
Tanaka, Yuki;Nishi, Tatsushi;Inuiguchi, Masahiro
本文提出了一种Petri网分解方法，用于实时给出运输请求的动态情况下自动引导车辆调度和无冲突路径的同时优化。目标是在时间范围内使AGV运输系统的总吞吐量最大化。为了解决动态问题，在向AGV系统发送传输请求时，周期性地求解静态问题。采用Petri网分解方法对调度和无冲突路由进行同步优化。在该方法中，将Petri网分解为若干子网，分别用于任务子问题和AGV子问题，这些子问题可通过可达图上的最短路径算法求解。子网的局部解由罚函数算法协调。为了保证无冲突路由的生成，在优化算法中引入了一种新的死锁避免策略。针对动态环境下的路由问题，研究了调度优化和无冲突路由同步优化的效果。
In this paper, we propose an application of Petri Net decomposition approach for the simultaneous optimization of dispatching and conflict-free routing for automated guided vehicles in the dynamic situation where transport requests are given in real time. The objective is to maximize the total throughput of the AGV transport system during the time horizon. In order to solve the dynamic problem, static problems are periodically solved when the transport requests are given to the AGV system. The dispatching and conflict-free routing are simultaneously optimized by the Petri Net decomposition approach. In the proposed method, the Petri Net is decomposed into several subnets for task subproblems and AGV subproblems that can be solved by the shortest path algorithm on the reachability graph. The local solutions for the subnets are coordinated by a penalty function algorithm. To ensure the generation of conflict-free routing, a new deadlock avoidance strategy is incorporated in the optimization algorithm. The effects of simultaneous optimization of dispatching and conflict-free routing are investigated for routing problems in dynamic environments.