Back to Search
Start Over
A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals
- Source :
-
Computers & Mathematics with Applications . Feb2011, Vol. 61 Issue 3, p630-641. 12p. - Publication Year :
- 2011
-
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]
Details
- Language :
- English
- ISSN :
- 08981221
- Volume :
- 61
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Computers & Mathematics with Applications
- Publication Type :
- Academic Journal
- Accession number :
- 57547073
- Full Text :
- https://doi.org/10.1016/j.camwa.2010.12.009