Scheduling Single-Load and Multi-Load AGVs in Container Terminals

Document Type : Research Article

Author

Abstract

In this paper, three solutions for scheduling problem of the Single-Load and Multi-Load Automated Guided Vehicles (AGVs) in Container Terminals are proposed. The problem is formulated as Constraint Satisfaction and Optimization. When capacity of the vehicles is one container, the problem is a minimum cost flow model. This model is solved by the highest performance Algorithm, i.e. Network Simplex Algorithm (NSA). If the capacity of the AGVs increases, the problem is a NP-hard problem. This problem has a huge search space and is tackled by the Simulated Annealing Method (SAM). Three approaches for its initial solution and a neighborhood function to the search method are implemented. The third solution is a hybrid of SAM and NSA. This hybrid is applied to the Heterogeneous AGVs scheduling problem in container terminals. Several the same random problems are generated, solved by SAM with the proposed approaches and the simulation results are compared. The experimental results show that NSA provides a good initial solution for SAM when the capacity of AGVs is heterogeneous.

Keywords

References

Periodicals:
[1]     E.P.K Tsang, “Scheduling techniques -- a comparative study”, British Telecom Technology Journal, Volume 13 (1), pp 16-28, Martlesham Heath, Ipswich, UK, 1995.
[2]     B.J Wook and  K.K Hwan,”A pooled dispatching strategy for automated guided vehicles in port container terminals”, International Journal of management science, Vol 6 (2), pp 47-60, 2000.
[3]     Chiang, Wen-Chyuan and A.R Robert, “Simulated Annealing Metaheuristic for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 63, pp 3-27, 1996.
[4]     M.D. Grigoriadis, ”An Efficient Implementation of the Network Simplex Method”, Mathematical Programming Study Vol. 26, pp 83-111, 1986.
[5]     M Grunow, H.O Günther and M Lehmann,  “Dispatching multi-load AGVs in highly automated seaport container terminals”, OR Spectrum, Volume 26 (2), pp 211-235, 2004.
[6]     K.G.Murty, L.Jiyin, W Yat-Wah, C,Zhang C.L Maria, J. Tsang and  L..Richard, “DSS (Decision Support System) for operations in a container terminal”. Decision Support System, Vol 39, pp 309-332., 2002.
 
Books:
[7]     R.K.Ahuja, T.L.Magnanti and J.B.Orlin, “Network Flows: Theory, Algorithms and Applications”. Prentice Hall, 1993.
 
 
Technical Reports:
[8]     Z.Czech and P Czarnas, “Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. In Proceedings of 10th Euromicto Workshop on Parallel Distributed and Network-Based Processing, Canary Islands, Spain, pp 376-383, 2002.
[9]     Y.Huang and W.J.Hsu, “Two Equivalent Integer Programming Models for Dispatching Vehicles at a Container Terminal”. CAIS, Technical Report 639798, School of Computer Engineering, Nan yang Technological University, Singapore, 2002.
[10]  H.Sen, “Dynamic AGV-Container Job Deployment”. Technical Report, HPCES Programme, Singapore-MIT Alliance, 2001.
[11]  M.Galati, H.Geng, and T.Wu, “A Heuristic Approach For The Vehicle Routing Problem Using Simulated Annealing”, Lehigh University, Technical Report IE316, 1998.
[12]  Y. Cheng, H. Sen, K. Natarajan, T. Ceo, and K.Tan,"Dispatching automated guided vehicles in a container terminal",  Technical Report, National University of Singapore, 2003.
 
Papers from Conference Proceedings (Published):
[13]  S.H Chan, “Dynamic AGV-Container Job Deployment”, Master of Science, University of Singapore, 2001.
[14]  H. Rashidi and E.P.K Tsang, "Applying the Extended Network Simplex Algorithm and a Greedy Search Method to Automated Guided Vehicle Scheduling", in Proceedings 2005, the 2nd Multidisciplinary International Conference on Scheduling: Theory & Applications (MISTA), New York, Vol 2, pp 677-693.
[15]  T. Hasama, H. Kokubugata and  H. Kawashima, “A Heuristic Approach Based on the String Model to Solve Vehicle Routing Problem with Backhauls”, Proceeding of the 5th World Congress on Intelligent Transport Systems (ITS), Seoul, 1998.
[16]  J.M. Patrick and P.M. Wagelmans, “Dynamic scheduling of handling equipment at automated container terminals”, Technical Report EI 2001-33, Erasmus University of Rotterdam, Econometric Institute, 2001.
[17]  J.M. Patrick and P.M. Wagelmans, “Effective algorithms for integrated scheduling of handling equipment at automated container terminals”, Technical Report EI 2001-19, Erasmus University of Rotterdam, Econometric Institute, 2001.
[18]  L. Qiu, W.J. Hsu, S.Y. Huang and H. Wang (2002), “Scheduling and Routing Algorithms for AGVs: a Survey”.  International Journal of Production Research, Taylor & Francis Ltd, Vol. 40 (3), pp 745-760.
[19]  L. Qiu, and W.J Hsu, “A bi-directional path layout for conflict-free routing of AGVs”. International Journal of Production Research, Volume 39 (10), pp 2177-2195, 2001.
[20]  L. Qiu and W.J. Hsu, “Scheduling of AGVs in a mesh-like path topology”. Technical Report CAIS-TR-01-34, Centre for Advanced Information Systems, School of Computer Engineering, Nanyang Technological University, Singapore, 2001.
[21]  J. Böse, T. Reiners, D. Steenken, and S.  Voß, ”Vehicle Dispatching at Seaport Container Terminals Using Evolutionary Algorithms”. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, IEEE, pp 1-10, 2000.
Dissertations:
[22]  H. Rashidi, “Dynamic Scheduling of Automated Guided Vehicles in Container Terminals”, PhD Thesis, Department of Computer Science, University of Essex, 2006.
[23]  D.J Kelly. and  G.M. ONeill, "The Minimum Cost Flow Problem and The Network  Simplex Solution Method", Master Degree Dissertation, University College, Dublin, 1993.
[24]  C. Y Leong, "Simulation study of dynamic AGV-container job deployment scheme", Master of science, National University of Singapore, 2001
[25]  A. Larsen, “The Dynamic Vehicle Routing Problem”, PhD Thesis, Technical University of Denmark, 2000.

Files

Share

How to cite

Statistics