بهینهسازی مسیر یعنی مرتب کردن stop ها و تخصیص وسایل نقلیه بهطوری که ناوگان کارش را با کمترین زمان، فاصله یا هزینه تمام کند. تفاوت بین راننده تحویلی است که در ساعت ۴ بعدازظهر تمام میکند و رانندهای که در ساعت ۷ شب با همان ون و همان stop ها تمام میکند. زیر هر دکمه "مسیر بهینه شد" در یک اپلیکیشن لجستیک، یک solver نشسته است که تازه میلیونها ترتیب ممکن را جویده و یکی را انتخاب کرده است.
در این راهنما توضیح میدهم بهینهسازی مسیر واقعاً چیست، solverها چطور به آن نزدیک میشوند، در دنیای واقعی کجا ظاهر میشود و کدام محدودیتها و دامها یک دمو را از محصول واقعی جدا میکنند.
بهینهسازی مسیر واقعاً چیست
در علوم کامپیوتر، بهینهسازی مسیر داخل دو مسئله کلاسیک زندگی میکند. Travelling Salesman Problem (TSP) میپرسد: با لیستی از شهرها و فواصل بینشان، کوتاهترین مسیری که هر شهر را دقیقاً یکبار بازدید میکند و به شروع برمیگردد چیست؟ این یک مسئله تکوسیلهای است. Vehicle Routing Problem (VRP) این را به یک ناوگان تعمیم میدهد: با یک depot، مجموعهای از مشتریها و چندین وسیله نقلیه، مشتریها چطور باید بین وسایل نقلیه تقسیم شوند، و هر وسیله نقلیه به چه ترتیبی باید آنها را بازدید کند؟
هر دو مسئله NP-hard هستند. تعداد ترتیبهای ممکن با تعداد stop ها به صورت فاکتوریل رشد میکند. بیست stop از قبل بیش از ۱۰ به توان ۱۸ مسیر ممکن تولید میکنند. هیچ الگوریتم دقیقی نمیتواند آن فضا را در زمان واقعی جستجو کند. پس بهینهسازی، در محصول واقعی، دربارهٔ یافتن پاسخ کامل نیست. دربارهٔ یافتن یک پاسخ خیلی خوب با سرعت کافی برای عمل کردن است.
solverها چگونه به مسئله نزدیک میشوند
چون فضای جستجو عظیم است، solver های واقعی چندین تکنیک را ترکیب میکنند.
برای مسائل کوچک (تقریباً زیر ۱۵ stop)، روشهای دقیق مثل branch-and-bound یا برنامهریزی صحیح میتوانند در چند ثانیه راهحل اثباتپذیر بهینه برگردانند. فراتر از آن مقیاس، روشهای دقیق دیگر کاربردی نیستند و این حوزه به heuristic ها سوئیچ میکند.
یک پایپلاین معمول با یک constructive heuristic مثل nearest-neighbour یا الگوریتم Clarke-Wright savings شروع میشود تا یک مسیر اولیه تولید کند. آن مسیر سپس به یک metaheuristic داده میشود، که به طور تکراری stop ها را عوض میکند، sub-tourها را برعکس میکند یا stop ها را بین وسایل نقلیه جابهجا میکند تا تابع هدف بهبود یابد. Simulated annealing، tabu search، large neighbourhood search و genetic algorithm ها رایجترین انتخابها هستند. همه شکل یکسانی دارند: یک تغییر را امتحان کن، تصمیم بگیر بپذیریش یا نه، برای یک بودجه زمانی ثابت تکرار کن.
ورودی حیاتی دیگر distance matrix است: یک جدول از پیش محاسبهشده از زمان سفر و فاصله بین هر جفت stop. optimizer در طول جستجو میلیونها بار از ماتریس کوئری میگیرد، پس ماتریس یکبار اول کار توسط یک routing engine ساخته میشود و در طول اجرای solver در حافظه نگه داشته میشود.
بهینهسازی مسیر کجا ظاهر میشود
بهینهسازی مسیر بیسروصدا فهرست بلندی از کسبوکارهای عملیاتی را قدرت میدهد.
- Last-mile delivery: حاملهای بسته، تحویل خواروبار و fulfilment ایکامرس همه دهها تا صدها stop در ون در روز ترتیب میدهند
- Field service: تکنسینهای HVAC، نصابهای مخابرات و کارگران سلامت خانگی به مشتریها در یک منطقه با پنجرههای نوبت و الزامات مهارت سر میزنند
- نیروی کار سیار: تیمهای خدمات همگانی، کنتورخوانها و بازرسها که قلمروها را با انواع وظایف مختلف پوشش میدهند
- تحویل غذا: تجمیعکنندههای رستوران چند سفارش را در یک سفر پیک batch میکنند وقتی جغرافیا اجازه میدهد
- جمعآوری زباله: کامیونهای شهرداری در دورهای هفتگی ثابت اجرا میشوند که در آن مرتبسازیهای کوچک سوخت واقعی ذخیره میکنند
- نمایندگان فروش: برنامهریزی قلمرو که در آن یک نماینده ۸ تا ۱۲ حساب در روز بازدید میکند و ترتیب برای زمان رانندگی و چگالی جلسات اهمیت دارد
در هر مورد کاربر یک لیست از stop ها را در ترتیب درست میبیند. کار در optimizer پشت آن انجام میشود.
محدودیتهایی که اهمیت دارند
یک solver که فقط فاصله را کمینه میکند یک اسباببازی است. مسیریابی محصول واقعی با محدودیتهایش تعریف میشود.
- ظرفیت وسیله نقلیه: هر ون یک محدودیت وزن، حجم یا پالت دارد که stop های تخصیصدادهشده نباید از آن فراتر روند
- پنجرههای زمانی: مشتریها انتظار تحویل بین، مثلاً، ۹ تا ۱۱ صبح را دارند، و رسیدن در ۱۱:۰۵ یک شکست است
- شیفتهای راننده: حداکثر ساعات کاری، استراحتهای اجباری و شروع و پایان در depot های مشخص
- تطابق مهارت یا وسیله نقلیه: نصب یخچال نیاز به تیم دو نفره دارد، تحویل cold-chain نیاز به ون یخچالدار دارد
- چند depot: ناوگانهای بزرگ از چندین انبار dispatch میکنند و solver تصمیم میگیرد کدام depot کدام stop را بگیرد
- بازگشت به پایگاه: برخی مسیرها باز هستند (راننده در خانه تمام میکند)، برخی بسته (راننده به depot برمیگردد)
هر محدودیت مجموعه قابل قبول مسیرها را کوچک میکند و solver را به سمت راهحلهایی هل میدهد که روی کاغذ کمی بدتر به نظر میرسند ولی در واقع قابل تحویل هستند.
دامها در محصول واقعی
بهینهسازی مسیر دستهای است که در آن دمو همیشه کار میکند و rollout اغلب نه.
بهینه کردن تابع هدف اشتباه. کمینه کردن فاصله پیشفرض است، اما برای بسیاری از ناوگانها درآمد یا انطباق با سطح خدمات بیشتر از کیلومتر صرفهجوییشده اهمیت دارد. مسیری که یک بسته اضافی را با هزینه ۲ کیلومتر میاندازد معمولاً برد است.
Free-flow در برابر زمان آگاه به ترافیک. ماتریسی که از سرعتهای خام جاده ساخته شده به شما میگوید مسیر ۴ ساعت طول میکشد در حالی که در ترافیک ساعت اوج ۶ ساعت میشود. از routing engine ای استفاده کنید که زمانهای سفر آگاه به ترافیک را برای زمانی از روز که مسیر اجرا خواهد شد در دسترس قرار میدهد.
نبود بازبرنامهریزی real-time. برنامهها لحظهای drift میکنند که راننده با ترافیک غیرمنتظره برخورد میکند، مشتری کنسل میکند یا یک stop جدید میآید. تیمهای عملیات نیاز به راهی دارند که stop های باقیمانده را در میانه روز دوباره بهینه کنند بدون دور انداختن کار صبح.
کهنگی برنامه فریزشده. یک مسیر هفتگی ثابت در ژانویه بهینه به نظر میرسید و الان ۲۰ درصد بدتر است چون مشتریها جابهجا شدند، حجمها تغییر کرد و یک خیابان یکطرفه ظاهر شد. بهینهسازی را به طور دورهای دوباره اجرا کنید و برنامه جدید را با برنامه زنده مقایسه کنید قبل از اینکه تغییر را به رانندگان تحمیل کنید.
بهینهسازی مسیر در MapAtlas
MapAtlas Optimize Route API مسائل مسیریابی تکوسیلهای و ناوگان را با محدودیتهایی که تیمهای عملیات واقعاً نیاز دارند حل میکند: ظرفیت، پنجرههای زمانی، شیفتها، مهارتها و چیدمانهای چند depot. یک برنامه ترتیبی به ازای هر وسیله نقلیه بههمراه زمانهای ورود و خروج پیشبینیشده برای هر stop برمیگرداند.
به طور طبیعی با دو endpoint دیگر در stack مپاطلس جفت میشود. Distance Matrix API جدول زمان سفری را که solver مصرف میکند میسازد، با زمانهای آگاه به ترافیک تا برنامهها در ساعت اوج دوام بیاورند. Directions API مسیرهای جادهای پیچ به پیچ واقعی را بین stop های متوالی رسم میکند بعد از اینکه ترتیب ثابت شد، تا یک اپ راننده بتواند یک polyline واقعی نشان دهد نه یک خط مستقیم.
بهینهسازی مسیر در یک slide deck جذاب به نظر نمیرسد. یک solver، یک ماتریس و یک لیست از محدودیتهاست. اما لایهای است که تصمیم میگیرد آیا یک ناوگان روزش را به موقع و در بودجه تمام میکند، و درست به دست آوردنش همان چیزی است که یک قابلیت مسیریابی که ship میشود را از قابلیتی که بیسروصدا خاموش میشود متمایز میکند.
سوالات متداول
بهینهسازی مسیر چیست؟
بهینهسازی مسیر فرآیند تصمیمگیری دربارهٔ بهترین ترتیب بازدید از مجموعهای از stop ها و، وقتی بیش از یک وسیله نقلیه درگیر است، اینکه کدام وسیله نقلیه باید کدام stop ها را بپذیرد، است. هدف کمینه کردن یک تابع هدف مثل زمان رانندگی کل، فاصله، سوخت یا هزینه است در حالی که محدودیتهای دنیای واقعی مثل ظرفیت وسیله نقلیه، شیفت راننده و پنجرههای زمانی مشتری رعایت شود. در علوم کامپیوتر در دو مسئله کلاسیک مینشیند: Travelling Salesman Problem (TSP) برای یک وسیله نقلیه و Vehicle Routing Problem (VRP) برای ناوگان.
تفاوت route planning و route optimization چیست؟
Route planning به سؤال 'چطور از A به B بروم' پاسخ میدهد. یک مسیر واحد بین دو نقطه برمیگرداند، معمولاً با راهنمای پیچ به پیچ. Route optimization به 'این ۸۰ stop را با این ۶ ون به چه ترتیبی بازدید کنم و کدام ون کدام stop را بگیرد' پاسخ میدهد. Optimization یک لایه بالاتر از planning قرار میگیرد: ترتیب و تخصیص را تصمیم میگیرد، سپس یک routing engine را فراخوانی میکند تا مسیر جادهای واقعی را بین هر جفت stop رسم کند.
از چه الگوریتمهایی برای بهینهسازی مسیر استفاده میشود؟
برای مسائل کوچک (تقریباً زیر ۱۵ stop) روشهای دقیق مثل branch-and-bound یا برنامهریزی صحیح میتوانند راهحل اثباتپذیر بهینه پیدا کنند. فراتر از آن، فضای جستجو منفجر میشود و سیستمهای واقعی از heuristic ها و metaheuristic ها استفاده میکنند: nearest-neighbour و الگوریتمهای savings برای راهحل اولیه، سپس local search، simulated annealing، tabu search یا genetic algorithm ها برای بهبود آن. بیشتر solver های تجاری چندتای اینها را ترکیب میکنند و برای یک بودجه زمانی ثابت اجرا میشوند نه تا بهینه اثباتپذیر.
یک API بهینهسازی مسیر چه ورودیهایی نیاز دارد؟
حداقل: لیست stop ها با مختصات، وسایل نقلیه با موقعیتهای شروع و پایان، و یک ماتریس فاصله یا زمان بین هر جفت stop. در عمل ظرفیت وسایل نقلیه، پنجرههای زمانی مشتری، مدت سرویس در هر stop، ساعات شیفت راننده، مهارتها یا انواع وسیله نقلیه مورد نیاز در هر stop، و مکانهای depot را هم وارد میکنید. ماتریس سنگینترین ورودی است و معمولاً قبل از اجرای optimizer توسط یک distance matrix API جداگانه تولید میشود.
