Developing Conflict-Free Routes for Automated Guided Vehicles

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

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1993-11, Vol.41 (6), p.1077-1090
Main Authors: Krishnamurthy, Nirup N, Batta, Rajan, Karwan, Mark H
Format: Article
Language:English
Subjects:
AGVS
Applied sciences
Automation
Computer science
control theory
systems
Control theory. Systems
Dispatching
Exact sciences and technology
Flexible manufacturing systems
Heuristics
Incumbents
Integers
Intelligent vehicles
Job shops
Materials handling
Mathematical models
Operations research
Process control. Computer integrated manufacturing
production/scheduling: planning
Studies
traffic models
transportation: freight/materials handling
Travel
Vehicle operation
Vehicles
Vertices
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.41.6.1077