Decomposition of Petri nets and Lagrangian relaxation for solving routing problems for AGVs

Abstract

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.

Keywords:

• automated guided vehicles
• routing
• petri nets
• decomposition
• Lagrangian relaxation

Acknowledgement

This research was partially funded by the Tateisi Science and Technology Foundation 2006–2007.