Ant colony optimisation algorithm for the facility localisation problem

Krzysztof Schiff

Abstrakt

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.

Słowa kluczowe: facility localisation problem, ant colony optimisation, heuristic algorithm
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.
[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.
[3] Lessing L., Dumitrescu I., Stutze T., A comparison between ACO algorithms for the set covering problem, LNCS, Vol. 3172, 2004, 1–12.
[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.
[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.
[6] Antomoshkin A.N., Kazakovtsev L.A., Random search algorithm for the p-median problem, Informatica, Vol. 37, 2013, 267–278.
[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.
[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.
[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] Chvatal V., A greedy heuristic for the set-covering problem, Oper. Research, Vol. 4/3, 1979, 233–235.
[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.
[12] Cerias S., Nobili P., Sassano A., A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming, Vol. 81, 1998, 215–228.
[13] Caprara A., Fischetti M., Toth P., A heuristic method for the set covering problem, Operations Research, Vol. 47/5, 1999, 730–743.
[14] Chiou Y., Lan L.W., Genetic clustering algorithms, European Journal of Operational Research, Vol. 2, No. 132, 2001, 413–427.
[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.
[16] Alp O., ErkutE., Drezner Z., An efficient genetic algorithm for the p-median problem, Annals of Operations Research, Vol. 122, 2003, 21–42.
[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.
[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.
[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.
[20] Lorena A.N., Furtado J.C., A Constructive genetic algorithm for clustering problems, Evolutionary Computation, Vol. 3, No. 9, 2001, 309–328.