Iterated greedy heuristic for the time-dependent prize-collecting arc routing problem

•We study the time-dependent prize-collecting arc routing problem (TD-PARP).•We propose an iterated greedy (IG) heuristic for TD-PARP.•The proposed IG heuristic outperforms existing approaches.

The time-dependent prize-collecting arc routing problem (TD-PARP) determines a number of full truckload orders and plans a vehicle route to maximize profit, which is calculated as total collected revenue (prizes) minus total travel cost. The travel cost on an arc is proportional to the travel time via the arc and changes over time. This study proposes an iterated greedy (IG) heuristic for the TD-PARP. Computational study on 41 benchmark problems indicates that the proposed IG heuristic outperforms existing approaches. The proposed IG heuristic obtains the best solutions to most of the benchmark problems.