Petri Net Decomposition Approach to Optimization of Route Planning Problems for AGV Systems

作者：Nishi Tatsushi^*; Maeno Ryota

来源：IEEE Transactions on Automation Science and Engineering, 2010, 7(3): 523-537.

DOI：10.1109/TASE.2010.2043096

• Automated guided vehicles
• decomposition
• discrete-event systems
• Petri nets (PNs)
• route planning problem
• shortest-path algorithm

In this paper, we propose a Petri Net (PN) decomposition approach to the optimization of route planning problems for automated guided vehicles (AGVs) in semiconductor fabrication bays. An augmented PN is developed to model the concurrent dynamics for multiple AGVs. The route planning problem to minimize the total transportation time is formulated as an optimal transition firing sequence problem for the PN. The PN is decomposed into several subnets such that the subnets are made independent by removing the original shared places and creating its own set of resource places for each subnet with the appropriate connections. The partial solution derived at each subnet is not usually making a feasible solution for the entire PN. The penalty function algorithm is used to integrate the solutions derived at the decomposed subnets. The optimal solution for each subnet is repeatedly generated by using the shortest-path algorithm in polynomial time with a penalty function embedded in the objective function. The effectiveness of the proposed method is demonstrated for a practical-sized route planning problem in semiconductor fabrication bay from computational experiments.
Note to Practitioners-For rapid growth of transportation systems for semiconductor fabrication bay, it is required to generate a collision-free route planning for multiple AGVs efficiently to minimize the total traveling time. Conventional decomposition techniques for mathematical programming need reformulation of the original problem when new constraints are added, that makes it extremely difficult to modify the optimization model. PNs can be used as a tool to integrate modeling, simulation, and optimization for designing transportation systems. This paper presents a modeling and optimization of route planning for multiple AGVs by PN. The main difficulty for optimization is the state explosion for PN. To reduce computational complexity, we propose a PN decomposition approach for solving large-scale optimization problems efficiently. The PN model is partitioned into several decomposed subnets. The local solutions of the subnets are integrated by the novel optimization algorithm. The shorter computation time by the proposed method enables us to use the proposed methodology for the rapid design and dynamic optimization for AGVs transportation systems in semiconductor manufacturing.

• 出版日期2010-7