A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics

New retail trends show the increasing importance of providing cost efficient deliveries in cities, where congestion and compliance with driving hours regulations should be incorporated into routing software. This paper introduces a large neighbourhood search algorithm that substantially improves the benchmark solutions (in terms of the number of vehicles required, travel distance and duty time) for the vehicle routing problem variant considering time windows, time-dependent travel times and driving hours regulations (EC) 561/2006 that apply to vehicles over 3.5 tons in European cities. Additionally, instances for The Road Transport (Working Time) Regulation 2005 that applies to drivers in the United Kingdom are introduced. The proposed algorithm is also used in scenarios that represent home delivery conditions to evaluate the impacts of the length of time windows, customer density, congestion and regulations in terms of cost and environmental impact.