Program > By author > Crainic Teodor Gabriel

A matheuristic for the anticipatory service network design of bike sharing systems
Bruno Albert Neumann Saavedra  1@  , Michael Römer  2@  , Teodor Gabriel Crainic  3@  , Bernard Gendron  3@  , Dirk Christian Mattfeld  1@  
1 : Technische Universität Braunschweig
2 : Martin-Luther-Universität Halle-Wittenberg
3 : Université de Montréal

Bike sharing systems (BSS) have enhanced the public transportation system in several cities by offering bike rentals through automated rental stations. User can realize short-term free-of-charge trips between any pair of the BSS's stations. This provides a suitable solution for the “last mile” problem between other modes of transport and final destination of the user.

In order to fulfill a high percentage of the expected demand, a sufficient provision of bikes and free bike racks need to be ensured at each station during the day. However, due to spatial and temporal characteristics of the demand, e.g., commuting, some stations tend to run empty or full at particular times of a day. Empty and full stations prohibit rental and return of bikes, respectively. To rebalance the system, redistribution vehicles are available in order to relocate bikes among stations, yielding suitable time-of-day target fill levels.

We present the anticipatory time-dependent service network design, the core of the BSS's tactical planning level. The optimization model anticipates the scheduling of redistribution vehicles, bike relocation decisions, by considering the operational costs. The multi-objective function minimizes the penalizations applied for expected unmet demand and violation of self-predefined fill level specifications.

We propose a matheuristic to solve real-world-size problem instances. The solution approach combines neighborhood search with exact solution techniques provided by a commercial mixed-integer linear programming solver. The matheuristic is tested by computational experiments on a set of challenging problem instances.


Online user: 2