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

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

2-5- اجزای مسأله VRP

اجزای مسأله VRP را در شکل معمول و شناخته شده آن می‌توان به مجموعه مشتریان، مجموعه وسیله نقلیه (ناوگان حمل و نقل)، و مسیرها  تقسیم‌بندی کرد. هر یک از این اجزا دارای خصوصیاتی هستند که بعنوان فرضیات مسأله یا پارامترهای ورودی آن بایستی مورد توجه قرار گیرد. شرح این خصوصیات در زیر آورده شده است.

2-5-1- خصوصیات کلی مشتریان

مکان هر مشتری: با گره در گراف شبکه مسیرها نشان داده می‌شود. مختصات مکان مشتری در صورت لزوم برای محاسبه فاصله-زمان و یا هزینه سفر بین گره‌ها استفاده می‌شود.

1. مقدار تقاضای مشتری: معرف مقدار کالایی است که باید به مشتری تحویل داده شود، یا از محل مشتری جمع‌ آوری گردد.
2. زمان خدمت به مشتری : مدت زمانی است که وسیله نقلیه در محل مشتری برای ارائه خدمت به آن توقف می کند. زمان خدمت را می‌توان بصورت تابعی از تقاضای مشتری هم تعریف کرد.
3. مجموعه وسایل نقلیه قابل استفاده برای مشتری: زیر مجموعه ای از وسایل نقلیه است که امکان خدمت‌دهی به مشتری را دارند.
4. بازه زمانی سرویس: بازه زمانی است که خدمت‌دهی به مشتری بایستی انجام پذیرد.