Προσεγγιστικοί και ευρετικοί αλγόριθμοι για το πρόβλημα του προσανατολισμού
Approximation algorithms and heuristics for the orienteering problem
In this thesis, we present the Orienteering Problem (OP) or Selective Travelling Salesman Problem (STSP) or Maximum Collection Problem which are some other names of the problem. Orienteering Problem is an optimization problem and it is a variant of Travelling Salesperson Problem (TSP). This kind of problems have a lot of interest because they are applicable in real life problems. The problem takes as an input a (directed or undirected) graph with some non-negative weights in its edges. Let G=(V,E) be the graph, s and t two given vertices and a non-negative time budget B. The goal is to find a path from s to t with time cost at most B, so as to maximize the number of vertices visited by the path. In this definition of the problem, s and t are given. In this case, the problem is called point to point OP. In addition, OP has some variants like rooted OP, unrooted OP, OP with the same or different profit to his nodes etc. Unrooted OP is defined like above with the difference that s and t are not given. In this variant of the problem, starting node and ending node s and t can be any node which belongs to V. In rooted OP, the starting node s is given but the ending node t is not. OP is a NP-hard problem which means that an exact algorithm for its solution in polynomial time, has not been found. Therefore some approximation algorithms have been proposed for solving the problem in acceptable time. In this thesis, the problem is formulated and some results for approximation algorithms are presented. We present a new heuristic algorithm for Team Orienteering Problem with Time Windows. Team Orienteering Problem is a generalization of OP. Given an additional positive integer parameter m, the goal is to find m distinct paths from s to t, having cost less than or equal to B, so as to maximize the total number of vertices visited by the m paths. OP with Time Windows has an extra constraint: the visit at each node must occur within a specific time interval for each node.