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

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 s...

Full description

Saved in:
Bibliographic Details
Published in:International journal of production research 2009-07, Vol.47 (14), p.3957-3977
Main Authors: Nishi, Tatsushi, Shimatani, Kenichi, Inuiguchi, Masahiro
Format: Article
Language:English
Subjects:
AGVS
Applied sciences
automated guided vehicles
Decomposition
Exact sciences and technology
Graph algorithms
Inventory control, production control. Distribution
Lagrange multiplier
Lagrangian relaxation
Operational research and scientific management
Operational research. Management science
Optimization algorithms
petri nets
Routing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0020-7543
1366-588X
DOI:10.1080/00207540701846244