  All Colors Shortest Path problem defined on an undirected graph aims at
finding a shortest, possibly non-simple, path where every color occurs at least
once, assuming that each vertex in the graph is associated with a color known
in advance. To the best of our knowledge, this paper is the first to define and
investigate this problem. Even though the problem is computationally similar to
generalized minimum spanning tree, and the generalized traveling salesman
problems, allowing for non-simple paths where a node may be visited multiple
times makes All Colors Shortest Path problem novel and computationally unique.
In this paper we prove that All Colors Shortest Path problem is NP-hard, and
does not lend itself to a constant factor approximation. We also propose
several heuristic solutions for this problem based on LP-relaxation, simulated
annealing, ant colony optimization, and genetic algorithm, and provide
extensive simulations for a comparative analysis of them. The heuristics
presented are not the standard implementations of the well known heuristic
algorithms, but rather sophisticated models tailored for the problem in hand.
This fact is acknowledged by the very promising results reported.
