Decomposition of petri nets and lagrangian relaxation for solving routing problems for AGVs

Tatsushi Nishi, Kenichi Shimatani, Masahiro Inuiguchi

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


In this paper, we propose a Lagrangian relaxation method for solving routing problems for multiple AGVs by decomposition of timed Petri nets. The AGV routing problem is represented by an optimal transition firing sequence problem for timed Petri nets. The timed Petri net is decomposed into several subnets in which the subproblem for each subnet can be easily solved by Dijkstra's algorithm. We show that each subproblem generated by each subnet is polynomially solvable. The optimality of the solution can be evaluated by the duality gap derived by the Lagrangian relaxation method. The performance of the proposed method is compared with a conventional optimisation algorithm with the penalty function method. The effectiveness of the proposed method is demonstrated.

Original languageEnglish
Pages (from-to)3957-3977
Number of pages21
JournalInternational Journal of Production Research
Issue number14
Publication statusPublished - Jan 2009
Externally publishedYes


  • Automated guided vehicles
  • Decomposition
  • Lagrangian relaxation
  • Petri nets
  • Routing

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Decomposition of petri nets and lagrangian relaxation for solving routing problems for AGVs'. Together they form a unique fingerprint.

Cite this