Версии алгоритма «луковой шелухи» для псевдогеометрической версии задачи коммивояжёра с малой дисперсией
Аннотация
Мы продолжаем рассматривать псевдогеометрическую задачу коммивояжера. В частности, мы рассматриваем несколько вспомогательных алгоритмов, необходимых для реализации различных версий алгоритма «луковой шелухи». Мы не нашли в~литературе точного описания конкретных версий алгоритмов для геометрической версии (впрочем, в этом нет необходимости,
поскольку исходные версии этих алгоритмов необходимо реализовать для псевдогеометрической версии), поэтому мы начинаем работу с геометрической версии.
Случайная генерация данных для вычислительных экспериментов соответствовала решаемой проблеме:
для каждого из нескольких вариантов размерности задачи были проведены некоторые вычислительные эксперименты со случайно сгенерированными входными данными. Были рассчитаны следующие характеристики полученных результатов:
среднее количество результирующих контуров для геометрического варианта;
отношение решения с контурами к оптимальному решению;
отношение решения псевдогеометрической версии, соответствующее порядку точек геометрической версии, к геометрическому решению.
Полученные результаты вычислительных экспериментов в целом приблизительно соответствуют ожидаемым значениям.
Литература
Kluwer Academic Publishers, 2002.
2. B. Melnikov and E. Melnikova, “On the Classical Version of the Branch and Bound Method,” Computer
tools in education, no. 1, pp. 21–44, 2021 (in Russian); doi:10.32603/2071-2340-2021-1-21-45
3. B. Melnikov and E. Melnikova, “About the classical version of the branch and bound method,” Computer
tools in education, no. 2, pp. 41–58, 2022 (in Russian); doi:10.32603/2071-2340-2022-2-41-58
4. B. Melnikov, “On the object-oriented implementation of the branch and bound method for the traveling
salesman problem. Part I,” Modern information technologies and IT education, vol. 18, no. 2,
pp. 287–299, 2022 (in Russian); doi:10.25559/SITIT0.18.202202.287-299
5. B. Melnikov, “On the object-oriented implementation of the branch and bound method for the traveling
salesman problem. Part II,” Modern information technologies and IT education, vol. 18, no. 3,
pp. 644–654, 2022 (in Russian); doi:10.25559/SITITO.18.202203.644-654
6. S. Makarkin and B. Melnikov, “Geometric methods for solving the pseudo-geometric version of the
traveling salesman problem,” Stochastic optimization in computer science, vol. 9, no. 2, pp. 54–72, 2013
(in Russian).
7. G. Bulynin, B. F. Melnikov, V. Y. Meshchanin, and Y. Y. Terentyeva, “Optimization problem, arising in
the development of high-dimensional communication networks, and some heuristic methods for solving
them,” Informatization and communication, no. 1, pp. 34–40, 2020 (in Russian); doi:10.34219/2078-
8320-2020-11-1-34-40
8. M. Lagutin, Visual mathematical statistics, Moscow: BINOM — Laboratory of Knowledge, 2009 (in
Russian).
9. D. Johnson and L. McGeoch, “Experimental analysis of heuristics for the STSP,” in G. Gutin and
A.Punnen, eds. The traveling salesman problem and its variations, Dordrecht, Netherlands: Kluwer
Academic Publishers, pp. 369–443, 2002.
10. Т. Ralphs, M. Saltzman, and M. Wiecek, “An improved algorithm for solving biobjective integer programs,”
Annals of Operations Research, vol. 147, no. 1, pp. 43–70, 2006; doi:10.1007/s10479-006-0058-z
Материал публикуется под лицензией:
