A hybrid iterated local search-firefly algorithm for solving discrete p-center problem

Kamran MALEKI, Mehdi ABBASI
2.728 884

Abstract


P-center problem is one of the most well-known location problems which is classified as NP-Hard. The purpose of this problem is to locate P new facilities among customers such that the maximum distance between customers and their nearest facility is minimized. Firefly method is a new meta-heuristic method that is used for optimization of NP-Hard and combinatorial problems which were mainly developed for optimization of continuous problems inspired by social behavior of fireflies in producing light for the mating. In this study, a hybrid iterated local search-firefly algorithm (HIF) approach was proposed to solve discrete p-center problem which was achieved by combining iterated local search (ILS) and firefly methods. The proposed algorithm was used for solving the OR-LIB problems and the results of method implementing were compared to obtained results from greedy harmony search (GHS) method. It was found the better performance of the proposed HIF algorithm than the GHS method. According to the results, the proposed HIF method on average has more than 60 percent lower error than GHS method and the time to yield the solution decreased about 32 percent.


Keywords


P-center problem, hybrid iterated local search-firefly algorithm, Firefly algorithm, Iterated local search algorithm

Full Text:

PDF


References


Hakimi S.L. (1963). Optimum locations of switching centers and the absolute centers and medians of a graph, Journal of the Operational Research, 12: 450–459.

Kariv O., & Hakimi S.L. (1979). An algorithmic approach to network location problems. Part 1: the p-centers problem, SIAM Journal of Applied Mathematics, 37: 513–538.

Fister I., Fister Jr. I., Yang X.S., & Brest J. (2013). A comprehensive review of firefly algorithms, Swarm and Evolutionary Computation, 13: 34–46.

Yang X.S. (2008). Firefly algorithm, Nature-Inspired Meta-heuristic Algorithms, 20:79–90.

Drezner Z. (1984). The p-center problem-heuristic and optimal algorithms, Journal of the Operational Research, 35 (8), 741–748.

Beasley J.E. (1985). A note on solving large p-median problems, European Journal of Operational Research, 21: 270–273.

Mladenovic N., Labbe M., & Hansen P. (2003). Solving the p-center problem with Tabu search and variable neighborhood search, Networks, 42: 48–64.

Geem Z.W., Kim J.H., & Loganathan G.V. (2001). A new heuristic optimization algorithm: harmony search, Simulation, 76(2): 60–68.

Kaveh A., & Nasr H. (2011). Solving the conditional and unconditional p-center problem with modified harmony search: A real case study, Scientia Iranica, 18 (4): 867–877.

Lourenco H.R., Martin O., & Stutzle T. (2003). Iterated Local Search. Handbook of Meta- heuristics. Kluwer Academic Publishers, International Series in Operations Research & Management Science, 57: 321–353.

Boussaid I., Lepagnot J., & Siarry P. (2013). A survey on optimization meta-heuristics, Information Sciences, 237: 82-117.

Mladenovic N., Brimberg J., Hansen P., Jose A., & Perez M. (20070. The p-median problem: A survey of meta-heuristic approaches, European Journal of Operational Research, 179 (3): 927- 939.