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.

### The capacitated orienteering problem

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2015
2015
Bock, Adrian; Sanità, Laura
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4063948
• ND
• 7
• 6