A polynomial algorithm solving discrete Weber problem for cycle and for finite set of location positions is presented. The algorithm is based on the dynamic programming idea. The comparison of action times of the given algorithm and of an integer linear programming model, which was realized in IBM ILOG CPLEX, is carried out.
Download file
Counter downloads: 98
- Title Exact algorithm for solving discrete Weber problem for a cycle
- Headline Exact algorithm for solving discrete Weber problem for a cycle
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(22)
- Date:
- DOI
Keywords
задача Вебера, простой цикл, динамическое программирование, точный алгоритм, Weber problem, cycle, dynamic programming, exact algorithmAuthors
References
Шангин Р. Э. Разработка и анализ алгоритмов для задачи Вебера // Проблемы оптимизации и экономические приложения. Омск, 2012. С. 121-122.
Panyukov А. V. and Pelzwerger B. V. Polynomial algorithms to finite Weber problem for a tree network // J. Comput. Appl. Math. 1991. V.35. P. 291-296.
Панюков А. В., Пельцвергер Б. Ф., Шафир А. Ю. Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности // Автоматика и телемеханика. 1990. №9. С. 153-162.
Сергеев С. А. Квадратичная задача о назначениях I // Автоматика и телемеханика. 1999. №8. С. 127-147.
Панюков А. В. Модели и методы решения задач построения и идентификации геометрического размещения: дис.. д-ра физ.-мат. наук. Челябинск, 1999. 260 с.
Панюков А.В., Пельцвергер Б Ф. Оптимальное размещение дерева в конечном множестве // Журн. вычисл. математики и матем. физики. 1988. Т. 28. №2. С. 618-620.
Шангин Р. Э. Исследование эффективности приближенных алгоритмов решения одного частного случая задачи Вебера // Экономика, статистика и информатика. Вестник УМО. 2012. №1. С. 163-168.
Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. 1978. №6. С. 67-70.
Zabudsky G. G. and Filimonov D. V. An algorithm for minimax location problem on tree with maximal distances // Proc. Second Intern. Workshop "Discrete Optimization Methods in Production and Logistics" (D0M2004). Omsk, 2004. P. 81-85.
Забудский Г. Г., Филимонов Д. В. О минимаксной и минисуммной задачах размещения на сетях // Труды XII Байкальской Междунар. конф. «Методы оптимизации и их приложения». Омск, 2001. С. 150-155.
Филимонов Д. В. Решение дискретной минимаксной задачи размещения на древовидной сети // Материалы ежегодного научного семинара аспирантов. Омск, 2003. С. 58-61.
Exact algorithm for solving discrete Weber problem for a cycle | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).
Download full-text version
Download fileCounter downloads: 337