Ant colony optimisation algorithm for the facility localisation problem

• Autorzy: Schiff K.

Identyfikatory

DOI

10.4467/2353737XCT.18.008.7959

Warianty tytułu

PL

Algorytm mrówkowy dla problemu lokalizacji punktów obsługi

• Języki publikacji: EN

Abstrakty

EN

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.

PL

W artykule przedstawiono algorytm mrówkowy dla problemu lokalizacji fabryk z nową zaproponowaną heurystyką wyboru obiektów i został on porównany z innym znanym już z literatury przedmiotu algorytmem mrówkowym. Nowa heurystyka wyboru została wyrażona jako iloraz trzech funkcji pożądania wyboru, to jest funkcji określającej średni koszt obsługi klientów poprzez włączaną lokalizację do rozwiązania, funkcję określająca całkowitą minimalną sumę obsługiwania klientów z włączanej do rozwiązania lokalizacji oraz funkcję określająca maksymalną minimalizację kosztów obsługiwania klientów poprzez włączaną lokalizację, gdy ci klienci są już obsługiwani przez lokalizacje wybrane do rozwiązania. W artykule przedstawiono wyniki przeprowadzonych testów pod kątem uzyskania jak najmniejszej liczby lokalizacji i jak najmniejszego kosztu obsługiwania klientów w funkcji rozmiaru problemu i natężenia obsługiwania klientów z danej lokalizacji.

Słowa kluczowe

EN

facility localisation problem; ant colony optimisation; heuristic algorithm

PL

problem lokalizacji punków obsługi; algorytm mrówkowy; heurystyka

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Technical Transactions
• Rocznik: 2018
• Tom: Vol. 115, iss. 1
• Strony: 103--112
• Opis fizyczny: Bibliogr. 20 poz., wz., tab., wykr.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical Engineering, Cracow University of Technology

Bibliografia

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

Uwagi

EN

Section "Electrical Engineering"

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).