The Black and White Traveling Salesman Problem

Gianpaolo Ghiani (), Gilbert Laporte () and Frédéric Semet ()
Additional contact information
Gianpaolo Ghiani: 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
Gilbert Laporte: 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
Frédéric Semet: LAMIH, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont-Houy, 59311 Valenciennes Cedex 9, France

Operations Research, 2006, vol. 54, issue 2, 366-378

Abstract: 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.

Keywords: traveling salesman problem; vehicle routing problem; valid inequalities; branch-and-cut; exact algorithm (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1050.0218 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:54:y:2006:i:2:p:366-378

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().