tsp_lau, a FORTRAN90 code which implements a heuristic algorithm for solution of the traveling salesman problem, by Hang Tong Lau.

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 computer code and data files made available on this web page are distributed under the MIT license


tsp_lau is available in a FORTRAN90 version.

Related Data and Programs:

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_BRUTE, a FORTRAN90 code which reads a file of city-to-city distances and solves the traveling salesperson problem, using brute force.



Hang Tong Lau


  1. Nicos Christofides,
    Worst-case analysis of a new heuristic for the traveling salesman problem,
    Management Science Research Report Number 388,
    Carnegie-Mellon University, 1976.
  2. Hang Tong Lau,
    Combinatorial Heuristic Algorithms in FORTRAN,
    Springer Verlag, 1986,
    ISBN: 3540171614,
    LC: QA402.5 L37.

Source Code:

Last revised on 10 September 2020.