کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4959449 1364862 2018 16 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm
ترجمه فارسی عنوان
حل مشکلات پیش صورت برداری کانتینر با اندازه واقعی در دنیای واقعی با یک الگوریتم شاخه و حد
کلمات کلیدی
OR در صنعت دریایی؛ پیش تدارکات کانتینر؛ عملیات ترمینال؛
OR in maritime industry; Container pre-marshalling; Terminal operations;
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی

•A new exact algorithm for the container pre-marshalling problem that solves real-world sized problems.•Tightened lower bound procedure improving on the bound from Bortfeldt and Forster.•An effective heuristic procedure for completing a partial pre-marshalling solution.•Optimal solutions for 161 previously unsolved pre-marshalling instances.

Container terminals around the world regularly re-sort the containers they store according to their retrieval times in a process called pre-marshalling, thus ensuring containers are efficiently transferred through the terminal. State-of-the-art algorithms struggle to find optimal solutions for real-world sized pre-marshalling problems. To this end, we introduce an improved exact algorithm using an iterative deepening branch and bound search, including a novel lower bound computation, a new branching heuristic, new dominance rule and a new greedy partial solution completion heuristic. Our approach finds optimal solutions for 161 more instances than the state-of-the-art algorithm on two well known, difficult pre-marshalling datasets, and solves all instances in three other datasets in just several seconds. Furthermore, we find optimal solutions for a majority of real-world sized instances, and feasible solutions with very low relaxation gaps on those instances where no optimal could be found.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 264, Issue 1, 1 January 2018, Pages 165-180
نویسندگان
, ,