A branch-and-price-and-cut algorithm for the Team Orienteering Arc Routing Problem
We consider in this work the Team Orienteering Arc Routing Problem. It is a variation of the well known Team Orienteering Problem where the set of customers is given by a subset of arcs in a directed graph. In this problem a set of vehicles has to mandatorily visit a subset of the customers. There is also a profit associated with the remaining ones, thus, in some circumstances is convenient visiting some of these customers. The time consumed by each vehicle along the route is bounded. We propose a set partitioning formulation for this problem, leading to a column generation algorithm. The performance of this algorithm has been studied on a wide family of benchmark test instances . We have observed that, as the number of vehicles grows, our proposal shows a better performance than other previous exact algorithms in the literature.
Keywords: team orienteering arc routing problem profits multivehicle branch-and-price-and-cut
