A Metaheuristic Algorithm for a Multi-period Orienteering Problem Arising in a Car Patrolling Application

This paper addresses a real-life multi-period orienteering problem arising in a large Italian company that needs to patrol a vast area in order to provide security services. The area is divided into clusters, and each cluster is assigned to a patrol. A cluster comprises a set of customers, each requiring different services on a weekly basis. Some services are mandatory, while others are optional. It might be impossible to perform all optional services, and each of them is assigned a score when performed. The challenge is to determine a set of routes, one for each patrol and each day, that maximizes the total collected score, while meeting a number of operational constraints, including minimum quality of service, hard time windows, maximum riding time, and minimum time between two consecutive visits for the same service at the same customer. To solve the problem, we propose an iterated local search that invokes at each iteration an inner variable neighborhood descent procedure. Computational tests performed on a number of real-life instances prove that the developed algorithm is very efficient and finds in a short time solutions that are consistently better than those in use at the company.