IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix
Abstract
The problem of the solution of asymmetric traveling salesman problem with sparse matrix, based on branch and bound techniques with linear assignment problems relaxation, is considered. Inheritance of the result’s data of previous problems and its reoptimization allows to decreasing time of reception of the new solution on branch’s tree path. The reoptimization algorithm, based on a Shortest Augmenting Path method, is offered.
About the Authors
M. P. Revotjuk
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
M. K. Qaraleh
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
P. M. Batura
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
References
1. Miller D., Pekny J. // Science. 1991. Vol. 251. P. 754-761.
2. Mahshid A.F., Rosnah M.Y. // European Journal of Scientific Research. 2009. Vol. 29. № 3. P. 349-359.
3. Ревотюк М.П., Батура П.М., Полоневич А.М. // Докл. БГУИР. 2011. № 3 (57). C. 56-62.
4. Jonker R., Volgenant A. // Computing. 1987. Vol. 38. P. 325-340.
5. Ревотюк М.П., Кароли М.К., Батура П.М. //Докл. БГУИР. 2013. № 5 (75). C. 30-36.
Review
For citations:
Revotjuk M.P., Qaraleh M.K., Batura P.M. IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix. Doklady BGUIR. 2013;(7):25-31. (In Russ.)
Views:
5308
JATS XML
Email this article 