Please use this identifier to cite or link to this item:
Title: Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays
Author: Herrera Machado, Erika Magdalena  
Panadero, Javier  
Carracedo, Patricia  
Juan, Angel A.  
Perez-Bernabeu, Elena  
Others: Universitat Oberta de Catalunya (UOC)
Universitat Politècnica de Catalunya (UPC)
Universitat Politècnica de València
Citation: Herrera, E., Panadero, J., Carracedo, P., Juan Perez, A.A. & Perez-Bernabeu, E. (2022). Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays. Mathematics, 10(20), 1-15. doi: 10.3390/math10203788
Abstract: In the team orienteering problem, a fixed fleet of vehicles departs from an origin depot towards a destination, and each vehicle has to visit nodes along its route in order to collect rewards. Typically, the maximum distance that each vehicle can cover is limited. Alternatively, there is a threshold for the maximum time a vehicle can employ before reaching its destination. Due to this driving range constraint, not all potential nodes offering rewards can be visited. Hence, the typical goal is to maximize the total reward collected without exceeding the vehicle’s capacity. The TOP can be used to model operations related to fleets of unmanned aerial vehicles, road electric vehicles with limited driving range, or ride-sharing operations in which the vehicle has to reach its destination on or before a certain deadline. However, in some realistic scenarios, travel times are better modeled as random variables, which introduce additional challenges into the problem. This paper analyzes a stochastic version of the team orienteering problem in which random delays are considered. Being a stochastic environment, we are interested in generating solutions with a high expected reward that, at the same time, are highly reliable (i.e., offer a high probability of not suffering any route delay larger than a user-defined threshold). In order to tackle this stochastic optimization problem, which contains a probabilistic constraint on the random delays, we propose an extended simheuristic algorithm that also employs concepts from reliability analysis.
Keywords: team orienteering problem
probabilistic constraints
reliability analysis
Document type: info:eu-repo/semantics/article
Version: info:eu-repo/semantics/publishedVersion
Issue Date: 14-Oct-2022
Publication license:  
Appears in Collections:Articles
Articles cientÍfIcs

Files in This Item:
File Description SizeFormat 
mathematics-10-03788.pdf401,05 kBAdobe PDFThumbnail
View statistics

Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.