A branch-and-price algorithm for the set team orienteering problem with time windows

The orienteering problem consists of selecting a path of limited duration that maximizes the collection of profits associated with visits. The problem differs from the travelling salesman problem by maximizing profits under resource constraints instead of minizing cost with unlimited resources. In the work, we propose an exact branch-and-price algorithm for the set team orienteering problems with time windows, that generalizes the original problem by considering multiple vehicles, time windows for the visits and profits associated with sets. We also proposed a GRASP metaheuristic approach for speeding-up relaxed column generation, usually done by relaxations of labelling algorithms. The results indicated that the method is capable of solving many previously open instances and find new best solutions.