tsp_lau, a Fortran90 code which implements a heuristic based on the Christofides algorithm, for solution of the traveling salesman problem (TSP), by Hang Tong Lau. Graphics files are created for processing by gnuplot().
The traveling salesman problem is given a list of cities, and seeks the shortest round trip that visits each location exactly once. The obvious method of solution, to compute the length of every possible path, is not much worse than the best known method of solution, in terms of the amount of computing required to find the exact answer. However, there are heuristic methods that can find a reasonable approximation to the answer for most problems, in a much shorter amount of time.
The information on this web page is distributed under the MIT license.
tsp_lau is available in a Fortran90 version.
cities, a Fortran90 code which handles various problems associated with a set of "cities" on a map.
cities, a dataset directory which contains a number of city distance datasets.
floyd, a Fortran90 code which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.
lau_np, a Fortran90 code which includes heuristic approaches to certain NP-complete problems, including the traveling salesman problem, the K-center problem and the K-median problem.
toms456, a Fortran77 library which handles the routing problem, connecting some nodes in a network.
tsp, a dataset directory which contains test data for the traveling salesperson problem (TSP) including the AT&T 48 state capital test, and Dantzig's 42 city test;
tsp_anneal, a Fortran90 code which reads a table of city locations, and uses simulated annealing to solve the traveling salesperson problem (TSP), based on a Numerical Recipes code. Graphics files are created for processing by gnuplot().
tsp_att48, a Fortran90 code which returns the (x,y) coordinates of the cities that constitute the AT&T 48 state challenge for the Traveling Salesman Problem (TSP). Graphics files are created for processing by gnuplot().
tsp_brute, a Fortran90 code which reads a table of city locations and solves the traveling salesperson problem (TSP), using brute force.
tsp_dantzig42, a Fortran90 code which returns the (x,y) coordinates of the cities that constitute the Dantzig 42 state challenge for the Traveling Salesman Problem (TSP). The minimal tour is known to have length 699. Graphics files are created for processing by gnuplot().
tsp_display, a Fortran90 code which displays the solution of a Traveling Salesman Problem (TSP). Graphics files are created for processing by gnuplot().
tsp_io, a Fortran90 code which reads or writes files from the TSPLIB collection of traveling salesman problems (TSP).
tsp_nearest, a Fortran90 code which is given a table of city locations, and solves a small traveling salesperson problem (TSP) using the nearest neighbor algorithm. It picks a starting city at random, and then successively visits the nearest unvisited city.
Hang Tong Lau