The Traveling Salesperson Problem

The Traveling Salesperson Problem

The “traveling salesperson” problem is a classic route selection problem where a sequence of locations has to be traveled to, and a return must be made to the starting location. Each location can only be traveled once. In the above example, a salesperson, starting at point 1, must visit six locations (1 to 6) and return to the starting point. The first route (1-4-2-5-6-3-1), with a total length of 62 km, is an 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 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.