مدلسازی و حل مساله مسیریابی وسیله نقلیه وابسته به زمان با پنجره‌های زمانی نیمه نرم در گراف‌های چندگانه

Abstract

مسائل مسیریابی کلاسیک عموما بگونه‌ای طراحی می‌شوند که ارتباط دو نقطه تنها از طریق یک یال یا سویه امکانپذیر است. با این حال گاهی شرایطی وجود دارد که از طریق بیش از یک یال از نقطه‌ای به نقطه دیگر می‌توان دسترسی داشت. این مقاله توسعه‌‌ای از مساله مسیریابی وسیله حمل و نقل وابسته به زمان را مورد بررسی قرار می‌دهد، که در آن امکان تخصیص بیش از یک یال یا سویه برای ارتباط نقاط مختلف میسر است. مساله مورد بررسی تحت پنجره‌های زمانی نیمه نرم برای برآورد تقاضای مشتریان مدلسازی شده است. مدل ارائه شده در این مقاله به اختصار TDVRPMSSTW نام نهاده شده است. در این مدل برای جلوگیری از مشکلات مفهومی ناشی از توابع زمان سفر گسسته، ویژگی "اولین ورودی اولین خروجی" برای تبدیل تابع سرعت سفر به تابع زمان سفر پیوسته، مورد استفاده قرار گرفته است. با توجه به NP-hard بودن مساله مورد مطالعه، یک الگوریتم جستجوی ممنوع پیشنهاد گردید. در روش ابتکاری پیشنهادی، جستجوی همسایگی بر اساس انتخاب تصادفی یکی از دو استراتژی تعویض دوتایی یا تعویض معکوس در هر تکرار انجام می‌شود. این مساله به بهبود نتایج حاصل از اجرای الگوریتم کمک می‌کند. در پایان نتایج محاسباتی الگوریتم جستجوی ممنوع و حل دقیق نرم‌افزار GAMS بر روی 40 مساله نمونه با هم مقایسه و کارایی الگوریتم پیشنهادی بر اساس کیفیت جواب و زمان حل در مقایسه با حل دقیق، نشان داده شده است.