# tsp_moler

tsp_moler, a Python 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.

### Languages:

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

### Related Data and Programs:

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

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

tsp_descent, a Python 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, a Python 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, a Python 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:

• state_capitals_48_ll.csv, two letter state abbreviation, latitude and longitude of state capital, for each of the "lower 48" US states.

Last revised on 14 March 2023.