بذارید یه کم براتون از یه روش جدید و باحال بگم که اومده واسه حل یکی از بزرگترین چالش‌های دنیای لجستیک – یعنی همون “مسئله مسیر‌یابی وسایل نقلیه با ظرفیت محدود” (Capacitated Vehicle Routing Problem یا همون CVRP) – یه راه حل سریع‌تر و باحال‌تر پیدا کنه!
اول یه توضیح: مسئله CVRP چیه؟ فرض کنید یه عالمه مشتری دارین که باید براشون با ماشین باری جنس بفرستین، هر ماشین هم یه ظرفیت خاصی داره و نمی‌تونه بیشتر از اون بار بزنه داخلش. حالا سوال اینه که بهترین راه برای اینکه ماشین‌ها برن و بیان چیه که هم کل مسیرها کوتاه بشه، هم ظرفیت ماشین‌ها رعایت شه؟ این سوال خودش یکی از مسائل اصلی دنیای لجستیک و پخش بار هست.
حالا معمولاً حل این مسئله خیلی زمان‌بر و پرمحاسبه‌ست، مخصوصاً اگه مشتریا خیلی زیاد باشن (مثلاً نه فقط صدتا یا هزارتا، بلکه حتی صد هزار نفر!). خب، تو مقاله‌ای که تو arXiv به تازگی منتشر شده، نویسنده‌ها یه رویکرد جدید ارائه دادن که هم بهینه کار می‌کنه و هم از منابع سخت‌افزاری (مثل چندتا هسته پردازنده کامپیوتر) حسابی استفاده می‌بره.
داستان اینه که یه الگوریتم به اسم FILO2 قبلاً ساخته بودن که مخصوص حل این مدل مسائل در مقیاس بزرگ بود. حالا اومدن نسخه موازی یا پارالل‌ش رو درست کردن که اسمشو گذاشتن FILO2$^x$. این الگوریتم جدید این‌جوری کار می‌کنه که به جای اینکه یه دونه مسیر حل یا «trajectory» رو دنبال کنه، چندتا حل‌گر یا solver با هم همزمان رو یه راه‌حل پایه‌ای کار می‌کنن، هر کدوم دارن یه گوشه‌ای از نقشه (یا همون solution area) رو شخم می‌زنن و بهینه می‌کنن. تازه همه‌شون هم لازم نیست عین هم کار کنن یا حتی از یه نقطه شروع کنن! این یعنی الگوریتم FILO2$^x$ همزمان تو چندتا جای مختلف رو نقشه داره بهینه‌سازی انجام می‌ده.
یک نکته خیلی جالب اینه که این همکاری موازی و آسنکرون (یعنی چیزی که نیاز به هماهنگ‌سازی و توقف بین همکارا نداشته باشه)، کلی سرعت حل رو زیاد می‌کنه، اونم بدون اینکه نیاز باشه مسأله رو بخش‌بندی کنیم یا جدا جدا باهاش برخورد کنیم. برای همین بهش می‌گن parallel shared-memory schema یعنی یه روش موازی توی یه حافظه اشتراکی که نیاز به هماهنگی زیاد هم نداره.
جالب‌ترش اینه که حتی اگه الگوریتم اصلی FILO2 هم تو حالت تک‌نخی (یعنی همون حالت عادی و ساده) سرعتش خوب بود، این نسخه پیشرفته‌تر یعنی FILO2$^x$ به خاطر استفاده بهتر از منابع پردازشی می‌تونه زمان حل رو به طور خیلی جدی بیاره پایین. مثلاً تو تست‌ها نشون داده که برای مسئله‌هایی که تعداد مشتری‌هاشون از صدتا تا حتی صد هزار تا می‌رسه، کیفیت جواب (یعنی اون مسیرهای بهینه‌ای که پیدا می‌کنه) تقریباً همون‌قدر خوب می‌مونه اما سرعت جواب فوق‌العاده بهتره!
خلاصه، اگه دنبال این بودین که چطور میشه مسأله‌های خیلی بزرگ مسیر‌یابی رو سریع‌تر و با کیفیت مناسب حل کرد و منابع سخت‌افزاری رو هم بدون دردسر هماهنگی اضافه به کار گرفت، این روش جدید خیلی می‌تونه به کارتون بیاد! هر سوالی داشتی، کامنت کن تا بیشتر توضیح بدم 🙂
منبع: +
