Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services

In the field of high-value shipment transportation, companies are faced to the malevolence problem. The risk of ambush increases with the predictability of vehicle routes. This paper addresses a very hard periodic vehicle routing problem with time windows, submitted by a software company specialized in transportation problems with security constraints. The hours of visits to each customer over the planning horizon must be spread in the customer's time window. As the aim is to solve real instances, the running time must be reasonable. A mixed integer linear model and a multi-start iterated local search are proposed. Results are reported on instances derived from classical benchmarks for the vehicle routing problem with time windows, and on two practical instances. Experiments are also conducted on a particular case with a single period, the vehicle routing problem with soft time windows: the new metaheuristic competes with two published algorithms and improves six best known solutions.