The lockmaster's problem

آبراه های داخلی یک زیرساخت شبکه طبیعی با ظرفیت برای ترافیک بیشتر را تشکیل می دهند. حمل و نقل توسط کشتی به طور گسترده ای ترویج می شود، زیرا این روش قابل اعتماد، کارآمد و محیط زیست دوستانه است. با این وجود، قفل های مدیریت سطح آب در آبراه ها و در داخل بندرگاه گاهی اوقات تنگناها را برای حمل و نقل بیش از آب تشکیل می دهند. مشکل قفل ساز مربوط به استراتژی بهینه برای اجرای چنین قفل است. در مسئله قفل ساز، ما یک قفل، مجموعه ای از کشتی های با دامنه بالادستی و مجموعه ای دیگر از کشتی هایی که در جهت مخالف حرکت می کنند، داده می شود. ما زمان ورود کشتی ها و زمان قفل ثابت داده می شود؛ هدف این است که کل زمان انتظار کشتی را به حداقل برسانیم. در این مقاله، یک الگوریتم برنامه ریزی پویا ارائه شده است که مشکل قفل ساز را در زمان چندجملهای حل می کند. این الگوریتم همچنین می تواند برای حل مساله برنامه ریزی یک باربندی موثر تر از الگوریتم های فعلی از ادبیات استفاده شود. ما الگوریتم را گسترش می دهیم به طوری که می توان آن را در تنظیمات واقع بینانه، با توجه به ظرفیت، زمان بارگیری وابسته به کشتی، وزن و استفاده از آب اعمال کرد. علاوه بر این، ما عملکرد این الگوریتم دقیق جدید را با عملکرد برخی از اکتشافی (ساده) در یک مطالعه محاسباتی مقایسه می کنیم.