Solving the Traveling Salesman Problem in Microsoft Excel: An Educational Exercise
Stephen E. Hill
Weber State University, USA
Volume 4: 2010, pp. 69-86; ABSTRACT
The Traveling Salesman Problem (TSP) is an important problem in operations management. Applications of the TSP appear in routing problems, but also occur in a variety of other areas such as job-shop scheduling and even sports. In this article, an educational exercise is presented in which a small Traveling Salesman Problem instance is solved to optimality. The exercise is performed in the Microsoft Excel spreadsheet software with the default Solver Add-in. The article is believed to be the first demonstration of the use of Excel and Solver to solve the Traveling Salesman Problem while using the subtour elimination constraints and variables of Miller, Tucker, and Zemlin. Suggestions for the coverage of topics related to the Traveling Salesman Problem and a sample problem suitable for a homework assignment or examination are also provided.
.jpg)
