Deterministic algorithm with agglomerative heuristic for location problems

International Scientific and Research Conference on Topical Issues in Aeronautics and Astronautics (dedicated to the 55th anniversary from the foundation of SibSAU)

航空航天工程

Kazakovtsev, L.^1 ; Stupina, A.^2

Siberian State Aerospace University Named after Academician M.F. Reshetnev, 31 Krasnoyarskiy Rabochiy prospect, Krasnoyarsk

660037, Russia^1

Siberian State University, 3 Vuzovskii, Krasnoyarsk

660025, Russia^2

关键词: Clustering methods;    Clustering problems;    Deterministic algorithms;    Greedy heuristics;    Information bottleneck;    Location problems;    Stochastic methods;    Warehouse location;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/94/1/012016/pdf
DOI  :  10.1088/1757-899X/94/1/012016

学科分类：航空航天科学

来源: IOP

【 摘 要 】

Authors consider the clustering problem solved with the k-means method and p-median problem with various distance metrics. The p-median problem and the k-means problem as its special case are most popular models of the location theory. They are implemented for solving problems of clustering and many practically important logistic problems such as optimal factory or warehouse location, oil or gas wells, optimal drilling for oil offshore, steam generators in heavy oil fields. Authors propose new deterministic heuristic algorithm based on ideas of the Information Bottleneck Clustering and genetic algorithms with greedy heuristic. In this paper, results of running new algorithm on various data sets are given in comparison with known deterministic and stochastic methods. New algorithm is shown to be significantly faster than the Information Bottleneck Clustering method having analogous preciseness.