The Stochastic Team Orienteering Problem with Position-Dependent Rewards

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