Fast Branch and Bound Algorithm for the Travelling Salesman Problem

Radosław Grymin (1) , Szymon Jagiełło (1)

1 Wroclaw University of Science and Technology

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.

Mots clés: Branch-and-Bound; Dynamic programming; Parallel algorithm

Domaines: Informatique [cs]; Sciences de l'information et de la communication

Radosław Grymin, Szymon Jagiełło. Fast Branch and Bound Algorithm for the Travelling Salesman Problem. 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⟩. ⟨hal-01637523⟩