Monday, 15:45 - 16:10 h, Room: H 3005


Frédéric Meunier
A routing problem raised by self-service bike hiring systems

Coauthors: Daniel Chemla, Roberto Wolfler Calvo


Operating bike-sharing systems raises many problems. One of the most natural is the repositioning of the bikes with the help of one or many trucks.
We focus in this talk on the case when there is only one truck. We are given a graph whose vertices model stations. The current repartition of the bikes is known. We wish to move these bikes with the truck in order to reach a target repartition, and we want to realize this task at a minimal cost. The concrete motivation corresponds to the situation encountered at the end of the night, when very few bikes are moving.
A part of the talk will be devoted to special polynomial cases and to approximation algorithms. An efficient method able to solve in practice instances of reasonable size will also be presented: this method combines the exact computation of a natural lower bound and a local search exploiting theoretical properties of the problem. Open questions will also be discussed.


Talk 2 of the invited session Mon.3.H 3005
"Exact and approximation algorithms on graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  Payday Loans In North Carolina. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.