A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation

A.L. Kok, C. Manuel Meyer, Herbert Kopfer, Johannes M.J. Schutten

Research output: Book/ReportReportProfessional

42 Downloads (Pure)

Abstract

In practice, apart from the problem of vehicle routing, schedulers also face the problem of nding feasible driver schedules complying with complex restrictions on drivers' driving and working hours. To address this complex interdependent problem of vehicle routing and break scheduling, we propose a dynamic programming approach for the vehicle routing problem with time windows including the EC social legislation on drivers' driving and working hours. Our algorithm includes all optional rules in these legislations, which are generally ignored in the literature. To include the legislation in the dynamic programming algorithm we propose a break scheduling method that does not increase the time-complexity of the algorithm. This is a remarkable eect that generally does not hold for local search methods, which have proved to be very successful in solving less restricted vehicle routing problems. Computational results show that our method finds solutions to benchmark instances with 18% less vehicles and 5% less travel distance than state of the art approaches. Furthermore, they show that including all optional rules of the legislation leads to an additional reduction of 4% in the number of vehicles and of 1.5% regarding the travel distance. Therefore, the optional rules should be exploited in practice.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Research School for Operations Management and Logistics (BETA)
Number of pages30
ISBN (Print)9789038617121
Publication statusPublished - 2009

Publication series

NameBETA Working Paper
PublisherUniversity of Twente, Beta Research School for Operations Management and Logistics
No.270

Keywords

  • METIS-256273
  • Vehicle Routing and Scheduling
  • EC Social Legislation
  • Dynamic Programming
  • IR-70216

Cite this

Kok, A. L., Meyer, C. M., Kopfer, H., & Schutten, J. M. J. (2009). A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation. (BETA Working Paper; No. 270). Enschede: University of Twente, Research School for Operations Management and Logistics (BETA).