An Efficient Extension of Network Simplex Algorithm

Subject Areas : Design of Experiment

Hassan Rashidi ¹ , Edward P.K Tsang ²

1 - School of Computer Science and Electronic Systems Engineering, University of Essex, Colchester CO4 3SQ, U.K.
2 - School of Computer Science and Electronic Systems Engineering University of Essex, Colchester CO4 3SQ, U.K.

Received: 2008-11-03 Accepted : 2008-02-12 Published : 2010-02-07

Keywords: Scheduling, Container Terminals, Minimum Cost Flow Problem, Network Simplex Algorithm, Optimization methods,

Abstract :

In this paper, an efficient extension of network simplex algorithm is presented. In static scheduling problem, where there is no change in situation, the challenge is that the large problems can be solved in a short time. In this paper, the Static Scheduling problem of Automated Guided Vehicles in container terminal is solved by Network Simplex Algorithm (NSA) and NSA+, which extended the standard NSA. The algorithms are based on graph model and their performances are at least 100 times faster than traditional simplex algorithm for Linear Programs. Many random data are generated and fed to the model for 50 vehicles. We compared results of NSA and NSA+ for the static automated vehicle scheduling problem. The results show that NSA+ is significantly more efficient than NSA. It is found that, in practice, NSA and NSA+ take polynomial time to solve problems in this application.