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).
Kok, A.L. ; Meyer, C. Manuel ; Kopfer, Herbert ; Schutten, Johannes M.J. / A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation. Enschede : University of Twente, Research School for Operations Management and Logistics (BETA), 2009. 30 p. (BETA Working Paper; 270).
@book{666ce4b9d175421fb528b62fe5289263,
title = "A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation",
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.",
keywords = "METIS-256273, Vehicle Routing and Scheduling, EC Social Legislation, Dynamic Programming, IR-70216",
author = "A.L. Kok and Meyer, {C. Manuel} and Herbert Kopfer and Schutten, {Johannes M.J.}",
year = "2009",
language = "Undefined",
isbn = "9789038617121",
series = "BETA Working Paper",
publisher = "University of Twente, Research School for Operations Management and Logistics (BETA)",
number = "270",
address = "Netherlands",

}

Kok, AL, Meyer, CM, Kopfer, H & Schutten, JMJ 2009, A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation. BETA Working Paper, no. 270, University of Twente, Research School for Operations Management and Logistics (BETA), Enschede.

A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation. / Kok, A.L.; Meyer, C. Manuel; Kopfer, Herbert; Schutten, Johannes M.J.

Enschede : University of Twente, Research School for Operations Management and Logistics (BETA), 2009. 30 p. (BETA Working Paper; No. 270).

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - Kok, A.L.

AU - Meyer, C. Manuel

AU - Kopfer, Herbert

AU - Schutten, Johannes M.J.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - METIS-256273

KW - Vehicle Routing and Scheduling

KW - EC Social Legislation

KW - Dynamic Programming

KW - IR-70216

M3 - Report

SN - 9789038617121

T3 - BETA Working Paper

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

PB - University of Twente, Research School for Operations Management and Logistics (BETA)

CY - Enschede

ER -

Kok AL, Meyer CM, Kopfer H, Schutten JMJ. A dynamic programming heuristic for the vehicle routing problem with time windows and EC social legislation. Enschede: University of Twente, Research School for Operations Management and Logistics (BETA), 2009. 30 p. (BETA Working Paper; 270).