Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE: The Multiple Colored TSP

CONFÉRENCIER: Roberto Wolfler-Calvo, Maître de conférences, Laboratoire des Systèmes Industriels, Université de Technologie, Troyes

DATE et ENDROIT: mercredi 30 octobre 2002, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE: Jean-François Cordeau (340-6278)

RÉSUMÉ: Let G=(V,A) be an oriented graph where V is the vertex set partitioned into clusters containing vertices of the same color. The number of colors (sets of nodes of the same color) is H. The arc set is A and a distance matrix is defined on A. The Multiple Colored TSP (MCTSP) consists of constructing a shortest hamiltonian cycle on G such that any two vertices belonging to the same cluster are separated by at least k vertices not belonging to the same cluster and by at most l vertices not belonging to the same cluster. Generally speaking the MCTSP is different from any other model of TSP. The models proposed in the literature that could have something in common with the MCTSP are: the Black and White Travelling Salesman Problem (BWTSP) and the Travelling Salesman Problem with separation requirements (TSPsr). An application of the MCTSP is the design of a watchman tour where all vertices of the same cluster correspond to a single location where several inspections are required by a travelling watchman but at different times. For security reasons it is best to impose a minimum separation constraint and a maximum number of other visits between any two consecutive visits to the same location. In this talk the multicolored travelling salesman problem is introduced for the first time. A formulation is proposed together with a set of valid inequalities.