Preview

Труды Института системного программирования РАН

Расширенный поиск

Метрическая задача коммивояжера: экспериментальное исследование Парето-оптимальных алгоритмов

https://doi.org/10.15514/ISPRAS-2017-29(4)-8

Полный текст:

Аннотация

Задача коммивояжера - одна из важнейших задач теории графов и комбинаторной оптимизации, суть которой состоит в нахождении гамильтонова цикла наименьшей длины. Разработка методов для решения задачи коммивояжера осуществляется на протяжении многих лет, и, по-прежнему, остается актуальной, поскольку задача является NP-трудной. Решения применяются, в основном, для минимизации производственных и логистических затрат и издержек. В работе рассматривается частный случай общей постановки задачи коммивояжера, в котором выполняется свойство метрики - метрическая задача коммивояжера. Целью данной работы является определение группы Парето оптимальных алгоритмов решения метрической задачи коммивояжера по критериям времени работы и точности решения в ходе экспериментального исследования. В связи с тем, что задача коммивояжера является NP-трудной, в работе рассматриваются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. В статье представлено краткое описание используемых алгоритмов решения метрической задачи коммивояжера, указаны их априорные точностные и временные оценки. Приведено описание плана эксперимента. Данными для экспериментального исследования послужили два набора из открытой библиотеки данных для метрической задачи коммивояжера, основанные на высоко-интегральных вычислительных схемах (VLSI Data Sets) и географических координатах (высоте и широте) городов в различных странах (National TSPs). В результате исследований выявлены оптимальные по Парето алгоритмы для наборов данных различных размерностей - до 700 тысяч вершин. Для каждого N в число Парето-оптимальных алгоритмов входят некоторые из алгоритмов MC, SC, NN, DENN, CI, GRD, CI + 2-Opt, GRD + 2-Opt, CHR и LKH. Приведена таблица, содержащая информацию о результатах экспериментов.

Об авторах

С. М. Авдошин
Национальный исследовательский университет “Высшая школа экономики”
Россия


Е. Н. Береснева
Национальный исследовательский университет “Высшая школа экономики”
Россия


Список литературы

1. Applegate, D., Bixby, R., Chvatal, V., Cook, W. The Traveling Salesman Problem: A Computational Study, Princeton: Princeton University Press, 2011.

2. Beresneva (Chirkova), E.N., Avdoshin, S.M. Pareto-optimal Algorithms for Metric TSP: Experimental Research. International Journal of Open Information Technologies , 5, № 5, pp. 16-24, 2017, ISSN: 2307-8162.

3. Department of Combinatorics and Optimization at the University of Waterloo. Status of VLSI Data Sets. University of Waterloo (web-site). Доступно по ссылке: http://www.math.uwaterloo.ca/tsp/vlsi/summary.html, дата обращения 29.04.2017.

4. University of Waterloo. National Travelling Salesman Problems. UWaterloo, (web-site). Доступно по ссылке: http://www.math.uwaterloo.ca/tsp/world/countries.html, дата обращения 16.04.2017.

5. Flood, M.M. The traveling-salesman problem. Operation research, vol. 4, pp. 61-75, 1956.

6. Rosenkrantz, D. Stearns, R., Lewis II, P. An analysis of several heuristics for the traveling salesman problem, 6, pp. 563-581, 1977.

7. Cook, W.J. Combinatorial optimization, New York: Wiley, 1998.

8. Hahsler, M., Hornik, K. TSP - Infrastructure for the Traveling Salesperson Problem, 23, № 2, 2007.

9. Christofides, N. Graph theory - An Algorithmic Approach, New York: Academic Press, 1974.

10. Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Administration, CMU, 1976.

11. Buchin, K. Space-Filling Curves. Organizing Points Sets: Space-Filling Curves, Delaunay Tessellations of Random Point Sets, and Flow Complexes, Berlin, Free University of Berlin, 2007, pp. 5-30.

12. Bartholdi, J., Platzman, L., Collins R., Warden, W. A Minimal Technology Routing System for Meals on Wheels, 13, № 3, pp. 1-8, 1983.

13. Aarts, E., Lenstra, J. Local Search in Combinatorial Optimization, Princeton, New Jersey: Princeton University Press, 2003.

14. Helsgaun, K. An effective implementation of the Lin-Kernighan traveling salesman heuristic, EJOR, 12, pp. 106-130, 2000.

15. Helsgaun, K. LKH (web-site). Доступно по ссылке: http://www.akira.ruc.dk/~keld/research/LKH, дата обращения 24.02.2017.

16. Gorkemli, B., Karaboga, D. Quick Combinatorial Artificial Bee Colony -qCABC- Optimization Algorithm for TSP, 1, № 5, 2013.


Для цитирования:


Авдошин С.М., Береснева Е.Н. Метрическая задача коммивояжера: экспериментальное исследование Парето-оптимальных алгоритмов. Труды Института системного программирования РАН. 2017;29(4):123-138. https://doi.org/10.15514/ISPRAS-2017-29(4)-8

For citation:


Avdoshin S.M., Beresneva E.N. The Metric Travelling Salesman Problem: The Experiment on Pareto-optimal Algorithms. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(4):123-138. https://doi.org/10.15514/ISPRAS-2017-29(4)-8

Просмотров: 275


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)