期刊
RAIRO-OPERATIONS RESEARCH
卷 45, 期 1, 页码 37-61出版社
EDP SCIENCES S A
DOI: 10.1051/ro/2011102
关键词
Approximation algorithm; routing problem; self service transport system
This paper is motivated by operating self service transport systems that flourish nowadays. In cities where such systems have been set up with bikes, trucks travel to maintain a suitable number of bikes per station. It is natural to study a version of the C-delivery TSP defined by Chalasani and Motwani in which, unlike their definition, C is part of the input: each vertex v of a graph G = (V, E) has a certain amount x(v) of a commodity and wishes to have an amount equal to y(v) (we assume that Sigma(v is an element of V) x(v) = Sigma(v is an element of V) y(v) and all quantities are assumed to be integers); given a vehicle of capacity C, find a minimal route that balances all vertices, that is, that allows to have an amount y(v) of the commodity on each vertex v. This paper presents among other things complexity results, lower bounds, approximation algorithms, and a polynomial algorithm when G is a tree.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据