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

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

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

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

UDK 519.6
APPLICATION OF THE PROBABILITY CHANGING METHOD FOR OPTIMAL LOCATION PROBLEMS ON A NETWORK
A. N. Antamoshkin, L. А. Kazakovtsev
Siberian State Aerospace University named after academician M. F. Reshetnev 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation E-mail: levk@bk.ru
In this paper, the authors consider the p-median optimal location problem on a graph (network) which is a popular model for both logistic problems (optimal transportation, telecommunication and other infrastructure elements placement) and problems of cluster analysis, pattern recognition and estimation theory. The aim of the p-median problem on a graph (network) is to find the given number p of vertices of a graph such that the total distance from each vertex to the nearest chosen vertex reaches its minimum. To solve this NP-hard (in general) problem approximately, the authors propose a heuristic algorithm based on ideas of the probability changing method which is a random search method with adaptation. The idea of the proposed algorithm is based on random choosing of vertices in accordance with the given probabilities of choosing each of them. The probabilities for every chosen vertex and its neighborhood alter depending on the value of the objective function (i.e. in accordance with the total distance from each of the vertices to the nearest chosen vertex). For the algorithm for the large-scale p-median problems, a problem of optimal use of computational capacity is important. The effectiveness of the proposed algorithm was proved experimentally on test datasets from the ORLIB (special dataset library for operations research). In addition, the authors illustrate the results for the proposed algorithm combined with a local search procedure for the considered problem. The experiments show that the results of such combination exceed the results of the multiple start of the local search procedure from randomly chosen vertices. In addition, the experiments demonstrate the ability of the proposed algorithm to reach an exact solution for small problems.
discrete optimization, p-median problem, methods of random search, the location problem.
References
  1. Wesolowsky G. The Weber problem: History and perspectives. Location Science. 1993, vol. 1, p. 53.
  2. Drezner Z., Wesolowsky G. O. A Trajectory Method for the Optimization of the Multifacility Location Problem with lp Distances. Management Science. 1978, vol. 24, p. 1507–1514.
  3. Osinuga I. A., Bamigbola O. N. On the Minimum Norm Solution to Weber problem. SAMSA Conference Proceedings. Windhoek, 2007, p. 27–30.
  4. Cooper L. An extension of the generalized Weber problem. Journal of Regional Science. 1968, vol. 8, Iss. 2, p. 181–197.
  5. Hakimi S. L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research. 1964, Iss. 12(3), p. 450–459.
  6. Kariv O., Hakimi S. L. An algorithmic approach to the network location problems. II. The p-medians. SIAM Journal on Applied Mathematics. 1979, vol. 37(3), p. 539–560.
  7. Avella P., Sassano A., Vasil’ev I. Computational Study of Large-Scale p-Median Problems. Mathematical Programming. 2007, vol. 109(1), p. 89–114.
  8. Masuyama S., Ibaraki T., Hasegawa T. The Computational Complexity of the m-Center Problems on the Plane. The Transactions of the Institute of Electronics and Communication Engineers of Japan. 1981, vol. 64E, p. 57–64.
  9. Megiddo N., Supowit K. On the Complexity of Some Common Geometric Location Problems. SIAM Journal on Computing. 1984, no. 13, p. 182–196.
  10. Zabudsky G. G., Nezhinsky I. V. [Solution to the problem of accommodation in Euclidean space with a prohibited area]. Byuleten Omskogo universiteta. 1999, no. 2, p. 17–19 (In Russ.).
  11. Morris J. G. Convergence of the Weiszfeld Algorithm for Weber Problems Using a Generalized “Distance” Function. Operations Research. 1981, vol. 29, no. 1, p. 37–48.
  12. Wesolowsky G. O, Love R. F. A Nonlinear Approximation Method for Solving a Generalized Rectangular Distance Weber Problem. Management Science. 1972, vol. 18, no. 11, p. 656–663.
  13. Kazakovtsev L. A., Adaptation of the Probability Changing Method for Weber Problem with an Arbitrary Metric. Facta Universitatis series Mathematics and Informatics, University of Nis. 2012, vol. 27, no. 2,  p. 239–254.
  14. Antavoshkin A. N., Kazakovtsev L. A. [Random search algorithm for the generalized Weber problem in discrete coordinates]. Informatika i sistemy upravleniya. 2013, vol. 1, p. 87–98 (In Russ.).
  15. Stanimirovic P. S., Ciric M., Kazakovtsev L. A., Osinuga I. A. Single-facility Weber Location Problem Based on the Lift Metric. Facta Universitatis series Mathematics and Informatics. 2012, vol. 27, no. 2, p. 175–190.
  16. Gugat M., Pfeiffer B. Weber problems with mixed distances and regional demand. Math. Meth. Oper. Res. 2007, Iss. 66, p. 419–449.
  17. Bischoff M., Fleischmann T., Klamroth K. The Multi-Facility Location-Allocation Problem with Polyhedral Barriers. Computers and Operations Research. 2009, no. 36, p. 1376–1392.
  18. Antamoshkin A. N., Saraev V. N. [Probability changing method]. Problemy sluchainogo poiska. 1988, Iss. 11, p. 26–34 (In Russ.).
  19. Reza A. W., Dimyati K., Noordin K. A., Kausar A. S. M. Z., Sarker Md. S. A Comprehensive Study of Optimization Algorithm for Wireless Coverage in Indoor Area. Optimization Letters. 2012. doi 10.1007/s11590-012-0543-z, Available at: http://link. springer.com/article/10.1007%2Fs11590-012-0543-z?LI=true (accessed 10.05.2013).
  20. Alp O., Erkut E. and Drezner Z. An Efficient Genetic Algorithm for the p-Median Problem. Annals of Operations Research. 2003, vol. 122, Iss. 1–4, p. 21–42.
  21. Antamoshkin A., Saraev V. On Definition of Informative Subsystem of Signs in the Pattern Recognition Problem. Computers and Artificial Intelligence. 1985, vol. 4, Iss. 3, p. 245–252.
  22. Antamoshkin A. Brainware for Searchal Pseudoboolean Optimization. Tr. оf Tenth Prague Conf. on Inf. Theory, Stat.Dec. Functions, Random Processes. Prague: Academia. 1987, vol. 10A-B, p. 203–206.
  23. Degterev A. S., Kanashkin F. V., Sumarokov A. D. [Generalization of genetic algorithms and algorithms of MIVER scheme]. Issledovano v Rossii. 2004, vol 7, p. 1658–1665. (In Russ.). Available at: http://zhurnal. ape.relarn.ru/articles/2004/153.pdf (accessed: 13.05.2013)
  24. Kazakovtsev L. A., Stupina A. A. [Parallel implementation of the probability changing method]. Sovremennye problem nauki i obrazovaniya. 2012, no. 4 (In Russ.). Available at: www.science-education.ru/104-6810 (accessed: 31.10.2012).
  25. Kazakovtsev L. A. Random Constrained Pseudo-Boolean Optimization Algorithm for Multiprocessor Systems and Clusters. ICUMT 2012, International Congress on Ultra-Modern Telecommunications. IEEE Press. S-Petersburg, 2012. P. 650–656.
  26. Kazakovtsev L. A. [Parallel algorithm of random search with adaptation for systems with distributed memory]. Sistemy upravleniya i informatsionnye tekhnologii. 2012, no. 3(49), p. 11–15 (In Russ.).
  27. Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik. 1959, vol. 1, p. 269–271.
  28. Beasley J. E. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society. 1990, vol. 41, no. 11, p. 1069–1072.
  29. Antamoshkin A. N., Kazakovtsev L. A. Random Search Algorithm for the p-Median Problem. Informatica (Ljubljana). 2013, vol. 37(1), p. 267–278.
  30. Resende M. G. C., Ribero C. C., Glover F., Marti R. Scatter Search and Path Relinking: Fundamentals, Advances and Applications. Handbook of Metaheuristics, 2nd edition, Gendreau M. and Potvin Y. (editors), Springer, 2010, p. 87–107.

Antamoshkin Alexander Nikolaevich – Dr. Sc., Professor, Siberian State Aerospace University named after academician M. F. Reshetnev. E-mail: oleslav@mail.ru

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