This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ghiani, G. Articles by Semet, F. Search for Related Content

The Black and White Traveling Salesman Problem

Centre de recherche sur les transports, Université de Montréal, C.P. 6128, Succursale Centre-ville, Montréal, Quebec, Canada H3C 3J7 and Dipartimento di Ingegneria dell’Innovazione, Università di Lecce, Via per Arnesano, 73100 Lecce, Italy
Centre de recherche sur les transports, Université de Montréal, C.P. 6128, Succursale Centre-ville, Montréal, Quebec, Canada H3C 3J7 and HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Quebec, Canada H3T 2A7
LAMIH, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont-Houy, 59311 Valenciennes Cedex 9, France
gianpaolo.ghiani{at}unile.it
gilbert{at}crt.umontreal.ca
frederic.semet{at}univ-valenciennes.fr

The black and white traveling salesman problem (BWTSP) is defined on a graph G whose vertex set is partitioned into black and white vertices. The aim is to design a shortest Hamiltonian tour on G subject to cardinality and length constraints: both the number of white vertices as well as the length of the tour between two consecutive black vertices are bounded above. The BWTSP has applications in airline scheduling and in telecommunications. This paper proposes an integer linear formulation for the undirected BWTSP, as well as several classes of valid inequalities. An exact branch-and-cut algorithm is then developed. Extensive tests show that it can solve exactly instances involving up to 100 vertices. The algorithm can also be applied directly to solve unit demand vehicle routing problems of similar sizes.

Subject classifications: traveling salesman problem; vehicle routing problem; valid inequalities; branch-and-cut; exact algorithm.
History: Received December 2000; revision received November 2004; accepted November 2004.