A hybrid population-based algorithm for the time-dependent shortest path and vehicle routing problem

In urban logistics, travel times between customers vary with traffic throughout the day. Different paths can connect two points, depending on the departure time of vehicles from a node of the graph. Time intervals with varying congestion levels are considered in the Time-Dependent Shortest Path Vehicle Routing Problem (TDSPVRP). The goal is to determine the least-cost routes to meet customer demands. Travel times are determined by solving the Time-Dependent Shortest Path Problem (TDSPP). This work proposes a heuristic approach to solve the TDSPVRP. The method uses a new ruin-and-recreate operator based on a recent procedure from the literature and an efficient strategy to evaluate and store time intervals, avoiding the recalculation of TDSPP solution costs. Tests on real-world instances show that the method improved several known solutions in competitive computational times.