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

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

کلیدواژه ها:

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