A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals

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. © 2010 Elsevier Ltd. All rights reserved.