Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays

Erika M. Herrera, Javier Panadero, Patricia Carracedo, Angel A. Juan () and Elena Perez-Bernabeu
Additional contact information
Erika M. Herrera: Computer Science Department, Universitat Oberta de Catalunya, 156 Rambla Poblenou, 08018 Barcelona, Spain
Javier Panadero: Department of Management, Universitat Politècnica de Catalunya–BarcelonaTech, 08028 Barcelona, Spain
Patricia Carracedo: Department of Applied Statistics and Operations Research, Universitat Politècnica de València, Plaza Ferrandiz y Carbonell, sn, 03801 Alcoy, Spain
Angel A. Juan: Department of Applied Statistics and Operations Research, Universitat Politècnica de València, Plaza Ferrandiz y Carbonell, sn, 03801 Alcoy, Spain
Elena Perez-Bernabeu: Department of Applied Statistics and Operations Research, Universitat Politècnica de València, Plaza Ferrandiz y Carbonell, sn, 03801 Alcoy, Spain

Mathematics, 2022, vol. 10, issue 20, 1-15

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; simheuristics; reliability analysis (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/20/3788/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/20/3788/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:20:p:3788-:d:942122

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().