The Time-Dependent Prize-Collecting Arc Routing Problem

Daniel Black, R. Eglese, Sanne Wøhlk

Research output: Contribution to journalArticlepeer-review


A new problem is introduced named the Time-Dependent Prize-Collecting Arc Routing Problem (TD-PARP). It is particularly relevant to situations where a transport manager has to choose between a number of full truck load pick-ups and deliveries on a road network where travel times change with the time of day. Two metaheuristic algorithms, one based on Variable Neighborhood Search and one based on Tabu Search, are proposed and tested for a set of benchmark problems, generated from real road networks and travel time information. Both algorithms are capable of finding good solutions, though the VNS approach generally shows better performance.
Original languageEnglish
Pages (from-to)526-535
JournalComputers and Operations Research
Issue number2
Early online date5 Oct 2012
Publication statusPublished - Feb 2013


  • Prize-collecting
  • Arc routing
  • Time-dependent


Dive into the research topics of 'The Time-Dependent Prize-Collecting Arc Routing Problem'. Together they form a unique fingerprint.

Cite this