ABSTRACT
In this chapter, we present the traveling salesman problem and demonstrate how SAS/OR® can be applied to solve the problem to optimality.
6.1.1 Concept of TSP
The traveling salesman problem (TSP) is one of the most widely studied integer programming problems and can be described as follows. Before visiting n distinct cities and then returning home, a salesman wants to determine the sequence of the travel so that the overall travel distance is minimized while visiting each city no more than once. Although the TSP is conceptually simple, it is difficult to obtain an optimal solution. In an n-city situation, any permutation of n cities yields a possible solution. As a consequence, n! possible tours must be evaluated in the search space. By introducing decision variables xij to represent the tour of the salesman from city i to city j, the TSP can be formulated as shown in Model 6.1.1.
