مسأله مسیریابی

هر مسأله که بدنبال تولید یک تور یا مجموعه‌ای از تورها بر روی یک شبکه یا زیر‌شبکه با هدف بهینه ساختن یک یا چند تابع هدف می‌باشد را مسأله مسیریابی گویند. تمامی این مسائل به نوعی یک حالت خاص از مسأله فروشنده دوره‌گرد به شمار می‌روند. در حقیقت با بهره گرفتن از این مسأله بدنبال مدل‌سازی موارد حقیقی هستیم (تاث و همکاران،2002). اجزای یک مسأله مسیریابی عبارتند از: شبکه، هزینه، تقاضا، ناوگان و اهداف.

2-3- مسأله فروشنده دوره‌گرد

مسأله فروشنده دروه‌گرد (TSP)[6] یکی از بنیادی‌ترین و مشهورترین مسائل در زمینه حمل و نقل و مسأله مسیریابی می‌باشد. در مسأله فروشنده دوره‌گرد هدف یافتن یک دور، مسیر کامل(تور) برای یک فروشنده دوره‌گرد است که در آن تمامی شهرها (مشتریان) با کمترین هزینه ممکن ملاقات شوند و فروشنده از هر کدام تنها و تنها یک بار عبور نماید، سپس این تور در همان شهر اولیه که سفر از آنجا آغاز شده بود پایان یابد (تاث و همکاران،2002).

حال اگر همین مسأله را با چند فروشنده در نظر بگیریم، مسأله ما تبدیل به مسأله چندین فروشنده دوره گرد (MTSP) خواهد شد که در واقع چند فروشنده از یک شهر حرکت کرده و از ملاقات چندین شهر دوباره به همان شهر اولیه باز می‌گردند. در این حالت نیز هر کدام از شهرها باید فقط یکبار مورد ملاقات قرار گیرند (تاث و ویگو،2002).

حال اگر پیچیدگی‌های دنیای واقعی در نظر گرفته شود در عمل با مسائل گسترده‌تری مواجه هستیم که از آن جمله می‌توان به مسائل مسیریابی وسایل نقلیهVRP  اشاره کنیم که در واقع تعمیم مسائل فروشنده دوره گرد TSP، مسأله چندگانه فروشنده دوره گرد MTSP می‌باشد با این تفاوت که در مسأله مسیریابی وسایل نقلیه مایک مبدأ مشخص داریم و برخلاف مسأله چندگانه فروشنده دوره‌گرد ظرفیت وسایل نقلیه بی‌نهایت نیست و همچنین در VRP مشتریان مشخص با میزان تقاضای مشخصی وجود دارد. در اینگونه مسائل هدف این است که تقاضای تمامی مشتریان تأمین شود و هزینه کل مسیر شامل هزینه وسایل نقلیه کمینه شود. بنابراین توضیحات مشخص می‌شود که بنیان مسأله مسیریابی وسایل نقلیه TSP و به طور دقیق تر بر MTSP استوار است. در شکل زیر نمایی از مسأله مسیریابی وسایل نقلیه VRP نشان داده شده است در این شکل qها  میزان تقاضای مشتریان بوده و فلش‌های مسیر خودروهای مختلفی را نشان می‌دهند که از انبار مرکزی حرکت کرده و پس از سرویس‌دهی به آن باز می‌گردند.

Network

Cost

Demand

Fleet

Cost

Traveling Salesman Problem(TSP)

Multi Traveling Salesman Problem

 Vehicle Routing Problem