یکی از رایج ترین کارهای بهینه سازی، مسیریابی وسایل نقلیه است که در آن هدف یافتن بهترین مسیرها برای ناوگان وسایل نقلیه ای است که از مجموعه ای از مکان ها بازدید می کنند. معمولاً «بهترین» به معنای مسیرهایی با کمترین مسافت کل یا هزینه است. در اینجا چند نمونه از مشکلات مسیریابی آورده شده است:
- یک شرکت تحویل بسته می‌خواهد مسیرهایی را برای رانندگان تعیین کند تا آنها را تحویل بگیرند.
- یک شرکت تلویزیون کابلی می‌خواهد مسیرهایی را برای تکنسین‌ها تعیین کند تا با خدمات مسکونی تماس بگیرند.
- یک شرکت به اشتراک گذاری سواری می خواهد مسیرهایی را برای رانندگان تعیین کند تا مسافران را سوار و پیاده کنند.
معروف ترین مشکل مسیریابی، مشکل فروشنده مسافر (TSP) است: کوتاه ترین مسیر را برای فروشنده ای که نیاز به بازدید از مشتریان در مکان های مختلف دارد پیدا کنید و به نقطه شروع بازگردید. یک TSP را می توان با یک نمودار نشان داد که در آن گره ها با مکان ها مطابقت دارند و لبه ها (یا کمان ها) نشان دهنده سفر مستقیم بین مکان ها هستند. برای مثال، نمودار زیر یک TSP را تنها با چهار مکان نشان می‌دهد که دارای برچسب A، B، C و D هستند.
با محاسبه فواصل تمام مسیرهای ممکن، می‌بینید که کوتاه‌ترین مسیر ACDBA است که کل مسافت 35 + 30 + 15 + 10 = 90 .
وقتی مکان های بیشتری وجود دارد، مشکل سخت تر می شود. در مثال بالا، فقط شش مسیر وجود دارد. اما اگر ده مکان وجود داشته باشد (بدون احتساب نقطه شروع)، تعداد مسیرها 362880 است. برای 20 مکان، این تعداد به 2432902008176640000 می رسد. جستجوی جامع همه مسیرهای ممکن برای یافتن کوتاه ترین مسیر تضمین می شود، اما این از نظر محاسباتی است. غیرقابل تحمل برای همه مکان ها به جز مجموعه های کوچک. برای مسائل بزرگتر، تکنیک های بهینه سازی برای جستجوی هوشمندانه فضای راه حل و یافتن راه حل بهینه (یا نزدیک به بهینه) مورد نیاز است.
یک نسخه کلی تر از TSP مشکل مسیریابی خودرو (VRP) است که در آن چندین وسیله نقلیه وجود دارد. در بیشتر موارد، VRP ها دارای محدودیت هایی هستند: به عنوان مثال، وسایل نقلیه ممکن است ظرفیت حداکثر وزن یا حجم اقلامی را داشته باشند که می توانند حمل کنند، یا ممکن است رانندگان ملزم به بازدید از مکان ها در طول پنجره های زمانی مشخصی باشند که مشتریان درخواست می کنند.
OR-Tools می تواند انواع مختلفی از VRP ها را حل کند، از جمله موارد زیر:
- مشکل فروشنده مسافرتی ، مشکل مسیریابی کلاسیک که در آن فقط یک وسیله نقلیه وجود دارد.
- مشکل مسیریابی خودرو ، تعمیم TSP با وسایل نقلیه متعدد.
- VRP با محدودیت های ظرفیت ، که در آن وسایل نقلیه حداکثر ظرفیت را برای مواردی که می توانند حمل کنند دارند.
- VRP با پنجره های زمانی ، که در آن وسایل نقلیه باید در بازه های زمانی مشخص از مکان ها بازدید کنند.
- VRP با محدودیت منابع ، مانند فضا یا پرسنل برای بارگیری و تخلیه وسایل نقلیه در انبار (نقطه شروع مسیرها).
- VRP با بازدیدهای حذف شده ، که در آن وسایل نقلیه ملزم به بازدید از همه مکان‌ها نیستند، اما باید برای هر بازدیدی که حذف می‌شود جریمه بپردازند.
محدودیت در حل مشکلات مسیریابی وسایل نقلیه
مشکلات مسیریابی وسایل نقلیه ذاتاً غیرقابل حل هستند: مدت زمانی که برای حل آنها لازم است به طور تصاعدی با اندازه مشکل افزایش می یابد. برای مشکلات به اندازه کافی بزرگ، OR-Tools (یا هر نرم افزار مسیریابی دیگر) سال ها طول می کشد تا راه حل بهینه را پیدا کند. در نتیجه، OR-Tools گاهی اوقات راه حل هایی را برمی گرداند که خوب هستند، اما بهینه نیستند. برای یافتن راه حل بهتر، گزینه های جستجو را برای حل کننده تغییر دهید. برای مثال به تغییر استراتژی جستجو مراجعه کنید.