کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421084 684132 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 195, 20 November 2015, Pages 31–42
نویسندگان
, ,