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

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

Research output: Contribution to journalArticleAcademicpeer-review

58 Citations (Scopus)

Abstract

In practice, apart from the problem of vehicle routing, schedulers also face the problem of finding 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 restricted dynamic programming heuristic for the vehicle routing problem with time windows and the full European social legislation on drivers' driving and working hours. The problem we consider includes all rules in this legislation, whereas in the literature only a basic set of rules has been addressed. In addition to this basic set of rules, the legislation contains a set of modifications that allow for more flexibility. To include the legislation in the restricted dynamic programming heuristic, we propose a break scheduling heuristic. Computational results show that our method finds solutions to benchmark instances—which only consider the basic set of rules—with 18% fewer vehicles and 5% less travel distance than state-of-the-art approaches. Moreover, our results are obtained with significantly less computational effort. Furthermore, the results show that including a set of rules on drivers' working hours—which has been generally ignored in the literature—has a significant impact on the resulting vehicle schedules: 3.9% more vehicle routes and 1.0% more travel distances are needed. Finally, using the modified rules of the legislation leads to an additional reduction of 4% in the number of vehicles and of 1.5% in travel distances. Therefore, the modified rules should be exploited in practice
Original languageEnglish
Pages (from-to)442-454
JournalTransportation science
Volume44
Issue number4
DOIs
Publication statusPublished - 2010

Fingerprint

social law
Vehicle routing
Dynamic programming
European Community
heuristics
programming
driver
legislation
working hours
travel
scheduling
Scheduling
flexibility
time
European Union

Keywords

  • METIS-271609
  • IR-76953

Cite this

@article{49c40ab98fbd4ef1b4b1fb506a95d716,
title = "A dynamic programming heuristic for the vehicle routing problem with time windows and European Community social legislation",
abstract = "In practice, apart from the problem of vehicle routing, schedulers also face the problem of finding 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 restricted dynamic programming heuristic for the vehicle routing problem with time windows and the full European social legislation on drivers' driving and working hours. The problem we consider includes all rules in this legislation, whereas in the literature only a basic set of rules has been addressed. In addition to this basic set of rules, the legislation contains a set of modifications that allow for more flexibility. To include the legislation in the restricted dynamic programming heuristic, we propose a break scheduling heuristic. Computational results show that our method finds solutions to benchmark instances—which only consider the basic set of rules—with 18{\%} fewer vehicles and 5{\%} less travel distance than state-of-the-art approaches. Moreover, our results are obtained with significantly less computational effort. Furthermore, the results show that including a set of rules on drivers' working hours—which has been generally ignored in the literature—has a significant impact on the resulting vehicle schedules: 3.9{\%} more vehicle routes and 1.0{\%} more travel distances are needed. Finally, using the modified rules of the legislation leads to an additional reduction of 4{\%} in the number of vehicles and of 1.5{\%} in travel distances. Therefore, the modified rules should be exploited in practice",
keywords = "METIS-271609, IR-76953",
author = "A.L. Kok and C.M. Meyer and H. Kopfer and Schutten, {Johannes M.J.}",
year = "2010",
doi = "10.1287/trsc.1100.0331",
language = "English",
volume = "44",
pages = "442--454",
journal = "Transportation science",
issn = "0041-1655",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "4",

}

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

In: Transportation science, Vol. 44, No. 4, 2010, p. 442-454.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Kok, A.L.

AU - Meyer, C.M.

AU - Kopfer, H.

AU - Schutten, Johannes M.J.

PY - 2010

Y1 - 2010

N2 - In practice, apart from the problem of vehicle routing, schedulers also face the problem of finding 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 restricted dynamic programming heuristic for the vehicle routing problem with time windows and the full European social legislation on drivers' driving and working hours. The problem we consider includes all rules in this legislation, whereas in the literature only a basic set of rules has been addressed. In addition to this basic set of rules, the legislation contains a set of modifications that allow for more flexibility. To include the legislation in the restricted dynamic programming heuristic, we propose a break scheduling heuristic. Computational results show that our method finds solutions to benchmark instances—which only consider the basic set of rules—with 18% fewer vehicles and 5% less travel distance than state-of-the-art approaches. Moreover, our results are obtained with significantly less computational effort. Furthermore, the results show that including a set of rules on drivers' working hours—which has been generally ignored in the literature—has a significant impact on the resulting vehicle schedules: 3.9% more vehicle routes and 1.0% more travel distances are needed. Finally, using the modified rules of the legislation leads to an additional reduction of 4% in the number of vehicles and of 1.5% in travel distances. Therefore, the modified rules should be exploited in practice

AB - In practice, apart from the problem of vehicle routing, schedulers also face the problem of finding 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 restricted dynamic programming heuristic for the vehicle routing problem with time windows and the full European social legislation on drivers' driving and working hours. The problem we consider includes all rules in this legislation, whereas in the literature only a basic set of rules has been addressed. In addition to this basic set of rules, the legislation contains a set of modifications that allow for more flexibility. To include the legislation in the restricted dynamic programming heuristic, we propose a break scheduling heuristic. Computational results show that our method finds solutions to benchmark instances—which only consider the basic set of rules—with 18% fewer vehicles and 5% less travel distance than state-of-the-art approaches. Moreover, our results are obtained with significantly less computational effort. Furthermore, the results show that including a set of rules on drivers' working hours—which has been generally ignored in the literature—has a significant impact on the resulting vehicle schedules: 3.9% more vehicle routes and 1.0% more travel distances are needed. Finally, using the modified rules of the legislation leads to an additional reduction of 4% in the number of vehicles and of 1.5% in travel distances. Therefore, the modified rules should be exploited in practice

KW - METIS-271609

KW - IR-76953

U2 - 10.1287/trsc.1100.0331

DO - 10.1287/trsc.1100.0331

M3 - Article

VL - 44

SP - 442

EP - 454

JO - Transportation science

JF - Transportation science

SN - 0041-1655

IS - 4

ER -