Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 519.6
GREEDY HEURISTIC METHOD FOR LOCATION PROBLEMS
L. A. Kazakovtsev*, A. N. Antamoshkin
Reshetnev Siberian State Aerospace University 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation *Е-mail: levk@bk.ru
Authors consider multi-source location problems, k-means, k-median and k-medoid. Such problems are popular models in logistics (optimal location of factories, warehouses, transportation hubs etc.) and cluster analysis, approximation theory, estimation theory, image recognition. Various distance metrics and gauges allow using these models for clustering various kinds of data: continuous and discrete numeric data, Boolean vectors, documents. Wide area of application of such problems leads to growing interest of researchers in Russia and worldwide. In this paper, the authors propose a new heuristic method for solving such problems which can be used as a standalone local search method (local search multi-start) or as the main part of a new algorithm based on ideas of the probability changing method. For the parameters self-tuning of such algorithm, the authors propose new meta-heuristic which allows using new algorithm without learning specific features of each solved problem. Algorithms were tested on various data sets of size up to 160000 data vectors from the UCI repository and real data of semiconductor devices examination. For testing purposes, various distance metrics were used. Computational experiments showed the high efficiency of new algorithms in comparison with local search methods used traditionally for the considered problems. In addition, results were compared with the evolutionary methods and a deterministic algorithm based on the Information Bottleneck Clustering method. Such comparison illustrated the ability of new algorithms to reach higher preciseness of the results in reasonable time.
p-median, k-medoid, k-means, Information Bottleneck Clustering.
References
  1. Farahani R. Z., Hekmatfar M. (editors). Facility Location Concepts, Models, Algorithms and Case Studies. Springer-Verlag Berlin Heidelberg, 2009, 550 p.
  2. Kazakovtsev L. A., Stupina A. A. Fast Genetic Algorithm with Greedy Heuristic for p-Median and k-Means Problems. IEEE 2014 6th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), St.-Petersburg, October 6–8, 2014. 2014, P. 702–706.
  3. Kazakovtsev L. A., Antamoshkin A. N. Genetic Algorithm wish Fast Greedy Heuristic for Clustering and Location Problems. Informatica. 2014, Vol. 38, Iss. 3. P. 229–240.
  4.  Deza M. M., Deza E. Encyclopedya of Distances. Springer Verlag. Berlin, Heilderberg, 2009, 590 p., DOI: 10.1007/978-3-642-00234-2_1.
  5. Trubin V. A. [An efficient algorithm for the Weber problem with rectilinear metric]. Kibernetika. 1978, Iss. 6, P. 67–70, DOI:10.1007/BF01070282/ (In Russ.).
  6. Kaufman L., Rousseeuw P. J. Finding Groups in Data: an Introduction to Cluster Analysis. New York: John Wiley & Sons, 1990, 342 p., DOI: 10.1002/ 9780470316801.ch1.
  7. Park H. S., Jun C.-H. A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications. 2009, Vol. 36, P. 3336–3341.
  8. Lucasius C. B., Dane A. D., Kateman G. On K-Medoid Clustering of Large Data Sets with the Aid of a Genetic Algorithm: Background, Feasibility and Comparison. Analytical Chimica Acta. 1993, Vol. 282, P. 647–669, DOI: 10.1007/s10732-006-7284-z.
  9. Zhang Q., Couloigner I. A New Efficient K-Medoid Algorithm for Spatial Clustering. ICCSA 2005, LNCS. 2005, Vol. 3482, P. 181–189, DOI: 10.1007/11424857_20.
  10. Sheng W., Liu X. A Genetic K-Medoids Clustering Algorithm. Journal of Heuristics. 2004, Vol. 12, Iss. 6, P. 447–466, DOI: 10.1007/s10732-006-7284-z.
  11.  Cooper L. Location-allocation problem. Oper. Res. 1963, Vol. 11, P. 331–343, DOI: 10.1287/ opre.11.3.331.
  12. Arthur D., Vassilvitskii S. k-Means++: the Advantages of Careful Seeding. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 2007, P. 1027–1035, DOI: 10.1.1.360.7427.
  13. Mishra N., Oblinger D., Pitt L. Sublinear time approximate clustering. 12th SODA. 2001, P. 439–447.
  14.  Ackermann M. R. et al. StreamKM: A Clustering Algorithm for Data Streams. J. Exp. Algorithmics. 2012, Vol. 17, Article 2.4, DOI: 10.1145/2133803.2184450/.
  15. Sun Zh., Fox G., Gu W., Li Zh. A parallel clustering method combined information bottleneck theory and centroid-based clustering. The Journal of Supercomputing. 2014, Vol. 69, Iss. 1, P. 452–467. DOI: 10.1007/s11227-014-1174-1.
  16. Alp O., Erkut E., Drezner Z. An Efficient Genetic Algorithm for the p-Median Problem. Annals of Operations Research. 2003, Vol. 122, Iss. 1–4, Р. 21–42. DOI: 10.1023/A:1026130003508.
  17. Neema M. N., Maniruzzaman K. M., Ohgai A. New Genetic Algorithms Based Approaches to Continuous p-Median Problem. Netw. Spat. Econ. 2011, Vol. 11, P. 83–99. DOI: 10.1007/s11067-008-9084-5.
  18. Kuehn A. A., Hamburger M. J. A heuristic program for locating warehouses. Management Science. 1963, Vol. 9, Iss. 4, P. 643–666, DOI:10.1287/mnsc.9.4.643.
  19. Kazakovtsev L. A., Orlov V. I., Stupina A. A., Masich I. S. [Problem of electronic components classifying]. Vestnnik SibGAU. 2014, No. 4(56), P. 55–61 (In Russ.).

Kazakovtsev Lev Aleksandrovich – Cand. Sc., Docent, Docent of Information economic system department, Reshetnev Siberian State Aerospace University. Е-mail: levk@bk.ru

Antamoshkin Alexander Nikolaevich – Dr. Sc., professor, Reshetnev Siberian State Aerospace University. E-mail: oleslav@mail.ru