Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem

Luis Gouveia, Markus Leitner and Mario Ruthmair

European Journal of Operational Research, 2017, vol. 262, issue 3, 908-928

Abstract: In this paper we study Integer Linear Programming models and develop branch-and-cut algorithms to solve the Black-and-White Traveling Salesman Problem (BWTSP) (Bourgeois, Laporte, & Semet, 2003) which is a variant of the well known Traveling Salesman Problem (TSP). Two strategies to model the BWTSP have been used in the literature. The problem is either modeled on the original graph as TSP using a single set of binary edge variables and with additional non-trivial hop and distance constraints between every pair of black nodes (see Ghiani, Laporte, & Semat, 2006) or as a sequence of constrained paths composed of white nodes connecting pairs of black nodes (see Muter, 2015). In this paper, we study and develop an intermediate approach based on the observation that it is sufficient to guarantee the required distance (and hop) limit of the path from a given black node to the next black node without explicitly stating which one it is. Thus, instead of stating the two constraints (after adding appropriately defined variables) for each pair of black nodes, they are stated for each black node only (that represents the source of each path). Based on this idea we develop several variants of position- and distance-dependent reformulations together with corresponding layered graph representations. Branch-and-cut algorithms are developed for all proposed formulations and empirically compared by an extensive computational study. The obtained results allow us to provide insights into individual advantages and disadvantages of the different models.

Keywords: Traveling Salesman Problem; Distance constraint; Integer Linear Programming; Layered graph; Branch-and-cut (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717304083
Full text for ScienceDirect subscribers only

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:eee:ejores:v:262:y:2017:i:3:p:908-928

DOI: 10.1016/j.ejor.2017.04.061

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().