All Colors Shortest Path Problem on Trees [Master Thesis]

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üğüme C = {1,2,...,k} kümesinden bir renk atandığında, r düğümünden başlayarak, her bir farklı renkten en az bir düğüm içeren en kısa yolu bulma problemidir. Biz TREKY-a probleminin 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şetmesini temel alarak çeşitli sezgisel çözüm yöntemleri öneriliyor. Bu tez ayrıca TREKY-a için Genetik ve Tabu Arama algoritmalarını temel alan alternatif sezgisel çözüm yöntemleri de geliştirmektedir. Önerilen bütün sezgisel yöntemlerin performansı çeşitli parametrik tipte 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 , All Colors 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 distinct color in C is visited. We show that ACSP-t is NP-Hard, and also prove that it doesn't have a constant factor approximation algorithm. We give an Integer Linear Programming formulation of ACSP-t. Based on a Linear Programming relaxation of this formulation, several heuristics are proposed. The thesis also explores Genetic Algorithms, and Tabu Search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are finally evaluated experimentally for a wide range of trees parametrically generated.