حل ابتکاری مساله مکان‌یابی تسهیلات ظرفیت‌دار و راهکارهای تسریع آن

نوع مقاله : مقاله پژوهشی

نویسندگان

استادیار، گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه مازندران، بابلسر، ایران

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

Accelerated Heuristic Approaches to the Capacitated Facility Location Problem

نویسندگان [English]

  • Ahmad Moradi
  • Ali Valinejad
Assistant Professor, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran
چکیده [English]

In this paper, a heuristic solution approach to the single source capacitated facility location problem is considered. As a first step, a local search method is designed to perform quick simple moves in the solution structure. Then, the greedy manner of the local search is combined by Simulated Annealing meta-heuristic. Such a careful combination would allow escaping local optima with the aim of more diversified search capabilities. The method, then makes use of acceleration mechanisms to enhance search process. Here, we combine the algorithm with two different acceleration mechanisms namely consecrating mechanism and parallelizing mechanism. Such a combination will define two different versions of the mentioned search strategy based on simulated annealing meta-heuristic. Computational results obtained over the existing standard benchmark instances, not only demonstrate the superiority of the proposed method over the best existing ones, but also announce the method as an effective practical tool to tackle the problem.

کلیدواژه‌ها [English]

  • Facility Location
  • Heuristic Methods
  • Simulated Annealing Algorithm
  • Parallelism
  • Neighborhood Structure

مراجع

[1]     H‎. ‎A. Eiselt‎ and V. Marianov‎, (2011)‎. Foundations of location analysis, Vol‎. ‎155‎. ‎Springer Science & Business Media‎.
[2]     A., Klose‎, and A‎. Drexl, ‎Facility location models for distribution system design‎. European journal of operational research‎, ‎162 (1)‎, 2005, ‎4-29‎.
[3]     M. Akbari, A Model for Production and Inventory Control in Crisis Condition, Management Research in Iran, 19 (4), 2016, 45-70. (In Persian)
[4]     A. Jafarnejhad, M. Esmaelian, and M. Rzvani, An Inventory-Location Model Formulation and Computational Results, Management Research in Iran, 12 (1), 2008, 105-125. (In Persian)
[5]     M. Asadi, M. Ali Shafia and S .Yaghoubi, A Disaster Facilities Location-Allocation Model Considering Reliability under Uncertainty and Dynamic Demand (Case Study: Earthquake Disaster in Tehran). Modern Researches in Decision Making, 3 (1), 2018, 1-28. (In Persian)
[6]     S. Basu, M. Sharma and P. S. Ghosh, Metaheuristic applications on discrete facility location problems: a survey. Opsearch, 52(3), 2015, 530-561.
[7]     J‎. ‎A. Diaz‎, ‎and E. Fernández, ‎A branch-and-price algorithm for the single source capacitated plant location problem‎. Journal of the Operational Research Society‎, ‎53 (7)‎, 2002, ‎728-740‎.
[8]     Z. Yang‎, ‎F. ‎Chu‎ and H. Chen, ‎A cut-and-solve based algorithm for the single-source capacitated facility location problem‎. European Journal of Operational Research‎, ‎221 (3)‎, 2012, ‎521-532‎.
[9]     R‎. ‎D. Galvao‎, and V. Marianov‎, ‎Lagrangean relaxation-based techniques for solving facility location problems‎. ‎In Foundations of location analysis. ‎Springer US‎., ‎2011, 391-420‎.
[10]  R‎. ‎K.‎ Ahuja‎, J‎. ‎B. ‎‎Orlin, ‎S. ‎Pallottino, ‎M‎. ‎P. ‎Scaparra‎ and ‎M‎. ‎G‎. Scutella‎, ‎A multi-exchange heuristic for the single-source capacitated facility location problem‎. Management Science‎, ‎50 (6), 2004, ‎749-760‎.
[11]  I‎. ‎A.‎ Contreras‎, and J‎. ‎A‎. Diaz‎,‎ ‎‎Scatter search for the single source capacitated facility location problem‎. Annals of Operations Research‎, ‎157 (1), 2008, ‎73-89‎.
[12]  S‎. ‎C‎. Ho‎, ‎An iterated tabu search heuristic for the single source capacitated facility location problem, Applied Soft Computing‎, ‎27‎, 2015, ‎169-178‎.
[13]  ‎E. Aarts‎, ‎J. ‎Korst and W. Michiels‎, ‎Simulated annealing,‎ Search methodologies, Springer, Boston, MA, 2014, 265-285.
[14]  S. Ghafoori, and M. Taghizadeh yazdi, Proposing a Multi-Objective Mathematical Model for RCPSP and Solving It with Firefly and Simulated Annealing algorithms. Modern Researches in Decision Making, 1(4), 2016, 117-142. 
[15]  B. Chapman‎, G. Jost‎ and R. Van Der Pas‎, ‎(2008)‎. Using OpenMP‎: ‎portable shared memory parallel programming. Vol‎. ‎10‎. ‎MIT press‎.
[16]  W. Gropp‎, ‎E. ‎Lusk‎‎ and A. Skjellum‎, (2014). Using MPI‎: ‎portable parallel programming with the message-passing interface. Vol‎. ‎1‎. ‎MIT press‎.
پژوهش های نوین در تصمیم گیری
دوره 3، شماره 3
آذر 1397
صفحه 191-211

فایل ها

هم رسانی

ارجاع به این مقاله

آمار