The generalized traveling salesman problem (GTSP) is a variation of the well-known traveling salesman problem (TSP). Given a graph G in which each of its n nodes belongs to at least one of the m clusters ( ), the GTSP seeks a minimum cost simple cycle which passes through each cluster exactly once. covering tour problem. The first work that is presented in this thesis is a new version of GTSP called the GTSP with cluster demand (GTSP-CD). In GTSP-CD, a specific demand is associated with each cluster and each node has a supply of its own; while in the GTSP the demand of each cluster is one unit and supply of each node is also one unit. In GTSP-CD the objective is to find a minimum cost Simple cycle that satisfies demand of all the clusters. An exact branch and bound method is presented as a solution method for the asymmetric version of this problem. Computational results demonstrate the ability of the proposed algorithm to solve small and moderate size problems. Due to the inability of this method to solve large scale GTSP-CD problems we need to use heuristic and metaheuristic algorithms. Hence, two heuristic and one metaheuristic algorithm are also proposed In recent years, several metaheuristics are proposed for GTSP. Computational results of these algorithms indicate that the best performing metaheuristics are all memetic algorithms. While ant colony optimization (ACO) is one the successful TSP metaheuristics, the only proposed ACO algorithm for the generalized version of this problem has a very weak performance and can’t be considered an efficient algorithm. Hence, the introduction of ant colony system algorithm for the symmetric generalized traveling salesman problem is the subject of another work that is presented in this thesis. To test the efficiency of this algorithm, we compare it with the only published ant colony algorithm and three of the best performing metaheuristics in the literature. Computational results demonstrate the efficiency of the proposed algorithm both in terms of running time and solution quality. The last work which is presented in this thesis is a new branch and bound algorithm for the asymmetric generalized traveling salesman problem. Comparisons of computational results of the proposed algorithm with the state of the art exact algorithm for the asymmetric GTSP demonstrate the very good performance of the proposed algorithm.