IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Educational institution «Belarusian State University of Informatics and Radioelectronics»
2019-06-01
|
| Series: | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| Subjects: | |
| Online Access: | https://doklady.bsuir.by/jour/article/view/234 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839568060019638272 |
|---|---|
| author | M. P. Revotjuk M. K. Qaraleh P. M. Batura |
| author_facet | M. P. Revotjuk M. K. Qaraleh P. M. Batura |
| author_sort | M. P. Revotjuk |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e4dba45b87e04da3a2cdb9bddbd22ade |
| institution | Matheson Library |
| issn | 1729-7648 |
| language | Russian |
| publishDate | 2019-06-01 |
| publisher | Educational institution «Belarusian State University of Informatics and Radioelectronics» |
| record_format | Article |
| series | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| spelling | doaj-art-e4dba45b87e04da3a2cdb9bddbd22ade2025-08-04T17:38:12ZrusEducational institution «Belarusian State University of Informatics and Radioelectronics»Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki1729-76482019-06-01072531233IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrixM. P. Revotjuk0M. K. Qaraleh1P. M. Batura2Белорусский государственный университет информатики и радиоэлектроникиБелорусский государственный университет информатики и радиоэлектроникиБелорусский государственный университет информатики и радиоэлектроники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.https://doklady.bsuir.by/jour/article/view/234задача коммивояжераметод ветвей и границвычислительная сложность |
| spellingShingle | M. P. Revotjuk M. K. Qaraleh P. M. Batura IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki задача коммивояжера метод ветвей и границ вычислительная сложность |
| title | IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix |
| title_full | IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix |
| title_fullStr | IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix |
| title_full_unstemmed | IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix |
| title_short | IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix |
| title_sort | implementation the branch and bound method for solving the traveling salesman problem with sparse matrix |
| topic | задача коммивояжера метод ветвей и границ вычислительная сложность |
| url | https://doklady.bsuir.by/jour/article/view/234 |
| work_keys_str_mv | AT mprevotjuk implementationthebranchandboundmethodforsolvingthetravelingsalesmanproblemwithsparsematrix AT mkqaraleh implementationthebranchandboundmethodforsolvingthetravelingsalesmanproblemwithsparsematrix AT pmbatura implementationthebranchandboundmethodforsolvingthetravelingsalesmanproblemwithsparsematrix |