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

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.