Write your message
Volume 11 - Winter and Spring 2019                   ijmt 2019, 11 - Winter and Spring 2019: 1-12 | Back to browse issues page

XML Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Rashidi H. Simulation and Evaluation of Network Simplex Algorithm and its Extensions for Vehicle Scheduling Problems in Ports. ijmt 2019; 11 :1-12
URL: http://ijmt.ir/article-1-647-en.html
Simulation and Evaluation of Network Simplex Algorithm and its Extensions for Vehicle Scheduling Problems in Ports
Hassan Rashidi *
Allameh Tabataba’i University
Abstract:   (4428 Views)
The Minimum Cost Flow (MCF) problem is a well-known problem in the area of network optimisation. To tackle this problem, Network Simplex Algorithm (NSA) is the fastest solution method. NSA has three extensions, namely Network Simplex plus Algorithm (NSA+), Dynamic Network Simplex Algorithm (DNSA) and Dynamic Network Simplex plus Algorithm (DNSA+). The objectives of the research reported in this paper are to simulate and investigate the advantages and disadvantages of NSA compared with those of the three extensions in practical situations. To perform the evaluation, an application of these algorithms to scheduling problem of automated guided vehicles in container terminal is used. In the experiments, the number of iterations, CPU-time required to solve problems, overheads and complexity are considered.
Keywords: Network Simplex Algorithm, Dynamic Network Simplex Algorithm, Optimization Methods, Dynamic Scheduling, Container Terminals
Full-Text [PDF 1007 kb]   (1961 Downloads)    
Type of Study: Research Paper | Subject: Maritime Transport and Port Management
Received: 2018/10/10 | Accepted: 2019/02/24
References
1. Grigoriadis, M. (1986). An Efficient Implementation of the Network Simplex Method. Mathematical Programming Study, 26, 83-111. [DOI:10.1007/BFb0121089]
2. Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network lows: Theory, Algorithms and Applications. Prentice Hall.
3. Kelly, D., & ONeill, G. (1993). The Minimum Cost Flow Problem and The Network Simplex Solution Method (Master degree dissertation).University College, Dublin.
4. Rashidi, H., & Tsang, E. (2011). A Complete and an Incomplete Algorithm for Automated Guided Vehicle Scheduling in Container Terminals. Journal of Computers and Mathematics with Applications, 61, 630-641. [DOI:10.1016/j.camwa.2010.12.009]
5. Rashidi, H. (2014). A Dynamic Version for the Network Simplex Algorithm. Journal of Applied Soft Computing, 24, 414-422. [DOI:10.1016/j.asoc.2014.07.017]
6. Parpalea, M., & Ciurea, E. (2011). Maximum Flow of Minimum Bi-Criteria Cost in Dynamic Networks. Recent researches in computer science, 118-123.
7. Wook, B., & Hwan, K. (2000). A pooled dispatching strategy for automated guided vehicles in port container terminals. International Journal of Management Science, 6(2), 47-60.
8. Goldberg, A., & Kennedy, R. (1993). An efficient cost scaling algorithm for the assignment problem.Technical Report, Stanford University.
9. Mulvey, J. (1978). Pivot Strategies for Primal Simplex Network Codes. Association for Computing Machinery Journal, 25, 266-270. [DOI:10.1145/322063.322070]
10. Bradley, G., Brown, G., & Graves, G. (1977). Design and Implementation of Large Scale Primal Transshipment Algorithms. Management Science, 24, 1-38. [DOI:10.1287/mnsc.24.1.1]
11. Eppstein, D. (1999). Clustering for faster network simplex pivots. In Proceedings of the 5th ACM-SIAM Symposium, Discrete Algorithms, 160-166.
12. Lobel, A. (2000). A Network Simplex Implementation. Technical Report, Konrad-Zuse-Zentrumfur Informations technik Berlin (ZIB).
13. Maros, I. (2003). A General Pricing Scheme for the Simplex Method. Technical Report, London, Department of Computing, Imperial College.
14. Cunningham, W. (1979). Theoretical properties of the network simplex method. Mathematics of Operations research, 4(2), 196-208. [DOI:10.1287/moor.4.2.196]
15. Aronson, J. (1989). A Survey of Dynamic Network Flows. Annal of Operation research, 20, 1-66. [DOI:10.1007/BF02216922]
16. Skutella, M. (2009). An Introduction to Network Flows Over Time. Research Trends in Combinatorial Optimization, Berlin: Springer.
17. Powell, W., Jaillet, P., & Odoni, A. (1995). Stochastic and Dynamic Networks and Routing. Handbooks in Operations Research and Management Science (pp. 141-295). Amsterdam: North-Holland.
18. Hoppe, B. (1995). Efficient Dynamic Network Flow Algorithms (Doctoral dissertation). Cornell University, New York.
19. Fonoberova, M., & Lozovanu, D. (2007). Optimal Dynamic Flows in Networks and Applications. The International Symposium the Issues of Calculation Optimization, Communications.Crimea, Ukraine, pp. 292-293.
20. Rauch, M. (1992). Fully Dynamic Graph Algorithms and Their Data Structures (Doctoral dissertation).Princeton University, New Jersey.
21. Afshari Rad, M., & Taghizadeh Kakhki, H. (2013). Maximum Dynamic Network Flow Interdiction Problem: New Formulation and Solution Procedures Original Research Article. Computers & Industrial Engineering, 65(4), 531-536. [DOI:10.1016/j.cie.2013.04.014]
22. Ratliff, H., Sicilia, G., & Lubore, S. (1975). Finding the n most vital links in flow networks. Management Science, 21, 531-539. [DOI:10.1287/mnsc.21.5.531]
23. Geranis, G., Paparrizos, K., & Sifaleras, A. (2012). On a Dual Network Exterior Point Simplex Type Algorithm and Its Computational Behavior. Operations Research, 46, 211-234. [DOI:10.1051/ro/2012015]
24. Shen, W., Nie, Y., & Zhang, H. (2007). A Dynamic Network Simplex Method for Designing Emergency Evacuation Plans. Transportation Research Record, 20(22), 83-93. [DOI:10.3141/2022-10]
25. Zheng, H., & Chiu, Y. (2011). A Network Flow Algorithm for the Cell-Based Single-Destination System Optimal Dynamic Traffic Assignment Problem. Transportation Science, 45(1), 121-137. [DOI:10.1287/trsc.1100.0343]
26. Parpalea, M. (2011). A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem. Open Journal of Discrete Mathematics, 1(3), 116-126. [DOI:10.4236/ojdm.2011.13015]
27. Parpalea, M., & Ciurea, E. (2011). The Quickest Maximum Dynamic Flow of Minimum Cost. Journal of Applied Mathematics and Informatics, 5(3), 266-274.
28. Hosseini, S. (2010). An Introduction to Dynamic Generative Networks: Minimum Cost Flow. Applied Mathematical Modelling, 35(10), 5017-5025. [DOI:10.1016/j.apm.2011.04.009]
29. Nasrabadi, E., & Hashemi, S. (2010). Minimum Cost Time-Varying Network Flow Problems. Optimization Methods and Software, 25(3), 429-447. [DOI:10.1080/10556780903239121]
30. Ciurea, E., & Parpalea, M. (2010). Minimum Flow in Monotone Parametric Bipartite Networks. NAUN International Journal of Computers, 4(4), 124-135.
31. Fonoberova, M. (2010). Algorithms for Finding Optimal Flows in Dynamic Networks. S. Rebennack et al. (eds.), Handbook of Power Systems II, Energy Systems, Springer-Verlag Berlin Heidelberg. [DOI:10.1007/978-3-642-12686-4_2]
32. El-Sherbenym, N. (2012). A New Class of a Minimum Cost Flow Problem on a Time Varying and Time Window. Scientific Research and Impact, 1(3), 18-28.
33. Salehi Fathabadi, H., Khodayifar, S., & Raayatpanah, M. (2012). Minimum flow Problem on network flows with time-varying bounds. Applied Mathematical Modeling, 36(9), 4414-4421. [DOI:10.1016/j.apm.2011.11.067]
34. Rashidi, H., & Tsang, E. (2005). Applying the Extended Network Simplex Algorithm and a Greedy Search Method to Automated Guided Vehicle Scheduling. the 2nd Multidisciplinary International Conference on Scheduling: Theory & Applications (MISTA). New York, p. 677-693.
35. Grunow, M., Gunther, H., & Lehmann, M. (2004). Dispatching multi-load AVGs in highly automated seaport vontainer terminals. OR Spectrum, 26(2), 211-235. [DOI:10.1007/s00291-003-0147-1]
36. Murty, K., Jiyin, L., Yat-Wah, W., Zhang, C., Maria, C., Tsang, J., & Richard, L. (2002). A Decision Support System for operations in a container terminal. Decision Support System, 39, 309-332. [DOI:10.1016/j.dss.2003.11.002]
37. Huang, Y., & Hsu, W. (2002). Two Equivalent Integer Programming Models for Dispatching Vehicles at a Container Terminal. Report No. 639798, Nan yang Technological University, School of Computer Engineering.
38. Cheng, Y., Sen, H., Natarajan, K., Ceo, T., & Tan, K. (2003). Dispatching Automated Guided Vehicles in A Container Terminal. Technical Report, National University of Singapore.
39. Patrick, J., & Wagelmans, P. (2001). Dynamic Scheduling of Handling Equipment at Automated Container Terminals. Report No. EI 2001-33, Erasmus University of Rotterdam, Econometric Institute.
40. Bose, J., Reiners, T., Steenken, D., & Vob, S. (2000). Vehicle Dispatching at Seaport Container Terminals Using Evolutionary Algorithms. In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii, p. 1-10. [DOI:10.1109/HICSS.2000.926669]
41. Rashidi, H., & Tsang, E. (2011). A Complete and an Incomplete Algorithm for Automated Guided Vehicle Scheduling in Container Terminals. Journal of Computers and Mathematics with Applications, 61, 630-641. [DOI:10.1016/j.camwa.2010.12.009]
42. Rashidi, H. (2006). Dynamic Scheduling of Automated Guided Vehicles in Container Terminals (Doctoral dissertation).University of Essex, Colchester.
43. Rashidi H., Tsang E. (2016). Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, Second Edition. CRC Press, New York.
Send email to the article author

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Creative Commons License
International Journal of Maritime Technology is licensed under a

Creative Commons Attribution-NonCommercial 4.0 International License.