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
- PDF / 843,735 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 255 Views
1
·
Dynamic programming
·
Parallel
Introduction
Branch and Bound (Branch and Bound, BnB, branch & bound) is an approach advised for designing exact algorithms solving N P-hard combinatorial optimization and discrete problems. Branch and Bound was introduced by Land and Doig in 1960 [10]. Until the late 1970s, it was the state-of-the-art method for almost all big and complex problems that could not be solved by other techniques known at that time. And it is still used everywhere, where small improvement of solution leads to big rise in profits. Branch and Bound uses a tree search strategy to implicitly enumerate all possible solutions to a given problem, applying pruning rules to eliminate regions of the search space that cannot lead to a better solution [11]. In this article we are considering a minimization problem and the whole used terminology relates to it. In order to optimally solve the problem, Branch and Bound algorithm divides the whole set of solutions X into mutually exclusive and exhaustive subsets Xj , where j ∈ S = {1, 2, 3, . . . , s}. In every moment of its work, algorithm stores the best found solution so far xub and its value called upper bound and the set of subsets not yet analysed. Branch and Bound does not search these subsets to which it is assured that they do not contain optimal solution x∗ , so it is much more effective than an exhaustive search. Decision, if some subset should be analysed or not, is based on its bound and objective function value counted for currently best found solution K(xub ). For minimization problem, such bound is called lower bound and it is lower or equal to all objective function values evaluated for every element of related subset. It is marked as LB. If for a certain subset, the lower bound is equal or greater than the value of the best solution found so c IFIP International Federation for Information Processing 2016 Published by Springer International Publishing Switzerland 2016. All Rights Reserved K. Saeed and W. Homenda (Eds.): CISIM 2016, LNCS 9842, pp. 206–217, 2016. DOI: 10.1007/978-3-319-45378-1 19
Fast Branch and Bound Algorithm for the Travelling Salesman Problem
207
far, such subset is removed from the set of subsets not yet analysed and will be no more considered. A good lower bound is a basic requirement for an efficient Branch and Bound minimization procedure [12]. The idea of Travelling Salesman Problem, TSP for short, relies in visiting every city by the sale representative from the given set of n cities exactly once [9], starting from and returning to the home city. In this article we are considering a symmetric TSP, where the distance between two cities is the same in each opposite direction. We also assume that there is a direct connection from each node to every other one. Formally, this problem is described as a search for the shortest Hamiltonian cycle [7] in the complete and symmetric graph Kn = (Vn , En ) containing n = |Vn | nodes and m = |En | = n2 edges. Nodes are numbered from 1 to n. We assume without loss of generality tha
Data Loading...
