A dynamic programming heuristic for vehicle routing with time-dependent travel times and required breaks.

Research output: Contribution to journalArticleAcademicpeer-review

55 Downloads (Pure)

Abstract

For the intensively studied vehicle routing problem (VRP), two real-life restrictions have received only minor attention in the VRP-literature: traffic congestion and driving hours regulations. Traffic congestion causes late arrivals at customers and long travel times resulting in large transport costs. To account for traffic congestion, time-dependent travel times should be considered when constructing vehicle routes. Next, driving hours regulations, which restrict the available driving and working times for truck drivers, must be respected. Since violations are severely fined, also driving hours regulations should be considered when constructing vehicle routes, even more in combination with congestion problems. The objective of this paper is to develop a solution method for the VRP with time windows (VRPTW), time-dependent travel times, and driving hours regulations. The major difficulty of this VRPTW extension is to optimize each vehicle’s departure times to minimize the duty time of each driver. Having compact duty times leads to cost savings. However, obtaining compact duty times is much harder when time-dependent travel times and driving hours regulations are considered. We propose a restricted dynamic programming (DP) heuristic for constructing the vehicle routes, and an efficient heuristic for optimizing the vehicle’s departure times for each (partial) vehicle route, such that the complete solution algorithm runs in polynomial time. Computational experiments demonstrate the trade-off between travel distance minimization and duty time minimization, and illustrate the cost savings of extending the depot opening hours such that traveling before the morning peak and after the evening peak becomes possible.
Original languageEnglish
Pages (from-to)83-108
JournalFlexible services and manufacturing journal
Volume2010
Issue number22
DOIs
Publication statusPublished - 2010

Fingerprint

Vehicle routing
Travel time
Dynamic programming
Traffic congestion
Truck drivers
Heuristics
Costs
Polynomials
Experiments

Keywords

  • METIS-274470
  • IR-76951

Cite this

@article{a6d449a0eca24676b77dfad98569e77d,
title = "A dynamic programming heuristic for vehicle routing with time-dependent travel times and required breaks.",
abstract = "For the intensively studied vehicle routing problem (VRP), two real-life restrictions have received only minor attention in the VRP-literature: traffic congestion and driving hours regulations. Traffic congestion causes late arrivals at customers and long travel times resulting in large transport costs. To account for traffic congestion, time-dependent travel times should be considered when constructing vehicle routes. Next, driving hours regulations, which restrict the available driving and working times for truck drivers, must be respected. Since violations are severely fined, also driving hours regulations should be considered when constructing vehicle routes, even more in combination with congestion problems. The objective of this paper is to develop a solution method for the VRP with time windows (VRPTW), time-dependent travel times, and driving hours regulations. The major difficulty of this VRPTW extension is to optimize each vehicle’s departure times to minimize the duty time of each driver. Having compact duty times leads to cost savings. However, obtaining compact duty times is much harder when time-dependent travel times and driving hours regulations are considered. We propose a restricted dynamic programming (DP) heuristic for constructing the vehicle routes, and an efficient heuristic for optimizing the vehicle’s departure times for each (partial) vehicle route, such that the complete solution algorithm runs in polynomial time. Computational experiments demonstrate the trade-off between travel distance minimization and duty time minimization, and illustrate the cost savings of extending the depot opening hours such that traveling before the morning peak and after the evening peak becomes possible.",
keywords = "METIS-274470, IR-76951",
author = "A.L. Kok and Hans, {Elias W.} and Schutten, {Johannes M.J.} and Zijm, {Willem H.M.}",
note = "Open access article From the issue entitled {"}Special Issue: Logistics in Supply Chains (Part 1){"}",
year = "2010",
doi = "10.1007/s10696-011-9077-4",
language = "English",
volume = "2010",
pages = "83--108",
journal = "Flexible services and manufacturing journal",
issn = "1936-6582",
publisher = "Springer",
number = "22",

}

TY - JOUR

T1 - A dynamic programming heuristic for vehicle routing with time-dependent travel times and required breaks.

AU - Kok, A.L.

AU - Hans, Elias W.

AU - Schutten, Johannes M.J.

AU - Zijm, Willem H.M.

N1 - Open access article From the issue entitled "Special Issue: Logistics in Supply Chains (Part 1)"

PY - 2010

Y1 - 2010

N2 - For the intensively studied vehicle routing problem (VRP), two real-life restrictions have received only minor attention in the VRP-literature: traffic congestion and driving hours regulations. Traffic congestion causes late arrivals at customers and long travel times resulting in large transport costs. To account for traffic congestion, time-dependent travel times should be considered when constructing vehicle routes. Next, driving hours regulations, which restrict the available driving and working times for truck drivers, must be respected. Since violations are severely fined, also driving hours regulations should be considered when constructing vehicle routes, even more in combination with congestion problems. The objective of this paper is to develop a solution method for the VRP with time windows (VRPTW), time-dependent travel times, and driving hours regulations. The major difficulty of this VRPTW extension is to optimize each vehicle’s departure times to minimize the duty time of each driver. Having compact duty times leads to cost savings. However, obtaining compact duty times is much harder when time-dependent travel times and driving hours regulations are considered. We propose a restricted dynamic programming (DP) heuristic for constructing the vehicle routes, and an efficient heuristic for optimizing the vehicle’s departure times for each (partial) vehicle route, such that the complete solution algorithm runs in polynomial time. Computational experiments demonstrate the trade-off between travel distance minimization and duty time minimization, and illustrate the cost savings of extending the depot opening hours such that traveling before the morning peak and after the evening peak becomes possible.

AB - For the intensively studied vehicle routing problem (VRP), two real-life restrictions have received only minor attention in the VRP-literature: traffic congestion and driving hours regulations. Traffic congestion causes late arrivals at customers and long travel times resulting in large transport costs. To account for traffic congestion, time-dependent travel times should be considered when constructing vehicle routes. Next, driving hours regulations, which restrict the available driving and working times for truck drivers, must be respected. Since violations are severely fined, also driving hours regulations should be considered when constructing vehicle routes, even more in combination with congestion problems. The objective of this paper is to develop a solution method for the VRP with time windows (VRPTW), time-dependent travel times, and driving hours regulations. The major difficulty of this VRPTW extension is to optimize each vehicle’s departure times to minimize the duty time of each driver. Having compact duty times leads to cost savings. However, obtaining compact duty times is much harder when time-dependent travel times and driving hours regulations are considered. We propose a restricted dynamic programming (DP) heuristic for constructing the vehicle routes, and an efficient heuristic for optimizing the vehicle’s departure times for each (partial) vehicle route, such that the complete solution algorithm runs in polynomial time. Computational experiments demonstrate the trade-off between travel distance minimization and duty time minimization, and illustrate the cost savings of extending the depot opening hours such that traveling before the morning peak and after the evening peak becomes possible.

KW - METIS-274470

KW - IR-76951

U2 - 10.1007/s10696-011-9077-4

DO - 10.1007/s10696-011-9077-4

M3 - Article

VL - 2010

SP - 83

EP - 108

JO - Flexible services and manufacturing journal

JF - Flexible services and manufacturing journal

SN - 1936-6582

IS - 22

ER -