The Vehicle Routing Problem with Arrival Time Diversification

Cash in Transit (CIT) companies deliver valuable goods to banks, ATMs and stores. Legal regulations and security considerations force these companies to take various measures to protect their valuable cargo against attacks. Driving varying routes to serve their customers is one key strategy to lower the risk of an attack. In this research, we want to generate sufficiently unpredictable routes by varying the arrival time at a customer, while minimizing transportation costs. We present a novel solution approach, by removing previous arrival time slots at customers from the solution space. This results in a routing problem with multiple time windows in which the customers are still available for service. The problem is solved using a rolling horizon framework by taking into account previous arrival times at the customers. Since waiting time at a customer is not allowed due to safety reasons, an efficient method is proposed to check if a route is feasible. An iterated tabu search is used to solve the routing problem and the proposed solution approach is tested on benchmark instances from the literature. We were able to find new best solutions for all but one instance and we study the trade-off between arrival time diversification and transportation cost.

Registration to Remy Spliet, spliet@ese.eur.nl, is required for availability of lunch.