Tour merging via tree decomposition

Abstract

The TSP and VRP are well known optimization problems. In this thesis we evaluate the use of a dynamic programming algorithm on a tree decomposition of a graph, with the goal to improve the solutions to these problems given by several heuristics. The used heuristics are the LKH algorithm, the savings algorithm and the sweep algorithm.