tsp_moler


tsp_moler, an Octave code which tries to optimize the traveling salesperson problem (TSP), written by Cleve Moler.

The code depends in part on randomization, and so the results are likely to vary each time it is run. Moler reports that the shortest itinerary he found had a length of 10818 miles, and is likely an optimum circuit.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

tsp_moler is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

tsp_moler_test

cities, an Octave code which handles various problems associated with a set of "cities" on a map.

tsp_brute, an Octave code which is given a city-to-city distance table, and solves a (small) traveling salesperson problem (TSP), using brute force.

tsp_descent, an Octave code which is given a city-to-city distance table, chooses an initial tour at random, and then tries simple variations, seeking to quickly find a tour of lower cost for the traveling salesperson problem (TSP).

tsp_greedy, an Octave code which is given a city-to-city distance table,, and solves a small traveling salesperson problem (TSP) using the greedy algorithm. It picks a starting city at random, and then successively visits the nearest unvisited city.

tsp_random, an Octave code which is given a city-to-city distance table, seeks a solution of the Traveling Salesperson Problem (TSP), by randomly generating round trips that visit every city, returning the tour of shortest length.

Reference:

  1. Cleve Moler,
    USA Traveling Salesman Tour,
    Posted 17 September 2018,
    logs.mathworks.com/cleve/2018/09/17/usa-traveling-salesman-tour/?s_tid=srchtitle_traveling%20salesman_1
  2. Great circle distance matrix between pairs of cities,
    https://en.wikipedia.org/wiki/Great-circle_distance.

Source Code:


Last revised on 04 July 2023.