Document Type : Applied Article
Author
Department of Mathematics and Computer Science, Allameh Tabataba’i University, Tehran, Iran,
Abstract
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
Main Subjects
bibitem{1}
Afshari Rad, M., & Taghizadeh Kakhki, H. (2013). textit{ Maximum Dynamic Network Flow Interdiction Problem: New Formulation and Sfigolution Procedures Original Research Article. Computers & Industrial Engineering}, 65(4), 531-536. DOI: 10.1016/j.cie.2013.04.014
bibitem{2}
Ahuja, R., Magnanti, T., & Orlin, J. (1993). {em Network Flows: Theory, Algorithms and Applications.} Prentice Hall.
bibitem{3}
Aronson, J. (1989). {em A Survey of Dynamic Network Flows.} Annal of Operation research, 20, 1-66. doi:10.1007/BF02216922
bibitem{4}
Bose, J., Reiners, T., Steenken, D., & Vob, S. (2000). textit{Vehicle Dispatching at Seaport Container Terminals Using Evolutionary Algorithms. } In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii (pp. 1-10).
bibitem{5}
Bradley, G., Brown, G., & Graves, G. (1977). {em Design and Implementation of Large Scale Primal Transshipment Algorithms.} Management Science, 24, 1-38. doi:10.1287/mnsc.24.1.1.
bibitem{6}
Chan, S. (2001). {em Dynamic AGV-Container Job Deployment(Master degree dissertation).} University of Singapore, Singapore MIT Alliance.
bibitem{7}
Chawla V.K., Chandab A.k. Angra S., (2018), textit{Scheduling Of Multi Load AGVs In FMS By Modified Memetic Particle Swarm Optimization Algorithm,} Journal Of Project Management, Vol. 3 , 39--54
bibitem{8}
Cheng, Y., Sen, H., Natarajan, K., Ceo, T., & Tan, K. (2003). {em Dispatching Automated Guided Vehicles in A Container Terminal.Technical Report, National University of Singapore.}
bibitem{9}
Ciurea, E., & Parpalea, M. (2010). textit{Minimum Flow in Monotone Parametric Bipartite Networks.} NAUN International Journal of Computers, 4(4), 124-135.
bibitem{10}
Cunningham, W. (1979). textit{Theoretical properties of the network simplex method.} Mathematics of Operations research, 4(2), 196-208. doi:10.1287/moor.4.2.196
bibitem{11}
El-Sherbenym, N. (2012). {em A New Class of a Minimum Cost Flow Problem on a Time Varying and Time Window.} Scientific Research and Impact, 1(3), 18-28.
bibitem{12}
Eppstein, D. (1999). textit{Clustering for faster network simplex pivots. }In Proceedings of the 5th ACM-SIAM Symposium, Discrete Algorithms. (pp. 160-166).
bibitem{13}
Rebennack, S., Pardalos, P., Pereira, M., & Iliadis, N. (Eds.). (2010). {em Algorithms for Finding Optimal Flows in Dynamic Networks. Berlin: Springer.}
bibitem{14}
Fonoberova, M., & Lozovanu, D. (2007). textit{Optimal Dynamic Flows in Networks and Applications.} The International Symposium the Issues of Calculation Optimization, Communications.Crimea, Ukraine (pp. 292-293).
bibitem{15}
Geranis, G. (2013). {em Dynamic Trees in Exterior-Point Simplex Type Algorithms for Network Flow Problems.} Electronic Notes in Discrete Mathematics, 41, 93-100.
bibitem{16}
Geranis, G., Paparrizos, K., & Sifaleras, A. (2012). textit{On a Dual Network Exterior Point Simplex Type Algorithm and Its Computational Behavior. Operations Research,} 46, 211-234. doi:10.1051/ro/2012015.
bibitem{17}
Goldberg, A., & Kennedy, R. (1993). {em An efficient cost scaling algorithm for the assignment problem.}Technical Report, Stanford University.
bibitem{18}
Grigoriadis, M. (1986). textit{ An Efficient Implementation of the Network Simplex Method.} Mathematical Programming Study, 26, 83-111.
bibitem{19}
Grunow, M., Gunther, H., & Lehmann, M. (2004). {em Dispatching multi-load AVGs in highly automated seaport vontainer terminals.} OR Spectrum, 26(2), 211-235. doi:10.1007/s00291-003-0147-1.
bibitem{20}
Hoppe, B. (1995). {em Efficient Dynamic Network Flow Algorithms(Doctoral dissertation). Cornell University, New York.}
bibitem{21}
Hosseini, S. (2010). textit{An Introduction to Dynamic Generative Networks: Minimum Cost Flow. Applied Mathematical Modelling,} 35(10), 5017-5025. DOI: 10.1016/j.apm.2011.04.009.
bibitem{22}
Hosseini A., Sahlin T., (2018), textit{An Optimization Model for Management of Empty Containers in Distribution Network of a Logistics Company Under Uncertainty,} Journal of Industrial Engineering International (2018), PP. 1-8, https://doi.org/10.1007/s40092-018-0286-2.
bibitem{23}
Huang, Y., & Hsu, W. (2002). textit{Two Equivalent Integer Programming Models for Dispatching Vehicles at a Container Terminal.} Report No. 639798, Nan yang Technological University, School of Computer Engineering.
bibitem{24}
Kelly, D., & ONeill, G. (1993). {em The Minimum Cost Flow Problem and The Network Simplex Solution Method (Master degree dissertation).} University College, Dublin.
bibitem{25}
Leong, C. (2001). {em Simulation Study of Dynamic AGV-Container Job Deployment Scheme (Master degree dissertation).} National University of Singapore, Singapore.
bibitem{26}
Lobel, A. (2000). textit{ A Network Simplex Implementation.Technical Report,} Konrad-Zuse-ZentrumfurInformationstechnik Berlin (ZIB).
bibitem{27}
Maros, I. (2003). textit{ A General Pricing Scheme for the Simplex Method.}Technical Report, London, Department of Computing, Imperial College.
bibitem{28}
Mulvey, J. (1978). textit{Pivot Strategies for Primal Simplex Network Codes.} Association for Computing Machinery Journal, 25, 266-270. doi:10.1145/322063.322070.
bibitem{29}
Murty, K., Jiyin, L., Yat-Wah, W., Zhang, C., Maria, C., Tsang, J., & Richard, L. (2002). textit{A Decision Support System for operations in a container terminal.} Decision Support System, 39, 309-332.
bibitem{30}
Nasrabadi, E., & Hashemi, S. (2010). {em Minimum Cost Time-Varying Network Flow Problems.} Optimization Methods and Software, 25(3), 429-447. doi:10.1080/10556780903239121.
bibitem{31}
Nicoleta A., Eleonora C., Mirceab P. (2017). {em The Maximum Parametric Flow in Discrete-time Dynamic Networks,} Fundamenta Informaticae, Vol. 156(2), pp. 125-139.
bibitem{32}
Parpalea, M. (2011). A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem. Open Journal of Discre Mathematics, 1eqref{GrindEQ__3_}, 116-126. doi:10.4236/ojdm.2011.13015.
bibitem{33}
Parpalea, M., & Ciurea, E. (2011). textit{Maximum Flow of Minimum Bi-Criteria Cost in Dynamic Networks.} Recent researches in computer science, 118-123.
bibitem{34}
Parpalea, M., & Ciurea, E. (2011). {em The Quickest Maximum Dynamic Flow of Minimum Cost}. Journal of Applied Mathematics and Informatics, 5(3), 266-274.
bibitem{35}
Parpalea M., Avesalon N., Eleonor Ciurea (2015), {em Minimum parametric flow over time,} Discrete Mathematics and Theoretical Computer Science, In Press.
bibitem{36}
Patrick, J., & Wagelmans, P. (2001). textit{Dynamic Scheduling of Handling Equipment at Automated Container Terminals.} Report No. EI 2001-33, Erasmus University of Rotterdam, Econometric Institute.
bibitem{37}
Patrick, J., & Wagelmans, P. (2001). {em Effective Algorithms for Integrated Scheduling of Handling Equipment at Automated Container Terminals.} Report No. EI 2001-19, Erasmus University of Rotterdam, Econometric Institute.
bibitem{38}
Powell, W., Jaillet, P., & Odoni, A. (1995). {em Stochastic and Dynamic Networks and Routing.} Handbooks in Operations Research and Management Science (pp. 141-295). Amsterdam: North-Holland.
bibitem{39}
Rashidi, H. (2006). {em Dynamic Scheduling of Automated Guided Vehicles in Container Terminals (Doctoral dissertation).} University of Essex, Colchester.
bibitem{40}
Rashidi, H. (2014). textit{A Dynamic Version for the Network Simplex Algorithm}. Journal of Applied Soft Computing, 24, 414-422. doi:10.1016/j.asoc.2014.07.017.
bibitem{41}
Rashidi, H., & Tsang, E. (2005). {em 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 (pp. 677-693).
bibitem{42}
Rashidi, H., & Tsang, E. (2011). textit{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.
bibitem{43}
Rashidi H., Tsang E., (2016). {em Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, Second Edition.} CRC Press, New York.
bibitem{44}
Ratliff, H., Sicilia, G., & Lubore, S. (1975). {em Finding the n most vital links in flow networks. Management Science}, 21, 531-539. doi:10.1287/mnsc.21.5.531.
bibitem{45}
Rauch, M. (1992). {em Fully Dynamic Graph Algorithms and Their Data Structures (Doctoral dissertation).} Princeton University, New Jersey.
bibitem{46}
Salehi Fathabadi, H., Khodayifar, S., & Raayatpanah, M. (2012). textit{ 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
bibitem{47}
Sen, H. (2001). {em Dynamic AVG-Container Job Deployment.} Technical Report, Singapore-MIT Alliance.
bibitem{48}
Shen, W., Nie, Y., & Zhang, H. (2007). textit{A Dynamic Network Simplex Method for Designing Emergency Evacuation Plans.} Transportation Research Record, 20(22), 83-93.
bibitem{49}
Skutella, M. (2009). {em An Introduction to Network Flows Over Time.} Research Trends in Combinatorial Optimization, Berlin: Springer.
bibitem{50}
Wook, B., & Hwan, K. (2000). textit{A pooled dispatching strategy for automated guided vehicles in port container terminals. }International Journal of Management Science, 6(2), 47-60.
bibitem{51}
Zheng, H., & Chiu, Y. (2011). textit{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.
)