The orienteering problem with variable profits

Abstract This article introduces, models, and solves a generalization of the orienteering problem, called the the orienteering problem with variable profits (OPVP). The OPVP is defined on a complete undirected graph G = ( V , E ), with a depot at vertex 0. Every vertex i ∈ V \{0} has a profit p i to be collected, and an associated collection parameter α i ∈[0, 1]. The vehicle may make a number of “passes,” collecting 100α i percent of the remaining profit at each pass. In an alternative model, the vehicle may spend a continuous amount of time at every vertex, collecting a percentage of the profit given by a function of the time spent. The objective is to determine a maximal profit tour for the vehicle, starting and ending at the depot, and not exceeding a travel time limit. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013