Optimizing departure times in vehicle routes

Research output: Book/ReportReportProfessional

101 Downloads (Pure)


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


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

Cite this