Перевод названия: Application of the probability changing method for optimal location problems on a network
Тип публикации: статья из журнала
Год издания: 2014
Ключевые слова: discrete optimization, P-median problem, methods of random search, location problem, дискретная оптимизация, p-медианная задача, методы случайного поиска, задачи размещения
Аннотация: Рассматривается p-медианная задача оптимального размещения на графе (сети), являющаяся популярной моделью как в логистических задачах (оптимальное размещение транспортной, телекоммуникационной и иной инфраструктуры), так и опосредованно в задачах кластерного анализа, распознавания образов, в теории оценивания. Цель p-медианной задаПоказать полностьючи на графе (сети) заключается в нахождении определенного числа вершин (узлов) таких, чтобы суммарное расстояние от всех узлов сети до ближайшей из выбранных вершин (узлов) было минимальным. Для приближенного решения рассматриваемой неразрешимой (в общем случае) за полиномиальное время задачи предложен эвристический алгоритм, основанный на идеях метода изменяющихся вероятностей, являющегося методом случайного поиска с адаптацией. Идея алгоритма заключается в случайном выборе вершин в соответствии с заданными вероятностями выбора каждой из вершин и изменении этих вероятностей для каждой из выбранных вершин и вершин в некоторой ее окрестности в зависимости от достигнутого значения целевой функции (т. е. в зависимости от суммарного расстояния от каждой из вершин графа до ближайшей из выбранных вершин). При создании алгоритма для p-медианных задач с большой размерностью и вычислительной сложностью ставится задача оптимального использования вычислительных мощностей. Эффективность алгоритма подтверждена экспериментальной проверкой на тестовых примерах из библиотеки ORLIB. Также приведены результаты работы комбинированного алгоритма - комбинации предложенного алгоритма с процедурой локального поиска для решения данной задачи. Экспериментально показано, что результаты такой комбинации превосходят результаты оригинального многократных запусков алгоритма, реализующего локальный поиск из случайным образом выбранных вершин. Кроме того, в работе экспериментально показано, что для небольших задач алгоритм способен получить точное решение задачи. 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.
Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева
Выпуск журнала: № 5
Номера страниц: 10-19
ISSN журнала: 18169724
Место издания: Красноярск
Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева