The modification of Little's algorithm for solving the well-known travelling salesman problem by branch-and-bound method is proposed. At each intermediate stage of the algorithm execution, a more exact lower bound is evaluated for all variants of the route which may be built on the basis of the current partial solution. Thanks to this, the rejection of unperspective variants becomes, as a rule, much more effective, especially when applied to the random asymmetrical distance matrix. The implementations of this modified algorithm are described with the depth-first and breadth-first search, and also with the depth-first search when an approximate route with the inaccuracy prescribed arbitrarily is searched. In a computing experiment, for each algorithm implementation, the values of constants a and c have been evaluated for the complexity function U(n) = a • c n that is the number of distance matrixes (decision tree nodes) processing by the algorithm. In any case the time of each node processing increases by 1,5-2 times while the time of processing the whole decision tree by the algorithm is significantly decreased.
Download file
Counter downloads: 130
- Title Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method
- Headline Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(20)
- Date:
- DOI
Keywords
computing experiment, travelling salesman problem, branch-and-bound method, вычислительный эксперимент, метод ветвей и границ, задача коммивояжёраAuthors
References
Костюк Ю. Л. Модифицированный алгоритм решения задачи коммивояжёра методом ветвей и границ. Программа и модуль с описанием класса: язык Паскаль в системе Delphi // Электронный ресурс: www.inf.tsu.ru/Decanat/Staff.nsf/people/KostjukJuL, 2013.
Хелд М., Карп Р. М. Применения динамического программирования к задачам упорядочивания // Кибернетический сборник. Вып. 9, старая серия. М.: Мир, 1964. С. 202-218.
Данциг Дж. Линейное программирование, его применения и обобщения: пер. с англ. М.: Прогресс, 1966.
Меламед И.И., Сергеев С. И., Сигал И. Х. Задача коммивояжёра. Точные алгоритмы // Автоматика и телемеханика. 1989. №10. С. 3-29.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: пер. с англ. М.: Мир, 1980. 478 с.
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.

Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 2(20).
Download full-text version
Download fileCounter downloads: 192