The Black and White Traveling Salesman Problem
- 1 April 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 54 (2), 366-378
- https://doi.org/10.1287/opre.1050.0218
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
This publication has 21 references indexed in Scilit:
- Heuristics for the black and white traveling salesman problemComputers & Operations Research, 2003
- Separating capacity constraints in the CVRP using tabu searchEuropean Journal of Operational Research, 1998
- A Polyhedral Approach to the Asymmetric Traveling Salesman ProblemManagement Science, 1997
- A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman ProblemOperations Research, 1997
- Tabu SearchPublished by Springer Science and Business Media LLC ,1997
- SONET Toolkit: A Decision Support System for Designing Robust and Cost-Effective Fiber-Optic NetworksInforms Journal on Applied Analytics, 1995
- A branch-and-cut algorithm for vehicle routing problemsAnnals of Operations Research, 1994
- A Tabu Search Heuristic for the Vehicle Routing ProblemManagement Science, 1994
- New Insertion and Postoptimization Procedures for the Traveling Salesman ProblemOperations Research, 1992
- Solution of a Large-Scale Traveling-Salesman ProblemJournal of the Operations Research Society of America, 1954