Article: An agile optimisation algorithm for the multi-source team orienteering problem Journal: European Journal of Industrial Engineering (EJIE) 2025 Vol.19 No.3 pp.273 - 294 Abstract: In the team orienteering problem (TOP), a fixed fleet of vehicles have to collect rewards by visiting customers. Typically, all vehicles depart from a source depot and end in a sink depot. Also, each vehicle has a limited driving range, so not all customers can be visited. The goal is then to select the set of customers to be visited, and the corresponding routes to do it, such in a way that the total reward collected is maximised while respecting the aforementioned constraints. This paper explores a TOP variant with multiple source depots and where real-time solutions need to be provided, i.e., computation times need to be in the order of milliseconds even for mid-sized instances with hundreds of customers. To deal with this challenge, and taking into account that the problem is <i>NP-hard</i>, we propose an 'agile' optimisation algorithm that is based on a biased-randomised heuristic. Our approach can be applied in realistic and dynamic scenarios where vehicles need to recompute their routes in real-time, as vehicles are in-route, new customers appear, and some existing customers are not available anymore. [Submitted: 20 May 2022; Accepted: 31 December 2022] Inderscience Publishers - linking academia, business and industry through research

Title: An agile optimisation algorithm for the multi-source team orienteering problem

Authors: Mattia Neroni; Javier Panadero; Elnaz Ghorbani; Majsa Ammouriova; Angel A. Juan

Addresses: 'Enzo Ferrari' Engineering Department, University of Modena and Reggio Emilia, Via Università 4, 41121, Modena, Italy ' Department of Computer Architecture and Operating Systems, Universitat Autònoma de Barcelona, Plaça Cívica, 08193, Bellaterra, Spain ' Computer Science Department, Universitat Oberta de Catalunya, Rambla del Poblenou 156, 08860 Barcelona, Spain ' Computer Science Department, Universitat Oberta de Catalunya, Rambla del Poblenou 156, 08860 Barcelona, Spain ' Research Center on Production Management and Engineering, Universitat Politècnica de València, Plaza Ferrándiz-Carbonell, s/n, 03801 Alcoy, Spain

Abstract: In the team orienteering problem (TOP), a fixed fleet of vehicles have to collect rewards by visiting customers. Typically, all vehicles depart from a source depot and end in a sink depot. Also, each vehicle has a limited driving range, so not all customers can be visited. The goal is then to select the set of customers to be visited, and the corresponding routes to do it, such in a way that the total reward collected is maximised while respecting the aforementioned constraints. This paper explores a TOP variant with multiple source depots and where real-time solutions need to be provided, i.e., computation times need to be in the order of milliseconds even for mid-sized instances with hundreds of customers. To deal with this challenge, and taking into account that the problem is NP-hard, we propose an 'agile' optimisation algorithm that is based on a biased-randomised heuristic. Our approach can be applied in realistic and dynamic scenarios where vehicles need to recompute their routes in real-time, as vehicles are in-route, new customers appear, and some existing customers are not available anymore. [Submitted: 20 May 2022; Accepted: 31 December 2022]

Keywords: agile optimisation; biased-randomised heuristics; team orienteering problem; TOP; dynamic scenarios.

DOI: 10.1504/EJIE.2025.145302

European Journal of Industrial Engineering, 2025 Vol.19 No.3, pp.273 - 294

Received: 20 May 2022
Accepted: 31 Dec 2022
Published online: 31 Mar 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: An agile optimisation algorithm for the multi-source team orienteering problem

Keep up-to-date