Optimizing departure times in vehicle routes

Research output: Book/ReportReportProfessional

39 Downloads (Pure)

Abstract

Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. However, in practice, temporal traffic congestions make that such solutions are not optimal with respect to minimizing the total duty time. Furthermore, VRPTW solutions do not account for complex driving hours regulations, which severely restrict the daily travel time available for a truck driver. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing step of solving a VRPTW. We propose an ILP-formulation that minimizes the total duty time. The obtained solutions are feasible with respect to driving hours regulations and they account for temporal traffic congestions by modeling time-dependent travel times. For the latter, we assume a piecewise constant speed function. Computational experiments show that problem instances of realistic sizes can be solved to optimality within practical computation times. Furthermore, duty time reductions of 8 percent can be achieved. Finally, the results show that ignoring time-dependent travel times and driving hours regulations during the development of vehicle routes leads to many infeasible vehicle routes. Therefore, vehicle routing methods should account for these real-life restrictions.
Original languageUndefined
Place of Publicationonbekend
PublisherUniversity of Twente
Number of pages17
ISBN (Print)9789038612256
Publication statusPublished - 1 Jan 2008

Publication series

NameBETA Working Papers
PublisherUniversity of Twente
No.236

Keywords

  • IR-70229
  • ILP-formulation
  • Duty times
  • Driving hours regulations
  • Time-dependent travel times
  • Vehicle scheduling
  • METIS-247527

Cite this

Kok, A. L., Hans, E. W., & Schutten, J. M. J. (2008). Optimizing departure times in vehicle routes. (BETA Working Papers; No. 236). onbekend: University of Twente.
Kok, A.L. ; Hans, Elias W. ; Schutten, Johannes M.J. / Optimizing departure times in vehicle routes. onbekend : University of Twente, 2008. 17 p. (BETA Working Papers; 236).
@book{c62b5381e90c497daceb01dc15017720,
title = "Optimizing departure times in vehicle routes",
abstract = "Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. However, in practice, temporal traffic congestions make that such solutions are not optimal with respect to minimizing the total duty time. Furthermore, VRPTW solutions do not account for complex driving hours regulations, which severely restrict the daily travel time available for a truck driver. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing step of solving a VRPTW. We propose an ILP-formulation that minimizes the total duty time. The obtained solutions are feasible with respect to driving hours regulations and they account for temporal traffic congestions by modeling time-dependent travel times. For the latter, we assume a piecewise constant speed function. Computational experiments show that problem instances of realistic sizes can be solved to optimality within practical computation times. Furthermore, duty time reductions of 8 percent can be achieved. Finally, the results show that ignoring time-dependent travel times and driving hours regulations during the development of vehicle routes leads to many infeasible vehicle routes. Therefore, vehicle routing methods should account for these real-life restrictions.",
keywords = "IR-70229, ILP-formulation, Duty times, Driving hours regulations, Time-dependent travel times, Vehicle scheduling, METIS-247527",
author = "A.L. Kok and Hans, {Elias W.} and Schutten, {Johannes M.J.}",
note = "ISBN 978-90-386-1225-6 / NUR 804",
year = "2008",
month = "1",
day = "1",
language = "Undefined",
isbn = "9789038612256",
series = "BETA Working Papers",
publisher = "University of Twente",
number = "236",
address = "Netherlands",

}

Kok, AL, Hans, EW & Schutten, JMJ 2008, Optimizing departure times in vehicle routes. BETA Working Papers, no. 236, University of Twente, onbekend.

Optimizing departure times in vehicle routes. / Kok, A.L.; Hans, Elias W.; Schutten, Johannes M.J.

onbekend : University of Twente, 2008. 17 p. (BETA Working Papers; No. 236).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Optimizing departure times in vehicle routes

AU - Kok, A.L.

AU - Hans, Elias W.

AU - Schutten, Johannes M.J.

N1 - ISBN 978-90-386-1225-6 / NUR 804

PY - 2008/1/1

Y1 - 2008/1/1

N2 - Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. However, in practice, temporal traffic congestions make that such solutions are not optimal with respect to minimizing the total duty time. Furthermore, VRPTW solutions do not account for complex driving hours regulations, which severely restrict the daily travel time available for a truck driver. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing step of solving a VRPTW. We propose an ILP-formulation that minimizes the total duty time. The obtained solutions are feasible with respect to driving hours regulations and they account for temporal traffic congestions by modeling time-dependent travel times. For the latter, we assume a piecewise constant speed function. Computational experiments show that problem instances of realistic sizes can be solved to optimality within practical computation times. Furthermore, duty time reductions of 8 percent can be achieved. Finally, the results show that ignoring time-dependent travel times and driving hours regulations during the development of vehicle routes leads to many infeasible vehicle routes. Therefore, vehicle routing methods should account for these real-life restrictions.

AB - Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. However, in practice, temporal traffic congestions make that such solutions are not optimal with respect to minimizing the total duty time. Furthermore, VRPTW solutions do not account for complex driving hours regulations, which severely restrict the daily travel time available for a truck driver. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing step of solving a VRPTW. We propose an ILP-formulation that minimizes the total duty time. The obtained solutions are feasible with respect to driving hours regulations and they account for temporal traffic congestions by modeling time-dependent travel times. For the latter, we assume a piecewise constant speed function. Computational experiments show that problem instances of realistic sizes can be solved to optimality within practical computation times. Furthermore, duty time reductions of 8 percent can be achieved. Finally, the results show that ignoring time-dependent travel times and driving hours regulations during the development of vehicle routes leads to many infeasible vehicle routes. Therefore, vehicle routing methods should account for these real-life restrictions.

KW - IR-70229

KW - ILP-formulation

KW - Duty times

KW - Driving hours regulations

KW - Time-dependent travel times

KW - Vehicle scheduling

KW - METIS-247527

M3 - Report

SN - 9789038612256

T3 - BETA Working Papers

BT - Optimizing departure times in vehicle routes

PB - University of Twente

CY - onbekend

ER -

Kok AL, Hans EW, Schutten JMJ. Optimizing departure times in vehicle routes. onbekend: University of Twente, 2008. 17 p. (BETA Working Papers; 236).