Research Repository

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

Rashidi, Hassan and Tsang, Edward PK (2011) 'A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals.' Computers & Mathematics with Applications, 61 (3). pp. 630-641. ISSN 0898-1221

Full text not available from this repository.

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

Item Type: Article
Uncontrolled Keywords: Search methods; Scheduling problems; Network Simplex Algorithm; Optimization; Container terminals
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 21 Nov 2013 07:19
Last Modified: 12 Apr 2022 02:45
URI: http://repository.essex.ac.uk/id/eprint/8534

Actions (login required)

View Item View Item