The Stochastic Team Orienteering Problem with Position-Dependent Rewards

Autor: Eva Barrena, Javier Panadero, Angel A. Juan, David Canca
Přispěvatelé: Universidad de Sevilla. Departamento de Organización Industrial y Gestión de Empresas I, Universidad de Sevilla. TEP216: Tecnologías de la Información e Ingeniería de Organización, 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), Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Mathematics; Volume 10; Issue 16; Pages: 2856
ISSN: 2227-7390
DOI: 10.3390/math10162856
Popis: 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.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje