Fast Branch and Bound Algorithm for the Travelling Salesman Problem
| Autor: | Radosław Grymin, Szymon Jagiełło |
|---|---|
| Přispěvatelé: | Wroclaw University of Science and Technology, Khalid Saeed, Władysław Homenda, TC 8 |
| Rok vydání: | 2016 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization 021103 operations research Branch and bound Computer science [SHS.INFO]Humanities and Social Sciences/Library and information sciences Branch and price Branch-and-Bound 0211 other engineering and technologies Parallel algorithm 02 engineering and technology Minimum spanning tree Dynamic programming Upper and lower bounds Travelling salesman problem 020901 industrial engineering & automation [INFO]Computer Science [cs] Branch and cut Algorithm |
| Zdroj: | Computer Information Systems and Industrial Management ISBN: 9783319453774 CISIM Lecture Notes in Computer Science 15th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM) 15th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2016, Vilnius, Lithuania. pp.206-217, ⟨10.1007/978-3-319-45378-1_19⟩ |
| DOI: | 10.1007/978-3-319-45378-1_19 |
| Popis: | Part 4: Optimization, Tuning; International audience; New strategies are proposed for implementing algorithms based on Branch and Bound scheme. Those include two minimal spanning tree lower bound modifications, a design based on the fact that edges in the optimal tour can never cross in the euclidean TSP and parallelization of Branch and Bound scheme. Proposed approaches are compared with primary algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|