id: 06065742
dt: j
an: 06065742
au: Roemer, Thomas A.; Ahmadi, Reza; Dasu, Sriram
ti: The traveling salesman problem with flexible coloring.
so: Discrete Appl. Math. 160, No. 12, 1798-1814 (2012).
py: 2012
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: traveling salesman problem; complexity; heuristics; probabilistic analysis;
    error bounds
ci: 
li: doi:10.1016/j.dam.2012.03.004
ab: Summary: This paper introduces a new generalized version of the Traveling
    Salesman Problem (TSP) in which nodes belong to various color classes
    and each color class must be visited as an entity. We distinguish the
    cases of the problem for which the colors are either pre-assigned or
    can be selected from a given subset of colors. We establish
    computational complexity and provide concise formulations for the
    problems that lend themselves to derive tight lower bounds. Exact
    solutions for special cases and a two-phase heuristic for the general
    case are provided. Worst case performance and asymptotic performance of
    the heuristic are analyzed and the effectiveness of the proposed
    heuristic in solving large industrial size problems is empirically
    demonstrated.
rv: