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

作者：Rashidi Hassan^*; Tsang Edward P K

来源：Computers & Mathematics with Applications, 2011, 61(3): 630-641.

DOI：10.1016/j.camwa.2010.12.009

• Search methods
• Scheduling problems
• Network Simplex Algorithm
• Optimization
• 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+.

• 出版日期2011-2