Citation
Applying The Extended Network Simplex Algorithm To Dynamic Automated Guided Vehicle Scheduling. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 677-692, 2005.
Paper
Abstract
Scheduling of vehicles in the container terminal is often studied as a static problem in the literature, where all information, including the number of jobs, their arrival time, etc., is known beforehand. The objective is generally minimizing the total travelling and/or waiting times of the vehicles. When the situation changes, for example new jobs arrive or a section of the terminal is blocked, new solutions are generated from scratch. In this paper, the problem of dynamically scheduling automated guided vehicles in the container terminals is formulated as a minimum cost flow problem. 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 it guarantees optimality of the solution if it finds one within the time available. Our software, DSAGV, employs NSA+ and can find the global optimal solutions for 3,000 jobs and 10 millions arcs in the graph model within 2 minutes on a 2.4 GHz Pentium PC. To complement NSA+, an incomplete algorithm Greedy Vehicle Search (GVS) is designed and implemented. To evaluate the relative strength and weakness of NSA+ and GVS, the two algorithms are compared for the dynamic automated vehicle scheduling problem. Both NSA+ and GVS are practical algorithms for dynamic automatic vehicle scheduling.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2005-677-692-P, author = {H. Rashidi and E. P. K. Tsang},
title = {Applying The Extended Network Simplex Algorithm To Dynamic Automated Guided Vehicle Scheduling},
booktitle = {In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA},
year = {2005},
editor = {G. Kendall and L. Lei and M. Pinedo},
pages = {677--692},
note = {Paper},
abstract = {Scheduling of vehicles in the container terminal is often studied as a static problem in the literature, where all information, including the number of jobs, their arrival time, etc., is known beforehand. The objective is generally minimizing the total travelling and/or waiting times of the vehicles. When the situation changes, for example new jobs arrive or a section of the terminal is blocked, new solutions are generated from scratch. In this paper, the problem of dynamically scheduling automated guided vehicles in the container terminals is formulated as a minimum cost flow problem. 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 it guarantees optimality of the solution if it finds one within the time available. Our software, DSAGV, employs NSA+ and can find the global optimal solutions for 3,000 jobs and 10 millions arcs in the graph model within 2 minutes on a 2.4 GHz Pentium PC. To complement NSA+, an incomplete algorithm Greedy Vehicle Search (GVS) is designed and implemented. To evaluate the relative strength and weakness of NSA+ and GVS, the two algorithms are compared for the dynamic automated vehicle scheduling problem. Both NSA+ and GVS are practical algorithms for dynamic automatic vehicle scheduling.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-677-692-P.pdf} }