An Iterated Local Search Approach for Finding Provably Good Solutions for Very Large TSP Instances Export

@incollection{citeulike:3300101, abstract = {Meta-heuristics usually lack any kind of performance guarantee and therefore one cannot be certain whether the resulting solutions are (near) optimum solutions or not without relying on additional algorithms for providing lower bounds (in case of minimization). In this paper, we present a highly effective hybrid evolutionary local search algorithm based on the iterated Lin-Kernighan heuristic combined with a lower bound heuristic utilizing 1-trees. Since both upper and lower bounds are improved over time, the gap between the two bounds is minimized by means of effective heuristics. In experiments, we show that the proposed approach is capable of finding short tours with a gap of 0.8\% or less for TSP instances up to 10 million cities. Hence, to the best of our knowledge, we present the first evolutionary algorithm and meta-heuristic in general that delivers provably good solutions and is highly scalable with the problem size. We show that our approach outperforms all existing heuristics for very large TSP instances.}, author = {Merz, Peter and Huhse, Jutta}, citeulike-article-id = {3300101}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-87700-4_92}, doi = {10.1007/978-3-540-87700-4_92}, journal = {Parallel Problem Solving from Nature – PPSN X}, keywords = {approximation, bound, evolutionary-computation, heuristic, hybridization, lin-kernighan, local-search, metaheuristic, travelling-salesman-problem}, pages = {929--939}, posted-at = {2008-09-20 20:28:38}, priority = {2}, title = {An Iterated Local Search Approach for Finding Provably Good Solutions for Very Large TSP Instances}, url = {http://dx.doi.org/10.1007/978-3-540-87700-4_92}, year = {2008} }

TY - CHAP ID - citeulike:3300101 L3 - citeulike-article-id:3300101 N2 - Meta-heuristics usually lack any kind of performance guarantee and therefore one cannot be certain whether the resulting solutions are (near) optimum solutions or not without relying on additional algorithms for providing lower bounds (in case of minimization). In this paper, we present a highly effective hybrid evolutionary local search algorithm based on the iterated Lin-Kernighan heuristic combined with a lower bound heuristic utilizing 1-trees. Since both upper and lower bounds are improved over time, the gap between the two bounds is minimized by means of effective heuristics. In experiments, we show that the proposed approach is capable of finding short tours with a gap of 0.8% or less for TSP instances up to 10 million cities. Hence, to the best of our knowledge, we present the first evolutionary algorithm and meta-heuristic in general that delivers provably good solutions and is highly scalable with the problem size. We show that our approach outperforms all existing heuristics for very large TSP instances. JF - Parallel Problem Solving from Nature – PPSN X EP - 939 TI - An Iterated Local Search Approach for Finding Provably Good Solutions for Very Large TSP Instances SP - 929 KW - approximation KW - bound KW - evolutionary-computation KW - heuristic KW - hybridization KW - lin-kernighan KW - local-search KW - metaheuristic KW - travelling-salesman-problem AU - Merz, Peter AU - Huhse, Jutta PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-87700-4_92 ER -