Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules

Research output: Book/ReportReportOther research output

58 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 vehicles 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 emonstrate 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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Research School for Operations Management and Logistics (BETA)
Number of pages30
ISBN (Print)9789038621951
Publication statusPublished - 2010

Publication series

NameBeta working papers
PublisherBeta Research School for Operations Management and Logistics, University of Twente
No.305

Keywords

  • duty time minimization
  • Restricted dynamic programming
  • IR-70204
  • Time-dependent travel times
  • Driving hours regulations
  • VRPTW

Cite this

Kok, A. L., Hans, E. W., Schutten, J. M. J., & Zijm, W. H. M. (2010). Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules. (Beta working papers; No. 305). Enschede: University of Twente, Research School for Operations Management and Logistics (BETA).
Kok, A.L. ; Hans, Elias W. ; Schutten, Johannes M.J. ; Zijm, Willem H.M. / Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules. Enschede : University of Twente, Research School for Operations Management and Logistics (BETA), 2010. 30 p. (Beta working papers; 305).
@book{3e34ce6f56d041a4a677113f7a2b22ee,
title = "Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules",
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 vehicles 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 emonstrate 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 = "duty time minimization, Restricted dynamic programming, IR-70204, Time-dependent travel times, Driving hours regulations, VRPTW",
author = "A.L. Kok and Hans, {Elias W.} and Schutten, {Johannes M.J.} and Zijm, {Willem H.M.}",
year = "2010",
language = "Undefined",
isbn = "9789038621951",
series = "Beta working papers",
publisher = "University of Twente, Research School for Operations Management and Logistics (BETA)",
number = "305",
address = "Netherlands",

}

Kok, AL, Hans, EW, Schutten, JMJ & Zijm, WHM 2010, Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules. Beta working papers, no. 305, University of Twente, Research School for Operations Management and Logistics (BETA), Enschede.

Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules. / Kok, A.L.; Hans, Elias W.; Schutten, Johannes M.J.; Zijm, Willem H.M.

Enschede : University of Twente, Research School for Operations Management and Logistics (BETA), 2010. 30 p. (Beta working papers; No. 305).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules

AU - Kok, A.L.

AU - Hans, Elias W.

AU - Schutten, Johannes M.J.

AU - Zijm, Willem H.M.

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 vehicles 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 emonstrate 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 vehicles 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 emonstrate 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 - duty time minimization

KW - Restricted dynamic programming

KW - IR-70204

KW - Time-dependent travel times

KW - Driving hours regulations

KW - VRPTW

M3 - Report

SN - 9789038621951

T3 - Beta working papers

BT - Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules

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

CY - Enschede

ER -

Kok AL, Hans EW, Schutten JMJ, Zijm WHM. Vehicle Routing with Traffic Congestion and Drivers' Driving and Working Rules. Enschede: University of Twente, Research School for Operations Management and Logistics (BETA), 2010. 30 p. (Beta working papers; 305).