An Approximation Algorithm for the Capacitated Arc Routing Problem

Sanne Wøhlk

doi:10.2174/1874243200802010008

An Approximation Algorithm for the Capacitated Arc Routing Problem

Authors:

Wøhlk, Sanne
Close
0000-0003-3847-7528
Department of Economics and Business Economics, Aarhus BSS, Aarhus University

DOI:

10.2174/1874243200802010008

Abstract:

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.

Type:

Journal article

Language:

English

Published in:

Open Operational Research Journal, 2008, Vol 2, p. 8-12

Main Research Area:

Social science

Publication Status:

Published

Review type:

Peer Review

Submission year:

2008

Scientific Level:

Scientific

ID:

268842592

An Approximation Algorithm for the Capacitated Arc Routing Problem

Full text access

On-site access

At institution

Example	Finds records
water{}	containing the word "water".
water supplies"{}"	containing the phrase "water supplies".
author:"Doe, John"author:"{}"	containing the prase "Doe, John" in the author field.
title:IEEEtitle:{}	containing the word "IEEE" in the title field.
Need more help?	Advanced search tutorial