A Template-Based Hybrid Large Neighborhood Search for the Consistent Vehicle Routing Problem with Time-Dependent Travel Times

Customer satisfaction attracts increasing attention in competitive environments. The consistent vehicle routing problem (ConVRP), introduced in recent years, incorporates customer satisfaction into VRP. In ConVRP, vehicle routes must be designed for multiple periods, and each customer must be visited by the same driver at roughly the same time on each period. Previous ConVRP research models travel times as constant and based only on distance. This is unrealistic for urban areas, where travel times vary dynamically with factors like congestion and time of day. The time-dependent VRP (TDVRP) incorporates time-varying travel times. In this paper, the ConVRP is considered with time-dependent travel times to integrate the TDVRP and ConVRP models. A mixed-integer linear programming (MILP) model is proposed for the new problem, termed the consistent TDVRP (ConTDVRP). We extend the ConVRP benchmark instances from the literature by incorporating time-dependent travel times. The model is solved using a solver for small-scale instances. Since the new problem -an extension of the two aforementioned models- is NP-hard, we propose a template-based hybrid large neighborhood search (THLNS) algorithm that incorporates variable neighborhood search (VNS) to solve it. An iterative procedure is also presented to modify a heuristic departure-time adjustment in the literature to be used with time-dependent travel times. Computational experiments and sensitivity analysis are performed on new extended instances to evaluate the efficiency of the proposed algorithm. Three presented methods in ConVRP literature are adapted to solve ConTDVRP and the results of proposed approach compared with them for three time-dependent speed profiles on extended instances. The results demonstrate that the proposed method not only achieves consistent solutions with reduced computation time but also delivers solutions with 13.38%, 10.61%, and 35.67% lower average travel times compared to the three alternative methods. Departure-time adjustment also results in 17.48% lower average travel times and 5.91% better time consistency across all benchmark instances and speed profiles.