The travelling salesman problem: improved lower bound in the branch-and-bound method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).

In a previous article, the author describes the implementation of Little's algorithm for solving the travelling salesman problem by the branch-and-bound method and gives a new modified algorithm where an additional transformation of the distance matrix is used at each step of the solution. This improves the lower bound for the exact solution and speeds up its work, but only in the case of non-symmetric matrices. In the present article, a method is described to further improve the lower bound, especially in the case of symmetric matrices. A new algorithm based on it is constructed. With the help of a computer simulation, some estimates of the constants in the formulas for the algorithm complexity are obtained for three types of distance matrices: 1) non-symmetric matrices with random distances, 2) matrices with the Euclidean distances between random points in the square, and 3) non-symmetric matrices with random distances satisfying the triangle inequality.
Download file
Counter downloads: 367
  • Title The travelling salesman problem: improved lower bound in the branch-and-bound method
  • Headline The travelling salesman problem: improved lower bound in the branch-and-bound method
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(22)
  • Date:
  • DOI
Keywords
задача коммивояжёра, метод ветвей и границ, вычислительный эксперимент, travelling salesman problem, branch-and-bound method, computing experiment
Authors
References
Костюк Ю. Л. Модифицированный алгоритм решения задачи коммивояжера методом ветвей и границ с улучшенной нижней границей. Программа и модуль с описанием класса: язык Паскаль в системе Delphi. 2013, август. Электронный ресурс: www.inf.tsu.ru/ Decanat/Staff.nsf/people/KostjukJuL.
Костюк Ю. Л. Модифицированный алгоритм решения задачи коммивояжера методом ветвей и границ. Версия 2. Программа и модуль с описанием класса: язык Паскаль в системе Delphi. 2013, июль. Электронный ресурс: www.inf.tsu.ru/Decanat/Staff.nsf/ people/KostjukJuL.
Хелд М., Карп Р. М. Применения динамического программирования к задачам упорядочивания // Киб. сборник, старая серия. М.: Мир, 1964. Вып. 9. С. 202-218.
Данциг Дж. Линейное программирование, его применения и обобщения: пер. с англ. М.: Прогресс, 1966.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 536 с.
Little J. D. C., Murty K. G., Sweeney D. W., and Karel C. An algorithm for the Traveling Salesman Problem // Operations Research. 1963. No. 11. P. 972-989.
Костюк Ю. Л. Эффективная реализация алгоритма решения задачи коммивояжера методом ветвей и границ // Прикладная дискретная математика. 2013. №2 (20). С. 78-90.
 The travelling salesman problem: improved lower bound in the branch-and-bound method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).
The travelling salesman problem: improved lower bound in the branch-and-bound method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).