مسئله مسیریابی وسیله نقلیه
تنظیم مسئله

مسئله VRP مربوط به خدمات یک شرکت حمل و نقلی است. در این مسئله، کالاها، از یک یا چند انبار که دارای مجموعه مشخصی از ناوگان وسایل نقلیه است و توسط مجموعه‌ای از رانندگان که می‌توانند در یک شبکه جاده‌ای معین حرکت کنند، به مجموعه‌ای از مشتریان، هدایت می‌شوند. در این مسئله، به دنبال مجموعه‌ای از مسیرها (S) هستیم که برای هر وسیله نقلیه، یک مسیر مجزا وجود داشته باشد که از انبار خود شروع کند و به آن ختم شود. هدف این است که تمام نیازهای مشتریان و محدودیت‌های عملیاتی برآورده شود و در عین حال، کل هزینه حمل و نقل به حداقل برسد. این هزینه می‌تواند پولی، مسافتی یا نوع دیگری باشد.
شبکه راه را می‌توان با استفاده از یک گراف توصیف کرد که در آن، یال‌ها نشان‌دهنده جاده‌ها، و رئوس، اتصالات بین آن‌ها هستند. یال‌ها ممکن است جهت‌دار یا بدون جهت باشند، زیرا ممکن است خیابان‌های یک طرفه یا هزینه‌های متفاوت در هر جهت وجود داشته باشد. به هر یال هزینه‌ای اختصاص داده می‌شود که به طور کلی طول یا زمان سفر آن است و ممکن است به نوع وسیله نقلیه بستگی داشته باشد.
برای محاسبه هزینه کل هر مسیر، باید هزینه سفر و مدت زمان سفر بین هر مشتری و انبار مشخص باشد. برای دستیابی به این هدف، گراف اصلی ما به گرافی تبدیل می‌شود که رئوس آن، مشتریان و انبار هستند و یال‌ها، جاده‌های بین آن‌ها هستند. هزینه روی هر یال، کمترین هزینه بین دو نقطه در شبکه اصلی جاده است. انجام این کار آسان است؛ زیرا حل مسائل یافتن کوتاه‌ترین مسیر نسبتاً آسان است. این فرآیند، گراف اصلی پراکنده را به یک گراف کامل تبدیل می‌کند. برای هر جفت رئوس i و j، یک یال (i,j) در گراف کامل وجود دارد که هزینه آن به صورت Cij نوشته می‌شود و به عنوان هزینه کوتاه‌ترین مسیر از i تا j تعریف می‌شود. زمان سفر tij، مجموع زمان‌های سفر یال‌ها در کوتاه‌ترین مسیر از i تا j در گراف اصلی جاده است.
گاهی اوقات برآورده کردن تمام خواسته‌های مشتری غیرممکن است و در چنین مواقعی، حل‌کننده‌ها ممکن است برخی از درخواست‌های مشتری را کاهش دهند یا برخی از مشتریان را بدون سرویس رها کنند. برای مقابله با این شرایط می‌توان یک متغیر اولویت برای هر مشتری در نظر گرفت یا جریمه‌های مربوط به خدمات جزئی یا عدم ارائه خدمات برای هر مشتری در نظر گرفت.
توسعه بهینه الگوریتم از مهمترین بخش های بهینه سازی است . از دیگر روش های بهینه سازی مسئله VRP را می توان از طریق GA یا الگوریتم ژنتیک که به الگوریتم تکامل تدریجی نیز شناخته می شود نام برد . روش حل بهینه سازی مسیر در این الگوریتم ها بطور خلاصه بدین شکل است که در ابتدا تعدادی راه حل یا همان Chromosome ایجاد و نقاط مختلف مانند محل های تحویل و یا انبار ها درون آن بعنوان Gene بصورت تصادفی و غیر تکراری قرار می گیرند و روی آنها محاسبات مورد نیاز انجام می شود . سپس ، تعدادی از راه حل هایی که بهتر از بقیه راه حل ها بودند را انتخاب و به مرحله بعد می روند . در مرحله بعد از کار برای تولید راه حل های جدید از همان راه حل های منتخب استفاده می کنند که در اصطلاح به آن Crossover یا تولید مثل می گویند . اینکار باعث می شود که فرزندان که همان راه حل های جدید هستند از شرایط مناسب تر والدین خود بخشی را به ارث برده و مسئله را به سمت یافتن راه حل های بهتر سوق می دهند . در مراحل بعد می توان از عملیاتی مانند Mutation یا جهش استفاده کرد . جهش باعث ایجاد تغییر ناخواسته در یک راه حل ایجاد می کند که ممکن است به بهتر شدن وضعیت و یا بدتر شدن آن بیانجامد . این فرآیند را تا زمانی که به شرایط مطلوب برسند انجام می دهند و در پایان از بهترین راه حل موجود را بعنوان جواب در نظر می گیرد .
از قابلیت هایی که می توان به الگوریتم های بهینه سازی می توان استفاده کرد را در زیر اشاره می کنیم :
استفاده از ترافیک لحظه ای برای محاسبه مدت زمان و فاصله بین دو نقطه
افزودن مدت زمان توقف برای هر نقطه
رتبه بندی مشتری ها و نقاط برای ایجاد اولویت در بهینه سازی مسیر و محاسبه زمان رسیدن
بهینه سازی چند تایی برای چند خودرو در یک عملیات
بهینه سازی برای وسیله نقلیه موتورسیکلت
بهینه سازی برای بازاریاب ها و ویزیتور های پیاده
بهینه سازی بر اساس یک نقطه شروع ثابت
و ...
با توجه به تغییرات مختلف در سطح جامعه و کشور ، حتما در توسعه بهینه الگوریتم برای رسیدن به نتایج مورد دلخواه مورد نیاز است .