Premium
The orienteering problem with variable profits
Author(s) -
Erdoǧan Güneş,
Laporte Gilbert
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21496
Subject(s) - orienteering , vertex (graph theory) , profit (economics) , operations research , mathematical optimization , mathematics , graph , combinatorics , computer science , travel time , time limit , mathematical economics , economics , microeconomics , transport engineering , engineering , management
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