Artículo
The Stochastic Team Orienteering Problem with Position-Dependent Rewards
Autor/es | Panadero, Javier
Barrena, Eva Juan, Ángel A. Canca Ortiz, José David |
Departamento | Universidad de Sevilla. Departamento de Organización Industrial y Gestión de Empresas I |
Fecha de publicación | 2022-08 |
Fecha de depósito | 2023-02-20 |
Publicado en |
|
Resumen | In this paper, we analyze both the deterministic and stochastic versions of a team orienteering problem (TOP) in which rewards from customers are dynamic. The typical goal of the TOP is to select a set of customers to visit ... In this paper, we analyze both the deterministic and stochastic versions of a team orienteering problem (TOP) in which rewards from customers are dynamic. The typical goal of the TOP is to select a set of customers to visit in order to maximize the total reward gathered by a fixed fleet of vehicles. To better reflect some real-life scenarios, we consider a version in which rewards associated with each customer might depend upon the order in which the customer is visited within a route, bonusing the first clients and penalizing the last ones. In addition, travel times are modeled as random variables. Two mixed-integer programming models are proposed for the deterministic version, which is then solved using a well-known commercial solver. Furthermore, a biased-randomized iterated local search algorithm is employed to solve this deterministic version. Overall, the proposed metaheuristic algorithm shows an outstanding performance when compared with the optimal or near-optimal solutions provided by the commercial solver, both in terms of solution quality as well as in computational times. Then, the metaheuristic algorithm is extended into a full simheuristic in order to solve the stochastic version of the problem. A series of numerical experiments allows us to show that the solutions provided by the simheuristic outperform the near-optimal solutions obtained for the deterministic version of the problem when the latter are used in a scenario under conditions of uncertainty. In addition, the solutions provided by our simheuristic algorithm for the stochastic version of the problem offer a higher reliability level than the ones obtained with the commercial solver. |
Agencias financiadoras | Ministerio de Ciencia e Innovación (MICIN). España Universidad de Sevilla Junta de Andalucía European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) |
Identificador del proyecto | PID2019-104263RB-C41
PID2019-106205GB-I00 US-1381656 |
Cita | Panadero, J., Barrena, E., Juan, Á.A. y Canca Ortiz, J.D. (2022). The Stochastic Team Orienteering Problem with Position-Dependent Rewards. Mathematics, 10 (16), 2856. https://doi.org/10.3390/math10162856. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Panadero_2022_Mathematics_ The ... | 474.3Kb | [PDF] | Ver/ | |