The Capacitated Orienteering Problem

In the Orienteering Problem, we are given an undirected, metric graph G=(V,E)G=(V,E), starting and end nodes s,t∈Vs,t∈V, node profits π:V→Nπ:V→N and a length bound DD. The goal is to find an ss–tt path of length at most DD 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→Nr:V→N and a capacity bound CC. The goal is to find an ss–tt path of length at most DD that collects maximum profit from nodes whose total demand does not exceed the capacity bound CC.We give a (3+ε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.