A Branch-and-Price Approach for the Team Orienteering Problem with Time Windows

Abstract

Given a set of vertices, each of which has its own prize and time window, the team orienteering problem with time windows (TOPTW) is a problem of finding a set of vehicle routes with the maximum total prize that satisfies vehicle time limit and vertex time window constraints. Many heuristic algorithms have solved the TOPTW; to our knowledge, however, no exact algorithm that can solve this problem optimally has yet been identified. This study proposes an exact algorithm based on the branch-and-price approach to solve the TOPTW. This algorithm can find optimal solutions for many TOPTW benchmark instances. We also apply the proposed algorithm to the team orienteering problem (TOP), which is a time window constraint relaxed version of the TOPTW. Unlike the TOPTW, a couple of exact algorithms have solved the TOP. The proposed algorithm can find more number of optimal solutions to TOP benchmark instances.