All Colors Shortest Path problem on trees

Mehmet Berkehan Akçay (), Hüseyin Akcan () and Cem Evrendilek ()
Additional contact information
Mehmet Berkehan Akçay: Izmir University of Economics
Hüseyin Akcan: Izmir University of Economics
Cem Evrendilek: Izmir University of Economics

Journal of Heuristics, 2018, vol. 24, issue 4, No 2, 617-644

Abstract: Abstract Given an edge weighted tree T(V, E), rooted at a designated base vertex $$r \in V$$ r ∈ V , and a color from a set of colors $$C=\{1,\ldots ,k\}$$ C = { 1 , … , k } assigned to every vertex $$v \in V$$ v ∈ V , All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically.

Keywords: NP-hardness; Inapproximability; Integer linear programming; Linear programming relaxation; Genetic algorithm; Tabu search (search for similar items in EconPapers)
Date: 2018
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.1007/s10732-018-9370-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:24:y:2018:i:4:d:10.1007_s10732-018-9370-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9370-4

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().