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

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