Метрическая задача коммивояжера: экспериментальное исследование Парето-оптимальных алгоритмов
https://doi.org/10.15514/ISPRAS-2017-29(4)-8
Аннотация
Об авторах
С. М. Авдошин
Национальный исследовательский университет “Высшая школа экономики”
Россия
Россия
Е. Н. Береснева
Национальный исследовательский университет “Высшая школа экономики”
Россия
Россия
Список литературы
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
Послать статью по эл. почте 