مسیریابی وسایل نقلیه/کاربرد

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

کاربرد مساله vrp[ویرایش]

موضوع مسیریابی وسیله‌نقلیه، یکی از مفاهیم آشنا در زمینه تحقیق در عملیات است که در دو دهه اخیر تلاش‌ها و به دنبال آن پیشرفت‌های بزرگی در این زمینه انجام گرفته است. مسأله مسیریابی وسایل نقلیه به مجموعه‌ای از مسائل اطلاق می‌شود که در آن ناوگانی متشکل از چندین وسیله نقلیه از یک یا چند انبار به ارائه خدمت به مشتریان مستقر در نقاط مختلف جغرافیایی می­پردازند و این امر را به نحوی انجام می‌دهند که هزینه‌های انجام این کار به حداقل برسد. در طول این مسیرها مشتریان تنها و تنها یک بار ملاقات می‌شوند و تمام تقاضاهای آنها تنها توسط یک وسیله نقلیه دریافت می‌گردد، هر وسیله دارای ظرفیت معینی است و از سویی تمام مسیرها از یک نقطه مشخص (مبدأ بارگیری) آغاز می‌شوند و پس از آنکه وسیله نقلیه یک سلسله از مشتریان را ملاقات نمود به همان نقطه اولیه باز می‌گردد و مسیر در همان مکان پایان می‌یابد. این‌گونه مسائل به طور کلی به عنوان مسائل مسیریابی وسایل نقلیه ( VRP) یا مسائل برنامه‌ریزی حمل‌ونقل، شناخته شده‌اند. مدل‌ها و الگوریتم‌های معرفی شده برای حل مسائل برنامه‌ریزی و مسیریابی ارائه شده را، نه تنها برای استفاده در مسائل مربوط به پخش و جمع‌آوری کالاها بلکه برای بسیاری از مسائل مختلف صنعت حمل‌ونقل در دنیای واقعی، نیز می‌توان استفاده نمود و به طور عمده مورد استفاده از این دست مسائل به عنوان مثال، در جمع‌آوری زباله‌های خشک، پاکیزه سازی خیابان‌ها، مسیریابی اتوبوس مدرسه، سیستم‌های جابه‌جایی معلولین، مسیریابی فروشنده دوره‌گرد و واحدهای نگهداری و تعمیرات می‌باشد. پخش کالاها در برگیرنده خدمت‌دهی به دسته‌ای از مشتریان، در یک بازه زمانی داده شده توسط دسته‌ایی از وسایل‌نقلیه می‌شود که در یک یا چند مرکز قرار دادند و توسط دسته‌ایی از رانندگان هدایت می‌شوند و جابجایی‌ها در یک شبکه مسیر مناسب انجام می‌شود[۱].

مسیریابی وسایل نقلیه (VRP) نامی کلی است که به تمامی کلاس‌ مسائلی که شامل ملاقات مشتری‌ها با خودروهاست، اطلاق می‌شود. VRP در نوشته‌ها، به‌صورت زمان‌بندی خودروها و توزیع خودرو یا به‌طور ساده‌تر به صورت مسئله تحویل نیز شناخته شده است

VPR در حالت‌های کاربردی که در برخی موارد حتی مستقیما با توزیع فیزیکی کالاها مرتبط نیستند، بسیار به تناوب ظاهر می‌شود. سوارکردن کودکان به اتوبوس‌های مدرسه، تحویل تولیدات بین سوپرمارکت‌ها و فروشگاه‌های بزرگ، توزیع روزنامه، تورهای بازرسی و تعمیر بازدارنده، توزیع لباسشویی و غیره، همگی VRPهایی هستند که در آن، کالاها و خودروها می‌توانند فرم‌های متنوعی بگیرند.

اغلب مسائل مسیریابی خودرو، NP-hard هستند و به نظر می‌رسد که قابل حل در زمانی چندجمله‌ای نباشند. الگوریتم‌های تحقیقاتی ارائه شده برای VRP عموماً شامل روش‌های دقیق و الگوریتم‌های بهینه‌سازی هوشمند است. الگوریتم‌های دقیق شامل روش‌های شاخه و کران، متدهای برنامه‌ریزی پویا و مانند اینها هستند. مثلا، Nobert روش‌های پیشرو شاخه و کران چندگانه پیشرو را ابداع کرد. در مقابل، الگوریتم‌های تقریبی عمدتاً شامل روش‌های جست‌وجوی ممنوع و شبیه‌سازی حرارتی ، الگوریتم‌های ژنتیک بهینه‌سازی مورچگان و غیره است. در بسیاری از سیستم های خدماتی نظیر حمل و نقل مسافران و سرویس های خدماتی تعمیرات و نگهداری، مشتریان می بایستی توسط مجموعهای از وسایل نقلیه سرویس دهی شوند. این ناوگان حمل و نقل در یک مکان استقرار یافته اند. هدف پیدا کردن مجموعه ای از مسیرها می باشد به گونه ای که مجموعه ای از محدودیت ها را ارضا کند و کل مسیر طی شده توسط وسایل نقلیه و سایر هزینه ها کمینه شود. این مساله، مساله مسیریابی وسیله نقلیه نام گذاری شده و دربسیاری از مجلات معتبر علمی به صورت گسترده مورد تجزیه و تحلیل قرار گرفته است. هدف از مساله VRP در شرایط کلاسیک، کمینه سازی کل مسافت طی شده توسط وسایل نقلیه، کاهش حجم ناوگان، کمینه سازی جریمه های دیرکرد یا زودکرد سرویس دهی و در نهایت افزایش رضایت مشتریان است. مساله مسیریابی وسایل نقلیه در واقع توسعه ای از مسئله معروف فروشنده دوره گرد بوده است. از همان سالهای اولیه معرفی این مسئله توسعه های زیادی بر روی این موضوع شروع به شکل گرفتن گرفت. این مسئله با توجه به اهمیت بالایی که به بحث زمان درحل مسایل می دهد در عمل از کاربرد بیشتری برخوردار بوده و لذا توجه بیشتری را در محافل علمی به خود اختصاص داده است. [۲].

در حالت خاص می توان جواب حاصل از مساله مسیریابی را به صورت زیر بیان نمود:

تعیین مجموعه ای از مسیرها که هر کدام توسط یک وسیله نقلیه مورد استفاده قرار میگیرند (البته وسایل نقلیه از مراکز توزیعی که اعزام میشوند در نهایت به همان مرکز توزیع نیز بر می گردند)، به نحوی کوه نیاز مشتری برآورده شود و تمام محدودیت های عملیاتی نیز ارضا شده و نتیجه به حداقل شدن هزینه کل منجر شود.

منابع[ویرایش]

  1. مسیریابی و سیستم های VRP
  2. مسیریابی وسایل نقلیه (VRP)