پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 45 |
| تعداد شماره‌ها | 1,219 |
| تعداد مقالات | 10,473 |
| تعداد مشاهده مقاله | 20,217,838 |
| تعداد دریافت فایل اصل مقاله | 13,905,750 |
Optimizing the Static and Dynamic Scheduling problem of Automated Guided Vehicles in Container Terminals | ||
| Control and Optimization in Applied Mathematics | ||
| مقاله 6، دوره 2، شماره 2، اسفند 2017، صفحه 77-101 اصل مقاله (1.07 M) | ||
| نوع مقاله: Applied Article | ||
| نویسنده | ||
| Hassan Rashidi* | ||
| Department of Mathematics and Computer Science, Allameh Tabataba’i University, Tehran, Iran, | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| Network Simplex Algorithm؛ Dynamic Network Simplex Algorithm؛ Optimization Methods؛ Dynamic Scheduling؛ Container Terminals | ||
| عنوان مقاله [English] | ||
| زمان بندی بهینه ایستا و پویای وسایل نقلیه هدایت خودکار در بنادر کانتینری | ||
| نویسندگان [English] | ||
| حسن رشیدی | ||
| دانشیار دانشکده علوم ریاضی و رایانه، ایران، تهران، دانشگاه علامه طباطبائی | ||
| چکیده [English] | ||
| امروزه، استفاده از وسایل نقلیه راهنمایی خودکار (AGV) برای حمل و نقل کانتینرها در بنادر و سیستم‌های تولید انعطاف‌پذیری، مورد توجه بیشتری قرار گرفته است. این وسایل بدون راننده و تحت کنترل کامپیوتر کار می‌کنند. یکی از چالش‌های این وسایل، زمانبندی وسیله نقلیه با محدودیت‌هایی در زمان رسیدن و تحویل کانتینرها به نقطه خاصی از اسکله است. این نوع مساله اغلب به عنوان مدل حداقل هزینه جریان (MCF)، که یکی از شناخته شده‌ترین مدل‌ها در زمینه برنامه‌ریزی شبکه است، فرموله می‌گردد. برای حل این مدل، الگوریتم سیمپلکس شبکه(NSA) سریع‌ترین راه حل است. NSA دارای سه انشعاب، شامل الگوریتم سیمپلکس شبکه ارتقاء یافته (NSA+)، الگوریتم سیمپکس شبکه پویا (DNSA) و الگوریتم سیمپلکس شبکه پویای ارتقاء یافته (DNSA+) است. NSA و NSA+ از ابتدا، بدون بازبینی راه حل‌های پیشین، آغاز به کار می‌کند. DNSA و DNSA+، به جای آغاز عملیات از ابتدا، راه حل‌های پیشین را ترمیم می‌کنند. اهداف این تحقیق، شبیه‌سازی و همچنین بررسی مزایا و معایب NSA در مقایسه با سه انشعاب آن در شرایط عملی است. برای انجام ارزیابی، استفاده از این الگوریتم‌ها برای حل مساله زمانبندی وسایل نقلیه راهنمایی خودکار در بنادر کانتینری مورد آزمایش قرار گرفته شده است. در آزمایشات، تعداد تکرارها، زمان CPU مورد نیاز برای حل مسائل، سربار و پیچیدگی در نظر گرفته شده است. نتایج تجربی بدست آمده نشان می‌دهد مزیت اصلی الگوریتم‌های پویا در مقایسه با NSA و NSA+، عملکرد آنها می‌باشد. | ||
| کلیدواژه‌ها [English] | ||
| الگوریتم سیمپلکس شبکه, الگوریتم سیمپلکس شبکه ارتقاء یافته, الگوریتم سیمپلکس شبکه پویا, بنادر کانتینری | ||
| مراجع | ||
|
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. | ||
|
آمار تعداد مشاهده مقاله: 594 تعداد دریافت فایل اصل مقاله: 462 |
||