The Capacitated Orienteering Problem

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.