Developing Conflict-Free Routes for Automated Guided Vehicles

Nirup N. Krishnamurthy, Rajan Batta and Mark H. Karwan
Additional contact information
Nirup N. Krishnamurthy: United Airlines, Chicago, Illinois
Rajan Batta: State University of New York at Buffalo, Buffalo, New York
Mark H. Karwan: State University of New York at Buffalo, Buffalo, New York

Operations Research, 1993, vol. 41, issue 6, 1077-1090

Abstract: Automated guided vehicles (AGVs) are a highly sophisticated and increasingly popular type of material handling device in flexible manufacturing systems. This paper details solution methodologies for the static routing problem in which demand assignment of the AGVs are known; the focus is to obtain an implementable solution within a reasonable amount of computer time. The objective is to minimize the makespan, while routing AGVs on a bidirectional network in a conflict-free manner. This problem is solved via column generation. The master problem in this column generation procedure has the makespan and vehicle interference constraints. Columns in the master problem are routes iteratively generated for each AGV. The subproblem is a constrained shortest path problem with time-dependent costs on the edges. An improvement procedure is developed to better the solution obtained at the end of the master-subproblem interactions. Several methods of iterating between the master and subproblem are experimented with in-depth computational experiments. Our empirical results indicate that the procedure as a whole usually generates solutions that are within a few percent of a proposed bound, within reasonable computer time.

Keywords: production/scheduling: planning; transportation: freight/materials handling; traffic models (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.6.1077 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:6:p:1077-1090

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().