Traveling Sales Person - Family of functions - pgRouting Manual (3.0)

Problem Definition

The travelling salesman problem (TSP) or travelling salesperson problem asks the following question:

Given a list of cities and the distances between each pair of cities, which is the shortest possible route that visits each city exactly once and returns to the origin city?

Origin

The traveling sales person problem was studied in the 18th century by mathematicians

Sir William Rowam Hamilton and Thomas Penyngton Kirkman .

A discussion about the work of Hamilton & Kirkman can be found in the book Graph Theory (Biggs et al. 1976) .

• ISBN-13: 978-0198539162

• ISBN-10: 0198539169

It is believed that the general form of the TSP have been first studied by Kalr Menger in Vienna and Harvard. The problem was later promoted by Hassler, Whitney & Merrill at Princeton. A detailed description about the connection between Menger & Whitney, and the development of the TSP can be found in On the history of combinatorial optimization (till 1960)

Characteristics

• The travel costs are symmetric:

  • traveling costs from city A to city B are just as much as traveling from B to A.

• This problem is an NP-hard optimization problem.

• To calculate the number of different tours through \(n\) cities:

  • Given a starting city,

  • There are \(n-1\) choices for the second city,

  • And \(n-2\) choices for the third city, etc.

  • Multiplying these together we get \((n-1)! = (n-1) (n-2) . . 1\) .

  • Now since our travel costs do not depend on the direction we take around the tour:

    • this number by 2

    • \((n-1)!/2\) .

pgRouting Implementation

pgRouting’s implementation adds some extra parameters to allow some exit controls within the simulated annealing process.

• max_changes_per_temperature :

  • Limits the number of changes in the solution per temperature

  • Count is reset to \(0\) when temperature changes

  • Count is increased by :math: 1 when solution changes

• max_consecutive_non_changes :

  • Limits the number of consecutive non changes per temperature

  • Count is reset to \(0\) when solution changes

  • Count is increased by :math: 1 when solution changes

• max_processing_time :

  • Limits the time the simulated annealing is performed.

Solution = initial_solution;

temperature = initial_temperature;
WHILE (temperature > final_temperature) {

    DO tries_per_temperature times {
        newSolution = neighbour(solution);
        If Probability(E(solution), E(newSolution), T) >= random(0, 1)
            solution = newSolution;

        BREAK DO WHEN:
            max_changes_per_temperature is reached
            OR max_consecutive_non_changes is reached
    }

    temperature = temperature * cooling factor;
    BREAK WHILE WHEN:
        no changes were done in the current temperature
        OR max_processing_time has being reached
}

Output: the best solution found

Choosing parameters

There is no exact rule on how the parameters have to be chose, it will depend on the special characteristics of the problem.

• If the computational time is crucial, then limit execution time with max_processing_time .

• Make the tries_per_temperture depending on the number of cities ( \(n\) ), for example:

  • Useful to estimate the time it takes to do one cycle: use 1

    • this will help to set a reasonable max_processing_time

  • \(n * (n-1)\)

  • \(500 * n\)

• For a faster decreasing the temperature set cooling_factor to a smaller number, and set to a higher number for a slower decrease.

• When for the same given data the same results are needed, set randomize to false .

  • When estimating how long it takes to do one cycle: use false

A recommendation is to play with the values and see what fits to the particular data.

Description of the Control Parameters

The control parameters are optional, and have a default value.

See Also

References

• Wikipedia: Traveling Salesman Problem

• Wikipedia: Simulated annealing

Indices and tables

• Index

• Search Page