روشی سریعتر برای حل مشکلات برنامه ریزی پیچیده

هنگامی که برخی از قطارهای مسافرتی به انتهای خط می رسند ، باید به یک سکوی تعویض سفر کنند تا بتوانند بعداً از ایستگاه خارج شوند ، غالباً از سکوی متفاوت از آنچه در آن وارد شده است.

مهندسان برای برنامه ریزی این حرکات از برنامه های نرم افزاری به نام Solvers الگوریتمی استفاده می کنند ، اما در ایستگاه با هزاران نفر از ورود و عزیمت هفتگی ، مشکل برای یک حل کننده سنتی بسیار پیچیده می شود تا همه به یکباره باز شود.

با استفاده از یادگیری ماشین ، محققان MIT یک سیستم برنامه ریزی بهبود یافته ایجاد کرده اند که زمان حل را تا 50 درصد کاهش می دهد و راه حلی را تولید می کند که بهتر از هدف کاربر باشد ، مانند روی-زمان عزیمت قطار. روش جدید همچنین می تواند برای حل کارآمد سایر مشکلات لجستیکی پیچیده ، مانند برنامه ریزی کارکنان بیمارستان ، اختصاص خدمه هواپیمایی یا اختصاص وظایف به دستگاه های کارخانه استفاده شود.

مهندسان غالباً این نوع مشکلات را به دنباله ای از زیرمجموعه های همپوشانی تقسیم می کنند که هر یک می توانند در مدت زمان ممکن حل شوند. اما همپوشانی ها باعث می شود که بسیاری از تصمیمات بی نیاز دوباره به دست بیایند ، بنابراین برای رسیدن به یک راه حل بهینه ، حل کننده بسیار طولانی تر طول می کشد.

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

“اغلب ، یک تیم اختصاصی می تواند ماه ها یا حتی سالها را برای طراحی الگوریتم صرف کند تا فقط یکی از این مشکلات ترکیبی را حل کند. یادگیری عمیق مدرن به ما فرصتی می دهد تا از پیشرفت های جدید برای کمک به طراحی این الگوریتم ها استفاده کنیم. سیستم ها و جامعه (IDS) در MIT و عضو آزمایشگاه سیستم های اطلاعات و تصمیم گیری (LIDS).

به او پیوسته است روی مقاله توسط نویسنده اصلی Sirui Li ، دانشجوی فارغ التحصیل IDSS. Wenbin Ouyang ، دانشجوی فارغ التحصیل CEE ؛ و yining ma ، یک پست دکتری. این تحقیق در کنفرانس بین المللی ارائه خواهد شد روی یادگیری بازنمایی.

حذف افزونگی

یکی از انگیزه های این تحقیق ، یک مشکل عملی است که توسط دانشجوی کارشناسی ارشد دیوین کامیل ویلکینز در دوره حمل و نقل در سطح وو مشخص شده است. دانش آموز می خواست یادگیری تقویت را برای یک مشکل واقعی قطار قطار در ایستگاه شمالی بوستون اعمال کند. سازمان ترانزیت باید قطارهای زیادی را به تعداد محدودی از سیستم عامل ها اختصاص دهد که در آن می توان قبل از ورود آنها به ایستگاه به خوبی چرخید.

به نظر می رسد این یک مشکل برنامه ریزی بسیار پیچیده ترکیبی است – نوع دقیق مشکلی که آزمایشگاه وو در چند سال گذشته انجام داده است onبشر

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

در برنامه ریزی فروشگاه کار انعطاف پذیر ، هر کار برای تکمیل نیاز به زمان متفاوتی دارد ، اما می توان وظایف را به هر دستگاه اختصاص داد. در عین حال ، هر کار از عملیاتی تشکیل شده است که باید به ترتیب صحیح انجام شود.

چنین مشکلاتی به سرعت برای حل کننده های سنتی بسیار بزرگ و ناخوشایند می شود ، بنابراین کاربران می توانند از بهینه سازی نورد افق (RHO) استفاده کنند تا مشکل را به تکه های قابل کنترل تبدیل کنند که می توانند سریعتر حل شوند.

با استفاده از Rho ، یک کاربر چند کار اولیه را به ماشین آلات در یک افق برنامه ریزی ثابت اختصاص می دهد ، شاید یک پنجره زمانی چهار ساعته. سپس ، آنها اولین کار را در آن دنباله انجام می دهند و افق برنامه ریزی چهار ساعته را به جلو تغییر می دهند تا کار بعدی را اضافه کنند ، process تا زمانی که کل مشکل حل نشود و برنامه نهایی تکالیف ماشین کار ایجاد شود.

یک افق برنامه ریزی باید طولانی تر از مدت زمان هر کار باشد ، زیرا اگر الگوریتم وظایفی را که پیش می آید نیز در نظر می گیرد ، راه حل بهتر خواهد بود.

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

وو توضیح می دهد: “شاید این راه حل های اولیه خوب باشد و نیازی به محاسبه مجدد نباشد ، اما شاید آنها خوب نباشند. این جایی است که یادگیری ماشین وارد می شود.”

محققان برای تکنیک خود ، که آنها بهینه سازی افق نورد با هدایت یادگیری (L-RHO) می نامند ، یک مدل یادگیری ماشین را آموزش می دهند تا پیش بینی کنند که کدام عملیات یا متغیرها باید هنگام حرکت افق برنامه ریزی دوباره انجام شود.

L-RHO برای آموزش مدل به داده ها نیاز دارد ، بنابراین محققان با استفاده از یک حل کننده الگوریتمی کلاسیک ، مجموعه ای از زیرمجموعه ها را حل می کنند. آنها بهترین راه حل ها را گرفتند – آنهایی که بیشترین عملیاتی را که نیازی به بازسازی آنها ندارند – و از اینها به عنوان داده های آموزشی استفاده می کردند.

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

وی می افزاید: “اگر در ضمن ، ما نیازی به دوباره بهینه سازی آنها نداریم ، می توانیم این متغیرها را از این مسئله دور کنیم. از آنجا که این مشکلات از نظر اندازه به صورت تصاعدی رشد می کنند ، اگر بتوانیم برخی از این متغیرها را کنار بگذاریم ، می تواند بسیار سودمند باشد.”

یک رویکرد سازگار و مقیاس پذیر

برای آزمایش رویکرد خود ، محققان L-RHO را با چندین حلال الگوریتمی پایه ، حل کننده های تخصصی و رویکردهایی که فقط از یادگیری ماشین استفاده می کنند ، مقایسه کردند. این از همه آنها بهتر است ، زمان حل 54 درصد و بهبود کیفیت راه حل تا 21 درصد را کاهش می دهد.

علاوه بر این ، روش آنها هنگام آزمایش آن از همه خطوطی بهتر است روی انواع پیچیده تری از مشکل ، مانند زمانی که دستگاه های کارخانه تجزیه می شوند یا در هنگام احتقان قطار اضافی وجود دارد. این حتی از خطوط اضافی اضافی که محققان برای به چالش کشیدن حل کننده خود ایجاد کرده اند ، بهتر عمل می کند.

او می گوید: “رویکرد ما می تواند بدون تغییر در همه این انواع مختلف اعمال شود ، این واقعاً همان کاری است که ما با این خط تحقیق انجام می دهیم.”

L-RHO همچنین می تواند در صورت تغییر اهداف ، به طور خودکار یک الگوریتم جدید برای حل مشکل ایجاد کند-تمام آنچه که به آن نیاز دارد یک مجموعه داده جدید آموزش است.

در آینده ، محققان می خواهند منطق تصمیم مدل خود را برای یخ زدن برخی از متغیرها بهتر درک کنند ، اما نه دیگران. آنها همچنین می خواهند رویکرد خود را در انواع دیگر مشکلات بهینه سازی پیچیده مانند مدیریت موجودی یا مسیریابی وسیله نقلیه ادغام کنند.

این کار تا حدودی توسط بنیاد ملی علوم ، کمیته پشتیبانی تحقیقاتی MIT ، کمک هزینه دکتری روباتیک آمازون و Mathworks پشتیبانی شد.