A new formulation and approach for the black and white traveling salesman problem

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.
Original languageEnglish
Pages (from-to)96-106
JournalComputers and Operations Research
Volume53
Early online date14 Aug 2014
DOIs
Publication statusPublished - Jan 2015

Fingerprint

Traveling salesman problem
Travelling salesman problems
Column Generation
Linear programming
Formulation
Linear Programming Relaxation
Hamiltonians
Cycle Cover
Dantzig-Wolfe Decomposition
Path
Cutting Planes
Resource Constraints
Multigraph
Shortest Path Problem
Hamiltonian circuit
Decomposition
Branch and Bound Algorithm
Pricing
Consecutive
Cardinality

Cite this

A new formulation and approach for the black and white traveling salesman problem. / Muter, Ibrahim.

In: Computers and Operations Research, Vol. 53, 01.2015, p. 96-106.

Research output: Contribution to journalArticle

@article{433dcb75cc0a4aeea9934785bc15beb2,
title = "A new formulation and approach for the black and white traveling salesman problem",
abstract = "This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.",
author = "Ibrahim Muter",
year = "2015",
month = "1",
doi = "10.1016/j.cor.2014.07.019",
language = "English",
volume = "53",
pages = "96--106",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",

}

TY - JOUR

T1 - A new formulation and approach for the black and white traveling salesman problem

AU - Muter, Ibrahim

PY - 2015/1

Y1 - 2015/1

N2 - This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.

AB - This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.

UR - https://doi.org/10.1016/j.cor.2014.07.019

U2 - 10.1016/j.cor.2014.07.019

DO - 10.1016/j.cor.2014.07.019

M3 - Article

VL - 53

SP - 96

EP - 106

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -