در سراسر کشور، صدها هزار راننده هر روز بسته‌ها و محموله‌ها را به مشتریان و کسب‌وکارها تحویل می‌دهند، که تعداد زیادی از زمان‌های کلیک به درب به طور میانگین تنها چند روز است. هماهنگ کردن یک شاهکار زنجیره تامین به این بزرگی به صورت قابل پیش بینی و به موقع یک مشکل دیرینه تحقیقات عملیاتی بوده است، جایی که محققان برای بهینه سازی مرحله نهایی مسیرهای تحویل کار می کنند. این به این دلیل است که آخرین مرحله فرآیند اغلب به دلیل ناکارآمدی‌هایی مانند فواصل طولانی بین توقف‌ها به دلیل افزایش تقاضای تجارت الکترونیک، تأخیر زمانی، ترافیک، کمبود پارکینگ، اولویت‌های تحویل مشتری یا کامیون‌های نیمه پر گران‌ترین است – ناکارآمدی، که در طول همه گیری به طور فزاینده اغراق آمیز و آشکار می شود.
با فناوری جدیدتر و داده های فردی و ظریف تر، محققان می توانند مدل هایی با گزینه های مسیریابی بهتر توسعه دهند، اما در عین حال باید هزینه محاسباتی پیاده سازی آنها را متعادل کنند. ماتیاس ویکنباخ، دانشمند اصلی MIT، مدیر تحقیقات مرکز حمل و نقل و لجستیک MIT (CTL) و محقق در آزمایشگاه هوش مصنوعی واتسون MIT-IBM، در مورد اینکه چگونه هوش مصنوعی می‌تواند راه‌حل‌های بهتر و محاسباتی کارآمدتری برای یک مسئله بهینه‌سازی ترکیبی ارائه دهد، بحث می‌کند. مثل این.
س: مشکل مسیریابی وسیله نقلیه چیست و روش های سنتی تحقیق در عملیات (OR) چگونه آن را حل می کنند؟
آ: تقریباً هر شرکت حمل و نقل و تدارکات مانند USPS، Amazon، UPS، FedEx، DHL با مشکل مسیریابی خودرو مواجه است. به عبارت ساده، یافتن یک مسیر کارآمد است که مجموعه‌ای از مشتریان را به هم متصل می‌کند که یا باید به آنها تحویل داده شود یا چیزی باید از آنها دریافت شود. این تصمیم می‌گیرد که هر یک از آن وسایل نقلیه – که در جاده می‌بینید – در یک روز معین و با چه ترتیبی باید از کدام مشتریان بازدید کنند. به طور معمول، هدف یافتن مسیرهایی است که به کوتاه‌ترین، سریع‌ترین یا ارزان‌ترین مسیر منتهی می‌شوند. اما اغلب آنها همچنین توسط محدودیت هایی هدایت می شوند که مخصوص مشتری است. به عنوان مثال، اگر مشتری دارید که پنجره زمان تحویل مشخصی دارد، یا مشتری در طبقه پانزدهم ساختمان مرتفع روبروی طبقه همکف. این امر ادغام این مشتریان در مسیر تحویل کارآمد را دشوارتر می کند.
برای حل مشکل مسیریابی خودرو، بدیهی است که نمی‌توانیم مدل‌سازی خود را بدون اطلاعات مربوط به تقاضا و در حالت ایده‌آل، ویژگی‌های مرتبط با مشتری انجام دهیم. به عنوان مثال، ما باید اندازه یا وزن بسته های سفارش داده شده توسط مشتری را بدانیم یا اینکه چند واحد از یک محصول خاص باید به یک مکان خاص ارسال شود. همه اینها مدت زمانی را که برای سرویس دهی به آن توقف خاص طول می کشد تعیین می کند. برای مشکلات واقع بینانه، شما همچنین می خواهید بدانید که راننده کجا می تواند وسیله نقلیه را با خیال راحت پارک کند. به طور سنتی، برنامه ریز مسیر باید تخمین های خوبی از این پارامترها ارائه می کرد، بنابراین اغلب مدل ها و ابزارهای برنامه ریزی را پیدا می کنید که فرضیات کلی را ایجاد می کنند زیرا داده های توقف خاصی در دسترس نبود.
یادگیری ماشینی می تواند برای این کار بسیار جالب باشد زیرا امروزه اکثر رانندگان گوشی های هوشمند یا ردیاب های GPS دارند، بنابراین اطلاعات زیادی در مورد مدت زمان تحویل بسته وجود دارد. اکنون می‌توانید در مقیاس، به روشی تا حدی خودکار، آن اطلاعات را استخراج کرده و هر ایستگاه را برای مدل‌سازی واقعی کالیبره کنید.
استفاده از یک رویکرد OR سنتی به این معنی است که یک مدل بهینه‌سازی بنویسید که در آن با تعریف تابع هدف شروع می‌کنید. در بیشتر موارد، این نوعی تابع هزینه است. سپس یک دسته معادلات دیگر وجود دارد که عملکرد درونی یک مسئله مسیریابی را تعیین می کند. به عنوان مثال، شما باید به مدل بگویید که اگر وسیله نقلیه به مشتری مراجعه کند، باید دوباره مشتری را ترک کند. در اصطلاح آکادمیک، معمولاً به آن حفاظت جریان گفته می شود. به همین ترتیب، باید اطمینان حاصل کنید که هر مشتری دقیقاً یک بار در یک مسیر معین بازدید شده است. اینها و بسیاری دیگر از محدودیت های دنیای واقعی با هم تعریف می کنند که چه چیزی یک مسیر قابل دوام را تشکیل می دهد. ممکن است برای ما واضح به نظر برسد، اما باید به صراحت کدگذاری شود.
هنگامی که مسئله بهینه سازی فرموله شد، الگوریتم هایی وجود دارند که به ما کمک می کنند بهترین راه حل ممکن را پیدا کنیم. ما آنها را حل کننده می نامیم. با گذشت زمان، آنها راه حل هایی پیدا می کنند که تمام محدودیت ها را برآورده می کند. سپس سعی می‌کند مسیرهایی را پیدا کند که بهتر و بهتر، بنابراین ارزان‌تر و ارزان‌تر باشند، تا زمانی که بگویید، “باشه، برای من به اندازه کافی خوب است” یا تا زمانی که بتواند از نظر ریاضی ثابت کند که او راه‌حل بهینه را پیدا کرده است. میانگین وسیله نقلیه تحویل در یک شهر ایالات متحده حدود 120 توقف دارد. حل صریح این مشکل ممکن است کمی طول بکشد، بنابراین شرکت ها معمولاً این کار را انجام نمی دهند زیرا از نظر محاسباتی بسیار گران است. بنابراین، آنها به اصطلاح از روش های اکتشافی استفاده می کنند، که الگوریتم هایی هستند که در یافتن راه حل های نسبتاً خوب بسیار مؤثر هستند، اما معمولاً نمی توانند کمیت کنند که این راه حل ها چقدر از بهینه نظری فاصله دارند.
س: شما در حال حاضر از یادگیری ماشین برای مشکل مسیریابی خودرو استفاده می کنید. چگونه از آن برای سود بردن و احتمالاً بهتر شدن از روش های سنتی OR استفاده می کنید؟
آ: این همان چیزی است که ما در حال حاضر با افراد در آزمایشگاه هوش مصنوعی MIT-IBM Watson AI کار می کنیم. ایده کلی در اینجا آموزش مدلی بر روی مجموعه بزرگی از تصمیمات مسیریابی موجود است که یا در عملیات شرکت در دنیای واقعی مشاهده کرده اید یا با استفاده از یکی از این اکتشافی های کارآمد ایجاد کرده اید. در اکثر مدل‌های یادگیری ماشین، دیگر تابع هدف واضحی ندارید. در عوض، باید به مدل بفهمانید که در واقع به چه مشکلی رسیدگی می‌کند و راه‌حل خوبی برای آن مشکل به نظر می‌رسد. به عنوان مثال، مانند آموزش یک مدل زبان بزرگ بر روی کلمات در یک زبان، باید یک مدل یادگیری مسیر را در مورد مفهوم ایستگاه های تحویل مختلف و ویژگی های تقاضای آنها آموزش دهید. مشابه درک گرامر ذاتی زبان طبیعی، مدل شما باید نحوه اتصال این ایستگاه‌های تحویل را به گونه‌ای که منجر به راه‌حل خوبی شود، بداند – در مورد ما، یک راه‌حل ارزان یا سریع. اگر مجموعه‌ای کاملاً جدید از نیازهای مشتری را به سمت او بیاندازید، او همچنان می‌تواند نقاط را به معنای واقعی کلمه به روشی که اگر سعی می‌کردید یک مسیر خوب برای ارتباط آن مشتریان پیدا کنید، به هم وصل کند.
برای این کار از معماری های مدلی استفاده می کنیم که اکثر مردم از فضای پردازش زبان با آن آشنا هستند. به نظر می رسد کمی غیر منطقی است زیرا پردازش زبان چه ربطی به مسیریابی دارد؟ اما در واقع ویژگی‌های این مدل‌ها، به‌ویژه مدل‌های ترانسفورماتور، در یافتن ساختار در زبان خوب هستند – کلمات را به گونه‌ای به هم متصل می‌کنند که جملات را تشکیل می‌دهند. به عنوان مثال، در یک زبان معین شما واژگان خاصی دارید و آن ثابت است. این مجموعه ای مجزا از کلمات ممکن است که می توانید استفاده کنید، و چالش این است که آنها را به روشی معنادار ترکیب کنید. با مسیریابی مشابه است. حدود 40000 آدرس در کمبریج وجود دارد که می توانید از آنها بازدید کنید. این معمولاً زیرمجموعه‌ای از آن آدرس‌هایی است که باید بازدید شوند، و چالش این است: چگونه آن زیرمجموعه – آن “کلمات” – را در یک دنباله منطقی ترکیب کنیم؟
این نوعی تازگی رویکرد ما است – استفاده از این ساختار که ثابت شده است در فضای زبان بسیار موثر است و آن را به بهینه سازی ترکیبی برسانیم. مسیریابی فقط یک آزمون عالی برای ما است زیرا اساسی ترین مشکل در صنعت لجستیک است.
البته، در حال حاضر الگوریتم‌های مسیریابی خوب زیادی وجود دارد که از دهه‌ها تحقیق در عملیات پدید آمده‌اند. آنچه ما در این پروژه می‌خواهیم انجام دهیم این است که نشان دهیم با یک رویکرد روش‌شناختی کاملاً متفاوت مبتنی بر یادگیری ماشینی خالص، می‌توانیم مسیرهایی را پیش‌بینی کنیم که تقریباً به خوبی یا بهتر از مسیرهایی هستند که از اجرای حالت به دست می‌آورید. اکتشافی بهینه سازی مسیرهای پیشرفته
س: روشی مانند روش شما نسبت به سایر تکنیک های پیشرفته OR چه مزایایی دارد؟
آ: در حال حاضر، بهترین روش‌ها از نظر منابع محاسباتی مورد نیاز برای آموزش این مدل‌ها هنوز بسیار تشنه هستند، اما شما می‌توانید بخشی از این تلاش‌ها را از قبل انجام دهید. سپس مدل آموزش دیده در ایجاد راه حل جدید در صورت نیاز نسبتاً کارآمد است.
جنبه دیگری که باید در نظر گرفت این است که محیط عملیاتی یک مسیر، به ویژه در شهرها، دائما در حال تغییر است. زیرساخت‌های موجود جاده یا قوانین ترافیکی و محدودیت‌های سرعت ممکن است تغییر کنند، پارکینگ ایده‌آل ممکن است توسط چیز دیگری اشغال شود، یا یک سایت ساخت‌وساز ممکن است یک جاده را مسدود کند. با یک رویکرد مبتنی بر OR خالص، ممکن است در واقع با مشکل مواجه شوید زیرا باید بلافاصله با در دسترس قرار گرفتن اطلاعات جدید در مورد مشکل، کل مشکل را حل کنید. همانطور که محیط کار به صورت پویا تغییر می کند، باید این کار را بارها و بارها انجام دهید. اگر چه اگر مدلی دارید که به خوبی آموزش دیده است که قبلاً مشکلات مشابهی را دیده است، می تواند به طور بالقوه بهترین مسیر بعدی را برای تقریباً فوری پیشنهاد دهد. بلکه ابزاری است که به شرکت ها کمک می کند تا با تغییرات غیرقابل پیش بینی فزاینده محیط سازگار شوند.
همچنین، الگوریتم های بهینه سازی اغلب برای حل مشکل خاص یک شرکت به صورت دست ساز ساخته می شوند. کیفیت راه حل های به دست آمده توسط چنین الگوریتم های صریح با سطح جزئیات و پیچیدگی طراحی الگوریتم محدود می شود. از سوی دیگر، یک مدل مبتنی بر یادگیری، به طور مداوم یک خط مشی مسیریابی را از داده ها یاد می گیرد. هنگامی که ساختار مدل خود را تعریف کردید، یک مدل یادگیری مسیر به خوبی طراحی شده، بهبودهای بالقوه را در خط مشی مسیریابی شما از تعداد زیادی از مسیرهایی که در آن آموزش دیده است، استخراج می کند. به زبان ساده، یک ابزار مسیریابی مبتنی بر یادگیری به یافتن پیشرفت‌هایی در مسیرهای شما بدون نیاز به سرمایه‌گذاری در طراحی صریح آن بهبودها در الگوریتم ادامه خواهد داد.
در نهایت، روش‌های مبتنی بر بهینه‌سازی معمولاً به بهینه‌سازی برای یک تابع هدف کاملاً تعریف‌شده محدود می‌شوند، که اغلب به دنبال به حداقل رساندن هزینه‌ها یا حداکثر کردن سود هستند. در واقعیت، اهداف پیش روی شرکت ها و رانندگان بسیار پیچیده تر از آن و اغلب تا حدودی متناقض هستند. به عنوان مثال، یک شرکت می خواهد مسیرهای کارآمد را پیدا کند، اما همچنین می خواهد ردپای کربن پایینی داشته باشد. راننده همچنین می خواهد ایمن باشد و راه مناسبی برای خدمت رسانی به این مشتریان داشته باشد. علاوه بر این، شرکت ها به ثبات نیز اهمیت می دهند. یک مدل یادگیری مسیر که به خوبی طراحی شده باشد، در نهایت می تواند این اهداف با ابعاد بالا را به تنهایی به دست آورد، و این چیزی است که شما هرگز نمی توانید به همان روش با رویکرد بهینه سازی سنتی به دست آورید.
بنابراین این نوعی کاربرد یادگیری ماشینی است که در واقع می تواند تأثیر ملموسی در دنیای واقعی در صنعت، جامعه و محیط داشته باشد. صنعت لجستیک مشکلاتی دارد که بسیار پیچیده تر از اینهاست. برای مثال، اگر می‌خواهید کل زنجیره تامین را بهینه کنید – مثلاً جریان یک محصول از یک تولیدکننده در چین از طریق شبکه‌ای از بنادر در سراسر جهان، از طریق شبکه توزیع یک خرده‌فروش بزرگ در آمریکای شمالی به فروشگاه شما که در آن در واقع آن را بخرید—تصمیمات زیادی در این امر دخیل است، که بدیهی است این کار را بسیار دشوارتر از بهینه سازی مسیر یک وسیله نقلیه می کند. امید ما این است که با این کار اولیه، بتوانیم زمینه را برای تحقیقات و همچنین تلاش‌های توسعه بخش خصوصی برای ساخت ابزارهایی فراهم کنیم که در نهایت بهینه‌سازی زنجیره تامین را از پایان به انتها ممکن می‌سازد.
