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?V s , t ? V , node profits ?:V?N ? : V ? N and a length bound D D . The goal is to find an s s t t path of length at most D 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 r : V ? N and a capacity bound C C . The goal is to find an s s t t path of length at most D D that collects maximum profit from nodes whose total demand does not exceed the capacity bound C C . 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.
orienteering vehicle routing approximation algorithms