Tabu search for solving the black-and-white travelling salesman problem

Haitao Li () and Bahram Alidaee
Additional contact information
Haitao Li: Tianjin University of Commerce
Bahram Alidaee: University of Mississippi

Journal of the Operational Research Society, 2016, vol. 67, issue 8, 1061-1079

Abstract: Abstract The black-and-white travelling salesman problem (BWTSP) is an extension to the well-known TSP by partitioning the set of vertices into black and white vertices, and imposing cardinality and length constraints between two consecutive black vertices in a Hamiltonian tour. BWTSP has various applications in aircraft routing, telecommunication network design and logistics. In this paper, we develop several tabu search (TS) heuristics for solving the BWTSP. Our TS is built upon a new efficient neighbourhood structure, which exploits both the permutation and knapsack features of BWTSP. We also embed our TS as a heuristic procedure to improve the upper bound in a mixed-integer linear programming method. Extensive computational experiment on both benchmark and randomly generated instances shows effectiveness and efficiency of our algorithms. Our algorithms are able to obtain optimal and near optimal solutions to small instances in seconds, and find feasible solutions to large instances that have not been solved by the existing methods in the literature.

Keywords: travelling salesman problem; side constraints; local search; metaheuristics; tabu search; hybrid algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1057/jors.2015.122 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:67:y:2016:i:8:d:10.1057_jors.2015.122

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/jors.2015.122

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().