Aarhus University Seal / Aarhus Universitets segl

An Approximation Algorithm for the Capacitated Arc Routing Problem

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • CORAL - Centre for Operations Research Applications in Logistics
  • Department of Business Studies
In this paper we consider approximation of the Capacitated Arc Routing Problem, which is the problem of servicing a set of edges in a graph using a fleet of capacity constrained vehicles.
We present a 7/2 - 3/W-approximation algorithm for the problem and prove that this algorithm outperforms the only existing approximation algorithm for the problem. Furthermore, we give computational results showing that the new algorithm performs very well  in practice.
Original languageEnglish
JournalOpen Operational Research Journal
Volume2
Pages (from-to)8-12
ISSN1874-2432
DOIs
Publication statusPublished - 2008

See relations at Aarhus University Citationformats

ID: 36465