Balancing the stations of a self service ‘bike hire’ system

Balancing the stations of a self service ‘bike hire’ system

0.00 Avg rating0 Votes
Article ID: iaor20127582
Volume: 45
Issue: 1
Start Page Number: 37
End Page Number: 61
Publication Date: Jan 2011
Journal: RAIRO - Operations Research
Authors: , , , , , ,
Keywords: allocation: resources, combinatorial optimization, programming: dynamic
Abstract:

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 v V x v = v V y v equ1 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.

Reviews

Required fields are marked *. Your email address will not be published.