Petri net decomposition approach to optimization of route planning problems for AGV systems

Tatsushi Nishi, Ryota Maeno

Research output: Contribution to journalArticlepeer-review

95 Citations (Scopus)


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.

Original languageEnglish
Article number5454421
Pages (from-to)523-537
Number of pages15
JournalIEEE Transactions on Automation Science and Engineering
Issue number3
Publication statusPublished - Jul 2010
Externally publishedYes


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

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Petri net decomposition approach to optimization of route planning problems for AGV systems'. Together they form a unique fingerprint.

Cite this