Tekijä: | Volgenant, T. V. Jonker, R. |
Otsikko: | On some generalizations of the travelling-salesman problem. |
Lehti: | Journal of the Operational Research Society
1987 : NOV, VOL. 38:11, p. 1073-1079 |
Asiasana: | INTEGER PROGRAMMING SEQUENTIAL ANALYSIS SALESMEN OPTIMIZATION |
Kieli: | eng |
Tiivistelmä: | A generalization of the problem is considered, in which a salesperson can visit every node at most once and some penalty cost is incurred for every unvisited node. It has several problems as special cases such as the travelling-salesman problem itself, the shortest-path problem with specified nodes and the longest-path problem. A new transformation of the generalized into a standard problem is described. Computational results for the shortest-path problem are presented. The transformation complements the previously published methods based on linear assignment relaxation, and thus makes it possible to solve the symmetric problems with relatively large number of specified nodes. |
SCIMA