Groupe d’études et de recherche en analyse des décisions


Optimal Tour Planning with Specified Nodes

, et

This paper consider the problem of determining the shortest circuit or cycle in a graph containing n nodes and such that (i) each of k nodes (k ≤ n) is visited exactly once; (ii) each of the remaining n-k nodes is visited at most once. A branch and bound algorithm for this problem is described. Results are presented for problems involving up to 200 nodes in the asymmetrical case and up to 80 nodes in the symmetrical case.

, 10 pages