1. A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals
- Author
-
Rashidi, Hassan and Tsang, Edward P.K.
- Subjects
- *
AUTOMATED guided vehicle systems , *ALGORITHMS , *CONTAINER terminals , *POLYNOMIALS , *ALGEBRA , *MATHEMATICS - Abstract
Abstract: In this paper, a scheduling problem for automated guided vehicles in container terminals is defined and formulated as a Minimum Cost Flow model. This problem is then solved by a novel algorithm, NSA+, which extended the standard Network Simplex Algorithm (NSA). Like NSA, NSA+ is a complete algorithm, which means that it guarantees optimality of the solution if it finds one within the time available. To complement NSA+, an incomplete algorithm Greedy Vehicle Search (GVS) is designed and implemented. The NSA+ and GVS are compared and contrasted to evaluate their relative strength and weakness. With polynomial time complexity, NSA+ can be used to solve very large problems, as verified in our experiments. Should the problem be too large for NSA+, or the time available for computation is too short (as it would be in dynamic scheduling), GVS complements NSA+. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF