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