A hybrid algorithm for time-dependent vehicle routing problem with time windows

Abstract

In this paper, we study the duration-minimizing time-dependent vehicle routing problem with time windows (DM-TDVRPTW), where time-dependent travel times represent different levels of road congestion throughout the day. The departure time from depot becomes an important decision to reduce the route duration. We provide an alternative arc-based mixed-integer programming model with explicit arc time zone index. For larger scale instances, we extend the segment-based evaluation method to speed up the feasibility check of a given vehicle route. It is thereafter incorporated to implement an efficient hybrid adaptive large neighborhood search with tabu search (ALNS-TS) algorithm, to explore both feasible and infeasible solution spaces. The ALNS-TS exploits the strength of diversification in ALNS through adaptive control of neighborhood size, as well as the strength of intensification in TS by limiting the maximum number of steps allowed without improvement. Related parameters are tuned using an automatic configuration tool to determine the best set of configurations. The computational results demonstrate its excellent performance on the benchmark instances proposed by Dabia et al. (2013), obtaining optimal solutions for all instances with 25 customers and improving best-known solutions for 36 instances with 50 and 100 customers. Computational experiments are also conducted to evaluate the effectiveness of the algorithm on an extra set of large scale instances and on the simplified VRPTW instances.