مسیریابی وسایل نقلیه-قسمت دوم

در گزارش شماره 1 به اهمیت مسائل حمل و نقل و  جایگاه آن در انواع سیستم­ها و جایگاه مسئله مسیریابی وسایل نقلیه در این حوزه پرداخته شد. مسئله مسیریابی وسایل نقلیه اولین بار توسط دانتزیگ و رامسر در سال 1959 مطرح شد. این مسئله که حالت ترکیبی از دو مسئله فروشنده دوره­گرد )نامحدود در نظر گرفتن ظرفیت وسیله نقلیه) و بسته­بندی صندوق­ها )صفر در نظر گرفتن هزینه حمل و نقل بر روی یال­ها( است، سعی در طراحی بهینه مجموعه­ای از مسیرها برای ناوگان حمل و نقل به نحوی دارد که به تعداد معینی مشتری خدمت­رسانی شود و دارای محدودیت­های جانبی مختلفی است. شکل زیر نمونه‌ای از جواب مسئله مسیریابی وسایل نقلیه را نشان می‌دهد:

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

می توان گفت به دو علت محققان به مطالعه و بررسی گسترده مسایل موجود در زمینه مسیریابی وسایل نقلیه پرداخته و پژوهش در این حوزه همچنان ادامه دارد. یکی کاربرد عملی این مسایل و دیگری سختی حل آنهاست. لنسترا و رینوی کان در سال 1981  پیچیدگی مسایل مسیریابی وسایل نقلیه را محاسبه کرده و اثبات کردند که عملا تمامی این مسایل از نوع NP-hard هستند. مسائل مسیریابی وسایل نقلیه کاربردهای فراوانی در دنیای واقعی دارند. به عنوان مثال می‌توان به جمع‌آوری زباله‌های جامد، پخش سوخت، مسیریابی اتوبوس مدرسه، جمع‌آوری نامه‌ها از صندوق‌های پستی و یا سکه‌ها از تلفن‌های عمومی، دورهای بازرسی جهت نگهداری پیشگیرانه ماشین‌آلات و یا مسیریابی حرکت کارگران در انبارها جهت جمع‌آوری سفارشات مشتری از نواحی مختلف انبار اشاره کرد.

اجزای اصلی و پایه‌ای مسئله مسیریابی وسایل نقلیه عبارتند از شبکه مسیرها، مشتریان، انبارها، وسایل نقلیه و رانندگان. در عمل، محدودیت‌ها و شرایط مختلفی می‌تواند بر هر یک از این اجزای اصلی تحمیل شود که هر یک از آن‌ها منجر به ایجاد نوع خاصی از مسایل مسیریابی وسایل نقلیه می‌شود. به عنوان مثال، اگر مشتریان تنها در بازه زمانی خاصی قادر به دریافت سفارش خود باشند بنابراین وسیله نقلیه می‌بایست در همان بازه زمانی خاص مشتری را ملاقات کند. مسایلی با چنین محدودیت‌هایی را مسئله مسیریابی وسایل نقلیه با پنجره زمانی می‌نامند. همچنین وسایل نقلیه در نظر گرفته شده در یک مسئله می‌توانند همگی یکسان و یا با ظرفیت‌ها و هزینه‌های مختلف باشند. همان‌طور که انتظار می‌رود با توجه به تعداد زیاد این محدودیت‌ها و حالات، مسایل مسیریابی وسایل نقلیه انواع مختلفی داشته و بسیار گوناگون هستند. در ادامه دسته­بندی ارائه شده توسط بوراک و همکاران در سال 2009 آورده شده است:

ادامه این گزارشات بصورت منظم و هر هفته در وبلاگ قرار خواهد گرفت و علاقمندان به این حوزه می توانند مطالب آن را دنبال نمایند و به‌ منظور دسترسی آسان‌تر به این سلسله مطالب، از این‌ پس خوانندگان عزیز می‌توانند به مطالب نوشته شده توسط محمدرضا قطره سامانی ([e-mail]) در وبلاگ مراجعه نمایند

 .