حل مساله مکانیابی-تخصیص با و بدون ظرفیت با الگوریتم مبتنی بر روش تقریب هذلولی

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

Keywords:

مکانیابی – تخصیص , محدودیت ظرفیت , الگوریتم تقریب هذلولی