The orienteering problem with variable profits

G Erdogan, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)
221 Downloads (Pure)

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 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
JournalNetworks
Volume61
Issue number2
Early online date28 Jan 2013
DOIs
Publication statusPublished - 1 Mar 2013

Fingerprint

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

Cite this