×

zbMATH — the first resource for mathematics

Generalized travelling salesman problem through n sets of nodes: The asymmetrical case. (English) Zbl 0633.90087
This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters of nodes, in the case where the distance matrix is asymmetrical. The problem is formulated as an integer linear program. The program is then relaxed and solved by a branch and bound algorithm. Computational results are reported for problems involving up to 100 nodes and 8 clusters.

MSC:
90C35 Programming involving graphs or networks
90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity
90C05 Linear programming
05C35 Extremal problems in graph theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bovet, J., The selective travelling salesman problem, Vienna, Paper presented at the EURO VI conference, (1983)
[2] Carpaneto, G.; Toth, P., Some new branching and bounding criteria for the asymmetric travelling salesman problem, Management sci., 26, 736-743, (1980) · Zbl 0445.90089
[3] Christofides, N., Bounds for the travelling salesman problem, Operations research, 20, 1044-1056, (1972) · Zbl 0251.90027
[4] Henry-Labordere, A.L., The record balancing problem: A dynamic programming solution of a generalized travelling salesman problem, Riro, B-2, 43-49, (1969) · Zbl 0187.14002
[5] Laporte, G.; Nobert, Y., Generalized travelling salesman problem through n sets of nodes: an integer programming approach, Infor., 21, 61-75, (1983) · Zbl 0524.90069
[6] Laporte, G.; Mercure, H.; Nobert, Y., Optimal tour planning with specified nodes, RAIRO rech. opér., 18, 203-210, (1984) · Zbl 0559.90090
[7] Laporte, G.; Mercure, H.; Nobert, Y., Finding the shortest Hamiltonian circuit through n clusters: a Lagrangean relaxation approach, Cong. mumer., 48, 277-290, (1985)
[8] Lenstra, J.K.; Rinnooy Kan, A.H.G., Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227, (1981) · Zbl 0416.90049
[9] Lin, S.; Kerninghan, B.W., Computer solutions of the travelling salesman problem, Operations research, 21, 498-516, (1973) · Zbl 0256.90038
[10] Rousseau, J.-M., Private communication, (January 1985), Centre de recherche sur les transports, University of Montreal
[11] Saksena, J.P., Mathematical model of scheduling clients through welfare agencies, Cors j., 8, 185-200, (1970) · Zbl 0211.52002
[12] Srivastava, S.S.; Kumar, S.; Garg, R.C.; Sen, P., Generalized travelling salesman problem through n sets of nodes, Cors j., 7, 97-101, (1969) · Zbl 0174.51305
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.