توسعه‌ي مدل استوار چندبازه‌يي براي مواجهه با عدم قطعيت هيستوگرامي (مطالعه‌ي موردي: مكان‌يابي تسهيلات)

Multi-bound robust model of facility location problem to deal with histogram-base uncertainty

يكي از فرض‌هاي بهينه‌سازي كلاسيك، قطعي بودن داده‌هاست در حالي كه وجود پارامتر غيرقطعي در مسايل واقعي غير قابل اجتناب است. بهينه‌سازي استوار ازجمله تكنيك‌هاي توسعه‌يافته براي مواجهه با شرايط غيرقطعي است. در رويكردهاي استواري ارايه‌شده تاكنون فرض بر آن بوده كه پارامتر غيرقطعي عضو مجموعه‌يي محدب است، در حالي كه در بسياري از مسايل واقعي با جمع‌آوري داده‌ها و سوابق گذشته‌ي پارامترها، فضاي غيرقطعي به‌صورت هيستوگرامي تعيين مي‌شود و بايد به‌صورت فضاي غيرمحدب تعريف شود. در اين مقاله ضمن توسعه‌ي الگوريتم پيشنهادي در زمان مواجهه با فضاي غيرقطعي هيستوگرامي، رويكرد پيشنهادي ارايه‌شده براي يافتن جواب استوار مسيله‌‌ي مكان‌يابي كه داراي پارامترهاي تقاضاي غيرقطعي هيستوگرامي است، با توجه به كاربردهاي فراوان تعريف غيرتصادفي پارامترهاي غيرقطعي در مسيله‌‌ي مكان‌يابي استفاده شده است.

A fundamental assumption in classical optimization is that all data are certain. However, many real-world problems contain uncertain parameters. The ignorance of these parameters affects the optimality and even feasibility of the solutions. That is why it is crucial to develop an optimization method to support real time fluctuating parameters. Robust optimization techniques have been developed for tackling the uncertainties which address data uncertainty while ensuring feasibility in different scenarios. Most of the robust approaches which assumed the uncertain data belong to a convex space and single deviation band that may be too limited in practice. The aim of our work is to propose a new algorithm to consider real circumstances by applying histogram-base uncertainty. The suggested algorithm finds the robust counterpart of models with non-convex space built based on historical data as an uncertain space. The new algorithm changes the problem to multi-range robust model which assigns value from more than one uncertain range to the uncertain parameter. The extension of Bertsimas and Sim approach is used to find the robust counterpart model in which an uncertain parameter is allowed to take values from more than one uncertain band. Bertsimas and Sim approach deals with uncertainties in a tractable manner and does not add complexity to the deterministic problem. Moreover, the conservation level of the solution can be handled in their model. Consequently, the obtained robust model of the algorithm guarantees the optimality and the feasibility of solutions in real scenarios with predefined level of conservation. The suggested robust optimization approach is applied to the capacitated facility location problem with a histogram-base uncertainty for demand deviations, since considering probability-based uncertainty is very likely in real facility location problems. The experimental results show the benefits of using the proposed method.