Accelerated Heuristic Approaches to the Capacitated Facility Location Problem

Document Type : Original Article

Authors

Assistant Professor, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

Abstract

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.

Keywords

References

[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‎.

Files

Share

How to cite

Statistics