Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem

در این مقاله، ما با استفاده از یک مدل جدید از مدل حداکثر-کمترین وزن با استفاده از مشکل حل منازعه برخورد می کنیم. مشکل شامل شناسایی مانورهایی است که فاصله جدایی لازم بین تمام جفتهای مجموعه ای از هواپیما را حفظ می کند در حالی که هزینه های سوخت را به حداقل می رساند. ما یک گراف را طراحی می کنیم که در آن رأس ها به مجموعه ای محدود از مانور ها متصل می شوند و لبه ها مانورهای بدون انطباق را برقرار می کنند. حداکثر فشار از وزن کم، یک وضعیت بدون تضاد را فراهم می کند که شامل تمام هواپیما است و هزینه های ناشی از آن را کاهش می دهد. این مدل در مقایسه با مسائل مربوط به جستجوی کلاسیک از ساختار هزینه های دیگر استفاده می کند: هزینه های رأس ها را نمی توان پیش تعیین کرد، زیرا آنها به رأس ها در سلسله مراتب بستگی دارد. ما مشکل را به عنوان یک برنامه خطی عدد صحیح ترکیب می کنیم. از آنجایی که مدل سازی دینامیک هواپیما و محاسبه مسیرها از فرایند راه حل جدا شده است، چارچوب ریاضی ما برای هر گونه فرضیه ای بر دینامیک هواپیما و هر انتخاب مانور های موجود معتبر است. به طور خاص، این هواپیما می تواند سرعت پویا، سرفصل و تغییرات سطح پرواز را انجام دهد. برای حل مواردی که تعداد زیادی از هواپیما را در چندین سطح پرواز پخش می کنند، ما دو الگوریتم تجزیه را معرفی می کنیم. اول، یک روش برنامه ریزی خطی یکپارچگی دنباله ای است که به طور تکراری اختیاری از مانور ها را برای انجام یک کار بین زمان و هزینه محاسبه می کند. دوم، جستجوگر محله بزرگ است که از اولین روش به عنوان یک فرعی استفاده می کند. بهترین راه حل برای مانورهای موجود در کمتر از 10 ثانیه برای مواردی که تا 250 هواپیما به طور تصادفی به سطوح پرواز بیستون اختصاص داده می شود، به دست می آید.