A new formulation and a branch-and-cut algorithm for the set orienteering problem

In this study we address the Set Orienteering Problem, which is a generalization of the Orienteering Problem where customers are clustered in groups. Each group is associated with a profit which is gained in case at least one customer in the group is served. A single vehicle is available to serve the customers. The aim is to find the vehicle route that maximizes the profit collected without exceeding a maximum route cost, which can be interpreted also as route duration. The problem was introduced in Archetti (2018) together with a mathematical programming formulation. In this paper, we propose a new formulation which uses less variables. We also derive different classes of valid inequalities to strengthen the formulation. In addition, separation algorithms are developed, some of which are new with respect to those presented in the literature. A branch-and-cut algorithm is implemented to solve the problem and tests are made on benchmark instances. The results show that the branch-and-cut algorithm is effective in solving instances with up to 100 customers. Moreover, the difficulty of solving the problem largely depends on the maximum route duration. We also show that valid inequalities are effective in speeding up the solution process. Finally, a comparison with two exact benchmark approaches proposed in the literature shows that the branch-and-cut algorithm proposed in this paper is the new state-of-the-art exact approach for solving the Set Orienteering Problem.