The orienteering problem with variable profits

G Erdogan, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

62 Citations (SciVal)
368 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)104-116
Number of pages13
Issue number2
Early online date28 Jan 2013
Publication statusPublished - 1 Mar 2013


Dive into the research topics of 'The orienteering problem with variable profits'. Together they form a unique fingerprint.

Cite this