toms456

toms456, a Fortran77 code which implements ACM toms algorithm 456, for the routing problem.

The text of many ACM TOMS algorithms is available online through ACM: https://www.acm.org/pubs/calgo or NETLIB: https://www.netlib.org/toms/index.html.

Usage:

call routng ( n, p, sn, en, m, d, l, r )
N is the number of nodes,
P is the node number index, but on output is replaced by the optimal connection,
SN and EN are the start and end nodes,
M is the order of the distance matrix,
D is the distance matrix,
L is output as the length of the shortest connection,
R is the number of runs (that is, the number of iterations of the algorithm. This should be less than or equal to 2*N).

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

toms456 is available in a Fortran77 version.

Related Programs and Data:

toms456_test

cities, a Fortran90 library of which defines various problems associated with a set of "cities" on a map.

CITIES, a dataset directory which contains some sets of intercity distances that can be used with this code.

LAU_NP, a Fortran90 library which includes a routine for the heuristic solution of the traveling salesman problem.

Reference:

  1. Zdenek Fencl,
    Algorithm 456: Routing Problem,
    Communications of the ACM,
    Volume 16, Number 9, September 1973, pages 572-574.

Source Code:

Last revised on 18 November 2023.