Scientific Program > Talks by Speaker > Rigonat Desiree

Success of bike sharing systems depends on the operators' ability to provide an adequate level of service. To this end, operators commonly deploy a fleet of vehicles to redistribute bicycles so that customers do not find stations empty or full. The problems of handling station inventory and routing the fleet have been widely explored in the literature, yet not frequently together. Moreover, most studies focus on the single time-period case (modelling night rebalancing) with only a handful dealing with the multi-period case (day rebalancing).

This work proposes an inventory routing model for the day rebalancing problem as well as an exact resolution approach based on branch-and-price.

The model describes the evolution of station inventory as function of both users' and vehicles' activity, instead of having “ideal” levels provided as input (as commonly found in the literature). The routing component follows a “prize collection” approach where the vehicles are routed to perform the most valuable operations in the available time. The objective is to minimise unsatisfied demand.

The model is decomposed in a formulation suitable for resolution via column generation: a master problem that handles inventory and a subproblem that generates feasible pickup and drop-offs patterns. The column generation is embedded in a branch-and-price algorithm.

The proposed approach was tested on instances obtained from real data from a European capital as well as on randomly generated ones. All have dimensions comparable to those presented in literature. Results show the effectiveness of the proposed method and offer some insights for operational planning.