Heuristic Solution of Traveling Salesman Problem

TSP_LAU is a FORTRAN90 library 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.


TSP_LAU is available in a FORTRAN90 version.

Related Data and Programs:

CITIES, a FORTRAN90 library 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 library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

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

TSP_IO, a FORTRAN90 library which reads or writes files in the TSP format used for examples of the traveling salesperson problem.


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:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.

Last revised on 18 April 2014.