Reformulation and Metaheuristic for the Team Orienteering Arc Routing Problem

The team orienteering arc routing problem (TOARP) is a relatively new vehicle routing problem. In this problem, a fleet of vehicles are available to serve two sets of customers, each of which is associated with an arc of a directed graph. The customers of the first set are required to be served whereas the ones of the second set are potential and may be not served. Each potential customer is associated with a profit, and the profit can be gained at most once when it is served. The TOARP aims to maximize the total profit gained by serving the customers while each vehicle must start from and end at a depot within a permitted maximum traveling time. This paper shows that the TOARP can be transformed into a team orienteering problem defined on a directed graph. To solve the TOARP, an iterated local search based algorithm is presented. The effectiveness of the proposed algorithm is studied on the benchmark instances.