The Bike Sharing Repositioning Problem with Fixed Routes and Time Windows

This paper addresses a problem in the area of urban transportation, that of dealing with the repositioning of bikes in public bike sharing systems, a notoriously difficult pick-up and delivery vehicle routing problem. We study a special case of this operation, which we call the Bike Sharing Repositioning Problem with Fixed Routes and Time Windows (\emph{BSRP/FRTW}). An integer programming formulation of the BSRP/FRTW is proposed. Strategies compatible with current practices for similar pickup and delivery problems are presented. A column generation approach based on a branch-and-price scheme that is solved by dynamic programming is described. Preliminary computational experience (to be reported in the future) is promising.