All Colors Shortest Path Problem on Trees

Abstract

Ağaç Yapılarında Tüm Renkleri İçeren En Kısa Yolu Bulma (TREKY-a) problemi,V kümesi içinde bulunan r düğümünde kökleşmiş bir T = (V;E) ağacı verilip, ağaçtaki her bir düğümeC = {1,2,...,k} kümesinden bir renk atandığında, r düğümünden başlayarak, her birfarklı renkten en az bir düğüm içeren en kısa yolu bulma problemidir. Biz TREKY-aprobleminin NP-Zor olduğunu gösteriyoruz. Ayrıca, TREKY-a için sabit faktörlübir yakınsama algoritmasının olmadığını kanıtlıyoruz. TREKY-a problemi için tamsayılineer programlama formülü veriyoruz. Bu formülün lineer programlama gevşetmesinitemel alarak çeşitli sezgisel çözüm yöntemleri öneriliyor. Bu tez ayrıca TREKY-a içinGenetik ve Tabu Arama algoritmalarını temel alan alternatif sezgisel çözüm yöntemleride geliştirmektedir. Önerilen bütün sezgisel yöntemlerin performansı çeşitli parametriktipte ağaçlarla deneysel olarak değerlendirilmektedir.

Given an edge weighted tree T(V;E), rooted at a designated base vertex r /in V,and a color from a set of colors C = {1,2,...,k} assigned to every vertex v /in V , AllColors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly nonsimple,path starting from r in T such that at least one node from every distinctcolor in C is visited. We show that ACSP-t is NP-Hard, and also prove thatit doesn't have a constant factor approximation algorithm. We give an IntegerLinear Programming formulation of ACSP-t. Based on a Linear Programmingrelaxation of this formulation, several heuristics are proposed. The thesis alsoexplores Genetic Algorithms, and Tabu Search to develop alternative heuristicsolutions for ACSP-t. The performance of all the proposed heuristics are finallyevaluated experimentally for a wide range of trees parametrically generated.