Outline

  • Abstract
  • Keywords
  • 1. Introduction
  • 2. Problem Description and Mathematical Formulation
  • 3. Hybrid Adaptive Large Neighborhood Search Algorithm
  • 3.1. Initial Solution
  • 3.2. List of Operators
  • 3.2.1. Destroy Operators
  • 3.2.2. Repair Operators
  • 3.3. Subproblem Solution
  • 3.4. Improvement Procedure
  • 3.5. Parameter Settings and Pseudocode
  • 4. Computational Experiments
  • 5. Conclusion
  • Acknowledgments
  • References

رئوس مطالب

  • چکیده
  • کلیدواژه ها
  • 1. مقدمه
  • 2. شرح مسئله و رابطه ریاضی
  • 3. الگوریتم جستجوی همسایگی وسیع تطبیقی ترکیبی
  • 3.1 راه حل اولیه
  • 3.2 فهرستی از اپراتورها
  • 3.2.1 اپراتورهای از بین برنده
  • 1. تعطیلی تصادفی P تاسیسات
  • 2. تعطیلی تاسیسات دارای کمترین تعداد مشتریان احتمالی
  • 3. تعطیلی تاسیسات با کمترین تقاضای کل احتمالی
  • 4. تعطیلی یکی از دو نزدیکترین تاسیسات
  • 3.2.2 اپراتورهای اصلاح کننده
  • 1. گشایش تصادفی یک تاسیسات
  • 2. گشایش تاسیساتی در دستکم 29 واحد از کلیه تاسیسات گشایش یافته
  • 3. گشایش تاسیساتی با بیشترین پتانسیل سرویس دهی (مشتری)
  • 4. گشایش تاسیساتی با بیشترین پتانسیل سرویس دهی (تقاضا)
  • 3.3 حل مسئله فرعی
  • 3.4 شیوه ارتقا دهی
  • 3.5 تنظیمات پارامترها و شبه کد
  • 4. آزمایشات محاسباتی
  • 5. نتیجه گیری

Abstract

This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location–Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver.

Keywords: - - - - - -

Conclusions

This study presented a hybrid method for solving the probabilistic maximal covering location-allocation problem. The algorithm is based on an adaptive large neighborhood search heuristic to determine the location decisions of the problem. Allocation subproblems are solved exactly by mathematical programming at each iteration. A flexible improvement procedure polishes good solutions obtained by the metaheuristic. A high performance solver has been employed to obtain bounds and prove optimality for some instances. This exact approach has found new best known solutions for 19 instances, proving optimality for 18 of them. The hybrid method performed very consistently, finding the best known solutions for 94,5% of the instances, outperforming the state-of-the-art heuristic method from the literature. A new dataset was tested and confirmed the superiority of the heuristic in instances that are difficult to solve by exact methods.

دانلود ترجمه تخصصی این مقاله دانلود رایگان فایل pdf انگلیسی