  We consider several Vehicle Routing Problems (VRP) with profits, which seek
to select a subset of customers, each one being associated with a profit, and
to design service itineraries. When the sum of profits is maximized under
distance constraints, the problem is usually called team orienteering problem.
The capacitated profitable tour problem seeks to maximize profits minus travel
costs under capacity constraints. Finally, in the VRP with private fleet and
common carrier, some customers can be delegated to an external carrier subject
to a cost. Three families of combined decisions must be taken: customers
selection, assignment to vehicles, and sequencing of deliveries for each route.
  We propose a new neighborhood search for these problems which explores an
exponential number of solutions in pseudo polynomial time. The search is
conducted with standard VRP neighborhoods on an "exhaustive" solution
representation, visiting all customers. Since visiting all customers is usually
infeasible or sub-optimal, an efficient "Select" algorithm, based on resource
constrained shortest paths, is repeatedly used on any new route to find the
optimal subsequence of visits to customers. The good performance of these
neighborhood structures is demonstrated by extensive computational experiments
with a local search, an iterated local search and a hybrid genetic algorithm.
Intriguingly, even a local-improvement method to the first local optimum of
this neighborhood achieves an average gap of 0.09% on classic team orienteering
benchmark instances, rivaling with the current state-of-the-art metaheuristics.
Promising research avenues on hybridizations with more standard routing
neighborhoods are also open.
