The time-dependent capacitated profitable tour problem with time windows and precedence constraints

摘要

Highlights?A new pickup and delivery problem with time dependent travel times is introduced.?Both an exact and heuristic procedure are defined to solve this problem.?Novel and strong dominance criteria are used to speed up the procedures.?The exact algorithm is able to solve instances with up to 150 locations.?The fast heuristic is able to find optimal solutions for 32 out of the 34 instances.AbstractWe introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time