حل مسئله فروشنده دوره گرد سود ده با الگوریتم تقریبی چند معیاره همزمان

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

Keywords:

الگوریتم تقریبی , فروشنده دوره گرد سود ده , پیچیدگی سخت , نقاط کارا