The Capacitated Orienteering Problem
In the Orienteering Problem, we are given an undirected, metric graph G = (V, E), starting and end nodes s, t is an element of V, node profits pi : V -> N 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 -> N 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 + epsilon)-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. (C) 2014 Elsevier B.V. All rights reserved.