یادگیری ماشین، سرعت مسیریابی وسایل نقلیه را افزایش می‌دهد

پژوهشگران MIT، از روش یادگیری ماشین افزوده برای افزایش سرعت راه‌حل‌های مسائل مربوط به مسیریابی خودرو در مجموعه‌های بزرگی از شهرها استفاده کردند.

آیا منتظر رسیدن خرید اینترنتی خود هستید؟ یک مسئله ریاضی پیچیده وجود دارد که باید قبل از رسیدن ماشین تحویل به در خانه شما حل شود و پژوهشگران MIT راهبردی دارند که می‌تواند سرعت حل این مسئله را افزایش دهد.

این روش به مسائل مسیریابی وسایل نقلیه مانند «تحویل درب منزل» اعمال می‌شود که هدف از آن تحویل محصولات از انبار مرکزی به چندین شهر، در عین پایین نگه داشتن هزینه‌های سفر است. با اینکه الگوریتم‌هایی برای حل این مشکل در صدها شهر طراحی شده‌اند، اما این راه‌حل‌ها هنگام استفاده در مجموعه بزرگ‌تری از شهرها، کند می‌شوند.

کتی وو، استادیار توسعه شغلی Gilbert W. Winslow در گروه مهندسی شهری و محیطی و مؤسسه داده، سیستم و جامعه و دانشجویان او به یک راهبرد یادگیری ماشین دست یافتند که سرعت برخی از قوی‌ترین حلگرهای الگوریتمی را 10 تا 100 برابر افزایش می‌دهد.

الگوریتم‌های حلگر مسئله تحویل را به مسئله‌های کوچک‌تر مثلاً 200 مسئله کوچک برای مسیریابی وسایل نقلیه بین 2 هزار شهر، تقسیم می‌کنند. وو و همکاران او، این فرایند تازه را به یک الگوریتم یادگیری ماشین جدید اضافه کردند که به جای حل تمام مسائل کوچک، مفیدترین مسائل را شناسایی و حل می‌کند، تا کیفیت راه‌حل را با استفاده از روش مرتبه بزرگی برای محاسبه کمتر، افزایش دهند.

پژوهشگران بیان کردند که می‌توان از روش آن‌ها که از آن با عنوان «یادگیری برای تفویض اختیار» یاد می‌کنند، در انواع گوناگونی از حلگرها و مسائل مشابه از جمله زمان‌بندی و مسیریابی ربات‌های انبار نیز استفاده کرد.

مارک کیو، بنیانگذار و مدیرعامل Routific که یک سامانه لجستیک هوشمند برای بهینه‌سازی مسیرهای تحویل است، می‌گوید: «این پژوهش، مرزهای حل سریع مسائل مسیریابی خودرو را جابه‌جا می‌کند. بعضی از جدیدترین پیشرفت‌های Routific در زمینه الگوریتم‌ها، از کار وو الهام گرفته‌اند. بیشتر پژوهش‌های دانشگاهی بر روی الگوریتم‌های تخصصی برای مسائل کوچک متمرکز هستند و سعی می‌کنند در ازای زمان پردازش بیشتر، راه‌حل‌های بهتری را پیدا کنند؛ اما در جهان واقعی، کسب‌وکارها اهمیتی به یافتن بهترین راه‌حل نمی‌دهند، به‌خصوص اگر زمان محاسبه آن‌ها بسیار طولانی باشد. در جهان «تحویل درب منزل»، زمان به‌منزله پول است و نمی‌توان تمام کار انبار خود را معطل الگوریتم‌های کند گذاشت، تا باز گردند. یک الگوریتم کاربردی، باید فوق سریع باشد.»

وو، سیروئی لی، دانشجوی دکتری سیستم‌های اجتماعی و مهندسی و ژونگشیا یان دانشجوی دکتری مهندسی برق و علوم کامپیوتر، پژوهش خود را در همایش 2021 NeurIPS  ارائه کردند.

انتخاب مسائل خوب

مسائل مسیریابی وسایل نقلیه، طبقه‌ای از مسائل ترکیبی هستند که برای پیدا کردن «راه‌حل‌های مناسبِ کافی» برای آن‌ها، مستلزم استفاده از الگوریتم‌های فراابتکاری هستند. معمولاً نمی‌توان برای این مسائل به «بهترین» پاسخ دست یافت، زیرا تعداد راه‌حل‌های ممکن بسیار زیاد است.

وو می‌گوید: «مهم‌ترین بخش این نوع مسائل، طراحی الگوریتم‌های کارآمدی است که بعضی عوامل در آن‌ها، بهینه است؛ اما هدف، پیدا کردن راه‌حل‌های بهینه نیست، زیرا این کار بسیار دشوار است. در عوض ما قصد داریم که بهترین راه‌حل‌های ممکن را بیابیم. حتی 5/0 درصد بهبود راه‌حل‌ها هم می‌تواند منجر به افزایش زیاد درآمد شرکت شود.»

طی چند دهه گذشته، محققان نوعی از الگوریتم‌های فراابتکاری را برای رسیدن فوری به راه‌حل مسائل ترکیبی، ایجاد کرده‌اند. آن‌ها معمولاً این کار را با یک راه‌حل ابتدایی ضعیف، اما معتبر آغاز می‌کنند و سپس به‌تدریج آن را ارتقا می‌دهند، مثلاً با ایجاد تغییرات کوچک برای بهبود مسیریابی بین شهرهای کوچک این کار را انجام می‌دهند. با این حال، برای مشکلات بزرگی مانند چالش مسیریابی در بیش از 2 هزار شهر، این رویکرد بسیار زمان‌بر است.

به‌تازگی، روش‌های یادگیری ماشین برای حل این مشکل توسعه یافته‌اند، اما حتی در مقیاس ده‌ها شهر نیز هرچه سرعت این روش‌ها بیشتر می‌شود، معمولاً از دقت آن‌ها کاسته می‌شود. وو و همکارانش تصمیم‌ گرفتند که به دنبال راهی سودمند برای ترکیب دو روش باشند، تا راه‌حل‌هایی سریع و با کیفیت بالا، پیدا کنند.

وو می‌گوید: «اینجاست که یادگیری ماشین به کار می‌آید. آیا می‌توان پیش‌بینی کرد که کدام یک از مسائل کوچکی که قصد حل آن‌ها را داریم، به بهبود بیشتر راه‌حل، صرفه‌جویی در زمان محاسبه و هزینه منجر می‌شوند؟»

معمولاً در روش‌های فراابتکاریِ حل مسائل کلان مسیریابی خودرو، مسائل کوچک را یا به‌صورت تصادفی یا با استفاده از یک راه‌حل فراابتکاری دیگر که به دقت طراحی شده است، انتخاب می‌کنند. در این مورد، پژوهشگران MIT مجموعه‌ای از مسائل کوچک را در یک شبکه عصبی اجرا کردند. آن‌ها این شبکه را به‌منظور یافتن خودکار مسائل کوچکی ایجاد کرده بودند که در صورت حل‌ آن‌ها، بیشترین ارتقای راه‌حل‌ها حاصل می‌شوند. وو و همکارانش دریافتند که این فرایند، سرعت انتخاب مسئله کوچک را 1.5 تا 2 برابر افزایش می‌دهد.

وو اشاره می‌کند: «ما نمی‌دانیم چرا این مسائل کوچک بهتر از دیگر مسئله‌ها هستند؛ در واقع، این امر می‌تواند موضوع پژوهشی جالبی برای آینده باشد. هر گونه اطلاعاتی در این مورد می‌تواند به طراحی الگوریتم‌های بهتری منجر شود.»

افزایش شگفت‌انگیز سرعت

وو و همکارانش از نحوه عملکرد موفق این رویکرد شگفت‌زده شدند. کیفیت رویکرد یادگیری ماشین به مقدار زیادی به کیفیت داده ورودی وابسته است. یک مسئله ترکیبی به‌قدری دشوار است که حتی مسائل کوچک آن هم به‌طور بهینه حل نمی‌شوند. به گفته وو، یک شبکه عصبی که با راه‌حل‌های مسائل کوچک با «کیفیت متوسط» آموزش دیده است، عموماً نتایج متوسطی هم ارائه می‌دهد. با این حال، در این پژوهش، محققان توانستند از راه‌حل‌های متوسط به نتایج باکیفیتی برسند که به‌طور چشمگیری از روش‌های پیشرفته سریع‌تر هستند.

برای حل مسائل مسیریابی و مسائل مشابه، کاربران اغلب باید الگوریتم‌هایی بسیار تخصصی را برای حل مسائل تخصصی خود طراحی کنند. برخی از این الگوریتم‌های فراابتکاری دهه‌ها در حال توسعه بوده‌اند.

روش یادگیری برای تفویض اختیار، فارغ از اینکه الگوریتم فراابتکاری یا مسئله بالقوه چه باشد، روش خودکاری برای افزایش سرعت الگوریتم‌های فراابتکاری در حل مسائل بزرگ ارائه می‌دهد.

وو می‌گوید: «از آنجایی که این روش می‌تواند با انواع حلگرها کار کند، احتمالاً برای انواع مسائل تخصیص منابع مفید باشد و ممکن است که کاربردهای جدیدی را اعلام کنیم که اکنون امکان‌پذیر هستند، زیرا با این روش، هزینه حل مسئله 10 تا 100 برابر کمتر است.»

انواع کاربردهای هوش مصنوعی در صنایع مختلف را در هوشیو بخوانید