Fast Branch and Bound Algorithm for the Travelling Salesman Problem

摘要

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 paralleliza-tion of Branch and Bound scheme. Proposed approaches are compared with primary algorithms.