Optimizing a Car Patrolling Application by Iterated Local Search

We address a car patrolling application arising in a service company that needs to visit customers in a large area periodically. Customers are divided into clusters, each of which is assigned to a single patrol and requires different services, either mandatory or optional, on a weekly basis. The services have to be performed by satisfying several operational constraints, including interdependent time windows and maximum route duration. The aim is to maximize a weighted function that combines the profit collected from the optional services and the total working time required to perform all routes. The resulting optimization problem can be represented as a territory design and multi-period team orienteering problem. We solve the problem using an Iterated Local Search that invokes several inner procedures, including dedicated heuristics for creating the initial clusters, perturbation operators to diversify the search, and a variable neighborhood descent to search for good-quality routes. Extensive computational tests on a set of real-world instances involving up to a few hundred customers and a few thousand services prove the algorithm efficiency.