An exact algorithm for a Vehicle-and-Driver Scheduling Problem

این مقاله یک مشکل بهینه سازی ترکیبی را ارائه می دهد که شامل تخصیص وظایف به ماشین ها و اپراتورها و توالی وظایف مربوط به هر یک است. دو پیکربندی وجود دارد تنظیمات متناوب ماشین، در حالی که اپراتورها باید در یک پیکربندی مشابه شروع و پایان دهند. علاوه بر این، ماشین آلات و اپراتور ظرفیت محدودی دارند. توالی وظایف باید تضمین کند که هر یک توسط یک دستگاه و یک اپراتور در یک زمان انجام می شود و برای به حداقل رساندن تابع هزینه کلی تعیین می شود. دو جنبه حیاتی مشکل عبارتند از نیاز به هماهنگ سازی دستگاه و اپراتور انجام هر کار، و نیاز به حداقل کردن تغییرات، که جفت کارهایی است که به وسیله ی یک ماشین انجام می شود، اما توسط اپراتورهای مختلف انجام می شود. این مشکل به عنوان مساله مسیریابی خودرو با دو نوع وسایل نقلیه و با دو انبار طراحی شده است. ما یک فرمول برنامه ریزی عدد صحیح ترکیبی را پیشنهاد می دهیم و نابرابری های معتبر را برای تقویت آرام سازی برنامه ریزی خطی پیشنهاد می کنیم. ما رویه های جداسازی برای این نابرابری ها را توصیف می کنیم و الگوریتم شاخه ای و برش را برای این مشکل طراحی می کنیم. الگوریتم بر روی مجموعه ای از نمونه های معیار آزمایش شده است که نشان می دهد قادر به حل موارد بهینه با بیش از 50 مشتری می باشد.