TY - JOUR
T1 - Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays
AU - Herrera, Erika M.
AU - Panadero, Javier
AU - Carracedo, Patricia
AU - Juan, Angel A.
AU - Perez-Bernabeu, Elena
N1 - Publisher Copyright:
© 2022 by the authors.
PY - 2022/10
Y1 - 2022/10
N2 - 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.
AB - 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.
KW - probabilistic constraints
KW - reliability analysis
KW - simheuristics
KW - team orienteering problem
UR - http://www.scopus.com/inward/record.url?scp=85140757109&partnerID=8YFLogxK
U2 - 10.3390/math10203788
DO - 10.3390/math10203788
M3 - Article
AN - SCOPUS:85140757109
SN - 2227-7390
VL - 10
JO - Mathematics
JF - Mathematics
IS - 20
M1 - 3788
ER -