The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.

► We address the Capacitated Team Orienteering Problem (CTOP). ► Interrelated search landscapes are explored via a generic bi-level search scheme. ► Generalized profit oriented neighborhood structures are proposed. ► A Filter-and-Fan method is developed for the first time to solve the CTOP. ► Compared to existing results, new upper bounds are reported with competitive computational times.