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.