The Traveling Salesperson Problem

The Traveling Salesperson Problem

The “traveling salesperson” problem is a classic route selection problem where a sequence of locations have to be traveled to and a return must be made to the starting location. Each location can only be traveled once to. On the above example, a salesperson, starting at point 1 has to visit six locations (1 to 6) and must come back to the starting point. The first route (1-4-2-5-6-3-1), with a total length of 62 km, is acceptable solution but not the best. The second route (1-2-5-4-6-3-1) represents a much better solution as the total distance, 48 km, is less than for the first route. This example assumes Euclidean distances and an isotropic space, but in reality the solution may be different considering the configuration of transport infrastructures making some locations more accessible than others. These types of problems are usually solved through combinational optimization, which is a branch of operations research.