Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
type: Item
instance of: scholarly article
title: Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
zbMATH Open document ID: 0633.90087
DOI: 10.1016/0166-218X(87)90020-5
author: G. Laporte
author: Hélène Mercure
author: Yves Nobert
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4031434
zbMATH Keywords: asymmetrical case
zbMATH Keywords: exact algorithm
zbMATH Keywords: generalized version
zbMATH Keywords: Travelling Salesman
zbMATH Keywords: shortest Hamiltonian circuit
zbMATH Keywords: branch and bound
zbMATH Keywords: Computational results
MaRDI profile type: Publication
cites work: Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
cites work: Technical Note—Bounds for the Travelling-Salesman Problem
cites work: Q5578578
cites work: Generalized Travelling Salesman Problem Through n Sets Of Nodes: An Integer Programming Approach
cites work: Optimal tour planning with specified nodes
cites work: Q3762096
cites work: Q3206662
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: Q5613007
cites work: Q5563210
description: scientific article; zbMATH DE number 4031434