The orienteering problem with variable profits

G Erdogan, Gilbert Laporte

OAI: oai:purehost.bath.ac.uk:publications/4a5a0b69-126c-432b-a65c-28d877ad823f • DOI: https://doi.org/10.1002/net.21496

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 pi 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.