Ant Colony Optimisation Algorithm for the Facility Localisation Problem

Schiff, Krzysztof

doi:10.4467/2353737XCT.18.008.7959

Abstract

This article describes a new ant colony optimisation algorithm for the facility localisation problem with a new heuristic pattern proposed by the author, which consists of three parts: the function of the average cost of client servicing; the total minimum cost of servicing from a site, which is selected and included into the solution; the function of improving the cost of already serviced clients. In this comparison, simulations were presented, and two parameters were observed: the number of sites and the cost of client servicing. The new algorithm allowed to improve the solution in both of these parameters.

References

[1] Pasricha R., Wadhwa V., Optimizing facility location problem using genetic algorithm, comparison between ACO algorithms for the set covering problem, International Journal of Computer Science and Telecommunication, Vol. 2, Issue 3, 2011, 13–15.
Search in Google Scholar Back to article
[2] Varnamkhasti M.J., Overview of algorithms for solving the p-median facility location problems, comparison between ACO algorithms, Advanced studies in biology, Vol. 4, No. 2, 2012, 49–55.
Search in Google Scholar Back to article
[3] Lessing L., Dumitrescu I., Stutze T., A comparison between ACO algorithms for the set covering problem, LNCS, Vol. 3172, 2004, 1–12.
Search in Google Scholar Back to article
[4] Lghoseiri K., Ghannadpour S.F., An efficient heuristic method for capacitated p-median problem, International Journal of Management Science, Vol. 4, 2009, No. 1, 72–80.10.1080/17509653.2009.10671064
Search in Google Scholar Back to article
[5] Crawford B., Soto R., Momfroy E., Paredes F., Palma W., A hybrid Ant algorithm for the set covering problem, International Journal of the Physical Sciences, Vol. 6/19, 2011, 4667–4673.
Search in Google Scholar Back to article
[6] Antomoshkin A.N., Kazakovtsev L.A., Random search algorithm for the p-median problem, Informatica, Vol. 37, 2013, 267–278.
Search in Google Scholar Back to article
[7] Sevkli M., Mamedsaidov R., Camci F., A novel discrete particle swarm optimization for p-median problem, Journal of King Saud University – Engineering Sciences, Vol. 26, 2014, 11–19.10.1016/j.jksues.2012.09.002
Search in Google Scholar Back to article
[8] Balas E., Carrera M.C., A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, Vol. 44/6, 1996, 875–890.10.1287/opre.44.6.875
Search in Google Scholar Back to article
[9] Fisher M.L., Kedia P., Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, Vol. 36/6, 1990, 674–688.10.1287/mnsc.36.6.674
Search in Google Scholar Back to article
[10] Chvatal V., A greedy heuristic for the set-covering problem, Oper. Research, Vol. 4/3, 1979, 233–235.10.1287/moor.4.3.233
Search in Google Scholar Back to article
[11] Lan G., Depuy G.W., On the effectiveness of incorporating randomness into a multi-star-heuristic with application to the set covering problem, Computer Industrial Engineer., Vol. 51, No. 3, 2006, 362–374.10.1016/j.cie.2006.08.002
Search in Google Scholar Back to article
[12] Cerias S., Nobili P., Sassano A., A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming, Vol. 81, 1998, 215–228.10.1007/BF01581106
Search in Google Scholar Back to article
[13] Caprara A., Fischetti M., Toth P., A heuristic method for the set covering problem, Operations Research, Vol. 47/5, 1999, 730–743.10.1287/opre.47.5.730
Search in Google Scholar Back to article
[14] Chiou Y., Lan L.W., Genetic clustering algorithms, European Journal of Operational Research, Vol. 2, No. 132, 2001, 413–427.10.1016/S0377-2217(00)00320-9
Search in Google Scholar Back to article
[15] Bozkaya B., Zhang J., Erkut E., An efficient genetic algorithm for the p-median problem, in Facility Location: Applications and Theory Operations Research, Berlin, Springer, 2002, 179–205.10.1007/978-3-642-56082-8_6
Search in Google Scholar Back to article
[16] Alp O., ErkutE., Drezner Z., An efficient genetic algorithm for the p-median problem, Annals of Operations Research, Vol. 122, 2003, 21–42.10.1023/A:1026130003508
Search in Google Scholar Back to article
[17] Lessing L., Dumitrescu I., Stutzle T., A comparison between ACO algorithms for the set covering problem, [in:] Ant Colony Optimization and Swarm Intelligence, LNCS, Vol. 3172, Springer Verlag, Berlin, 2004, 1–12.
Search in Google Scholar Back to article
[18] Crawford B., Castro C., Integrating look ahead and post processing procedures with ACO for solving set partitioning and covering problems, [in:] Proc. of the 8th international conference on Artificial Intelligence and Soft Computing, Springer–Verlag, Berlin, Heidelberg, 2006, 1082–1090.10.1007/11785231_113
Search in Google Scholar Back to article
[19] Lim A., Hu Z., A fixed-length subset genetic algorithm for the p-median problem, LNCS, Vol. 2724, Springer Verlag, Berlin, 2003, 1596–1597.
Search in Google Scholar Back to article
[20] Lorena A.N., Furtado J.C., A Constructive genetic algorithm for clustering problems, Evolutionary Computation, Vol. 3, No. 9, 2001, 309–328.10.1162/10636560175040601911522209
Search in Google Scholar Back to article

Ant Colony Optimisation Algorithm for the Facility Localisation Problem

Abstract

Paradigm

My account