The Traveling Salesman Problem

    In this section you will be introduced to the traveling salesman problem (TSP). Genetic algorithms are commonly used to solve the traveling salesman problem, because the TSP is an NP-hard problem that generally cannot be solved by traditional iterative algorithms.

Understanding the Traveling Salesman Problem

    The traveling salesman problem involves a “traveling salesman” who must visit a certain number of cities. The task is to identify the shortest route for the salesman to travel between the cities. The salesman is allowed to begin and end at any city, but must visit each city once. The salesman may not visit a city more than once.

    This may seem like an easy task for a normal iterative program, however, consider the speed with which the number of possible combinations grows as the number of cities increases. If there are one or two cities, only one step is required. Three increases the possible routes to six. Table 6.2 shows how quickly these combinations grow.

Table 6.2: Number of Steps to Solve TSP with a Conventional Program

    The formula behind the above table is the factorial. The number of cities, n, is calculated using the factorial operator (!). The factorial of some arbitrary value n is given by n * (n – 1) * (n – 2) * ... * 3 * 2 * 1. As you can see from the above table, these values become incredibly large when a program must do a “brute force” search. The sample program that we will examine in the next section finds a solution to a 50-city problem in a matter of minutes. This is done by using a genetic algorithm, rather than a normal brute-force approach.