×

Optimal tour planning with specified nodes. (English) Zbl 0559.90090

Let \(N=\{1,...,n\}\) be a set of cities, \(K=\{1,...,k\}\) (k\(\leq n)\) a set of ”specified” cities. The travelling salesman problem with specified nodes (STSP) consists of determining the shortest circuit for a salesman wishing to visit each city of K exactly once and each of the remaining n- k cities at most once. This paper presents an algorithm for the solution of the STSP. It is very similar to Ibaraki’s algorithm [see T. Ibaraki, Electronics and Communications in Japan 53-A, 10-18 (1970)] for the problem of determining the shortest path between a source and a sink, passing through a set of specified nodes exactly once and the other nodes at most once. Results are presented for the STSP involving up to 200 nodes in the asymmetrical case and up to 80 nodes in the symmetrical case.

MSC:

90C35 Programming involving graphs or networks
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI EuDML