The Stochastic Team Orienteering Problem with Position-Dependent Rewards

Javier Panadero, Eva Barrena, Angel A. Juan () and David Canca
Additional contact information
Javier Panadero: Department of Management, Universitat Politècnica de Catalunya—BarcelonaTech, 08028 Barcelona, Spain
Eva Barrena: Department of Economics, Quantitative Methods and Economic History, Universidad Pablo de Olavide, 41013 Seville, Spain
Angel A. Juan: Department of Applied Statistics and Operations Research, Universitat Politècnica de València, 03801 Alcoy, Spain
David Canca: Department of Industrial Engineering and Management Science, Universidad de Sevilla, 41092 Seville, Spain

Mathematics, 2022, vol. 10, issue 16, 1-25

Abstract: 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.

Keywords: team orienteering problem; mathematical modeling; biased-randomized algorithms; simheuristics (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: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/16/2856/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/16/2856/ (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:16:p:2856-:d:885036

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 ().