A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem

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