TY - JOUR

T1 - The Capacitated Orienteering Problem

AU - Bock, Adrian

AU - Sanità, Laura

PY - 2015/11/20

Y1 - 2015/11/20

N2 - In the Orienteering Problem, we are given an undirected, metric graph G=(V,E), starting and end nodes s,t ∈ V, node profits π:V → ℕ and a length bound D. The goal is to find an s-t path of length at most D that collects maximum profit. The Orienteering Problem is a fundamental network design problem and efficient algorithms for this problem have often been used as subroutine to develop efficient algorithms for a wide number of vehicle routing problems. The focus of this paper is on a natural generalization in which we also consider node demands r:V → ℕ and a capacity bound C. The goal is to find an s-t path of length at most D that collects maximum profit from nodes whose total demand does not exceed the capacity bound C. We give a (3+ε)-approximation algorithm for the Capacitated Orienteering Problem in general graphs, which improves over the previously best known approximation bound. We further obtain a PTAS on trees and a PTAS on Euclidean metrics. As one may expect, there is a number of capacitated vehicle routing problems where the Capacitated Orienteering Problem appears as subroutine. As a byproduct of our analysis, we develop new approximation results for some of those problems.

AB - In the Orienteering Problem, we are given an undirected, metric graph G=(V,E), starting and end nodes s,t ∈ V, node profits π:V → ℕ and a length bound D. The goal is to find an s-t path of length at most D that collects maximum profit. The Orienteering Problem is a fundamental network design problem and efficient algorithms for this problem have often been used as subroutine to develop efficient algorithms for a wide number of vehicle routing problems. The focus of this paper is on a natural generalization in which we also consider node demands r:V → ℕ and a capacity bound C. The goal is to find an s-t path of length at most D that collects maximum profit from nodes whose total demand does not exceed the capacity bound C. We give a (3+ε)-approximation algorithm for the Capacitated Orienteering Problem in general graphs, which improves over the previously best known approximation bound. We further obtain a PTAS on trees and a PTAS on Euclidean metrics. As one may expect, there is a number of capacitated vehicle routing problems where the Capacitated Orienteering Problem appears as subroutine. As a byproduct of our analysis, we develop new approximation results for some of those problems.

KW - Approximation algorithms

KW - Orienteering

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=84941419705&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2014.10.001

DO - 10.1016/j.dam.2014.10.001

M3 - Article

AN - SCOPUS:84941419705

SN - 0166-218X

VL - 195

SP - 31

EP - 42

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -