دانلود رایگان مقاله رویکرد ترکیبی حل دقیق مساله گسسته و ترکیبی تخصیص اسکله

عنوان فارسی
رویکرد ترکیبی حل دقیق مساله گسسته و ترکیبی تخصیص اسکله
عنوان انگلیسی
Combinatorial approach to exactly solving discrete and hybrid berth allocation problem
صفحات مقاله فارسی
0
صفحات مقاله انگلیسی
22
سال انتشار
2016
نشریه
الزویر - Elsevier
فرمت مقاله انگلیسی
PDF
کد محصول
E2146
رشته های مرتبط با این مقاله
ریاضی
گرایش های مرتبط با این مقاله
ریاضی کاربردی
مجله
مدلسازی ریاضی کاربردی - Applied Mathematical Modelling
دانشگاه
دانشکده دریایی، دانشگاه مونته نگرو، کوتور، مونته نگرو
کلمات کلیدی
بهینه سازی ترکیبی، شاخه و حد، راه حل بهینه، مشکل تخصیص اسکله، به حداقل رساندن هزینه کل
۰.۰ (بدون امتیاز)
امتیاز دهید
چکیده

ABSTRACT


 This paper presents an exact combinatorial algorithm for solving the Discrete Berth Allocation Problem (DBAP) and the Hybrid Berth Allocation Problem (HBAP) with fixed handling times of vessels based on the original algorithm for solving combinatorial problems called Sedimentation Algorithm. We address the issues of DBAP and HBAP according to the Rashidi and Tsang model. To the best of our knowledge, the proposed algorithm is the first exact combinatorial algorithm for solving the general DBAP and HBAP based on Rashidi and Tsang model. Computational results prove the superiority of the proposed algorithms compared with the exact solvers based on the Mixed Integer Programming (MIP) models. Effi- cient C implementation enabled us to solve instances with up to 65 vessels. This resolves most of the real life problems, even in large ports.

نتیجه گیری

6. Conclusion


We considered the Discrete (minimum-cost) Berth Allocation Problem (DBAP) and Hybrid (minimum-cost) Berth Allocation Problem (HBAP) with the static arrival of vessels and fixed vessel handling times. The computational experiments performed fully justify the design and further development of Sedimentation Algorithm, the exact combinatorial approach for solving DBAP and HBAP. When combined with a simple heuristic like Estimation & Rearrange Heuristic, the algorithm can be used for instances with large number of vessels as a standalone method or as a part of some more complex heuristic or meta-heuristic approach to solving DBAP or HBAP. The most difficult problems of our test instances can be solved within the time limit of 1800 s. Actually, majority of them are solved in less than 6.65 s on average, including the cases with 30 up to 60 vessels. These results indicate that this method can be used for solving real-life medium and big size instances of BAP, depending on container port layout. The differences between the minimum and maximum solving times for a large number of vessels in the test instances indicate that Sedimentation Algorithm is worth further development. We find it especially worthwhile to investigate the possibility of solving sub-problems of DBAP or HBAP that contain conflicting vessels and then combining these partial solutions to obtain the optimal solution of the entire problem. Moreover, the generalization of the algorithm to the continuous BAP and the inclusion of crane assignment to Sedimentation Algorithm are natural avenues for further development of the algorithms presented here.


بدون دیدگاه