Solving the Traveling Salesman Problem Using Binary Decision Diagrams

Abstract

The traveling salesman problem is one of the most well known NP-hard problems. Binary decision diagrams can be used in the process of finding an exact solution to traveling salesman problems. Previous methods using binary decision diagrams did not evaluate how well such methods work. We implemented two of these methods and compared them to other methods by timing them on different problems. We found out that existing and well known methods generally are better than methods making use of binary decision diagrams as their search tree.