A Matheuristic Approach Based on Variable Neighborhood Search for the Static Repositioning Problem in Station-Based Bike-Sharing Systems

Abstract

In this paper, we study a novel static bike-sharing repositioning problem. There is a set of stations spread over a given area, each containing a number of operative bikes, damaged bikes, and free slots. The customers may pick up an operative bike from a station, use it, and return it to another station. Each station should have a target number of operative bikes to make it likely to meet customer demands. Furthermore, the damaged bikes should be removed from the stations. Given a fleet of available vehicles, the repositioning problem consists of designing the vehicles’ routes and calculating the number of operative (usable) and damaged (unusable) bikes that will be moved (loading instructions/loading policy) between stations and/or the depot. The objective is to minimize the weighted sum of the deviation from the target number of bikes for each station, the number of damaged bikes not removed, and the total time used by vehicles. To solve this problem, we propose a matheuristic based on a variable neighborhood search combined with several improving algorithms, including an integer linear programming model to optimize loading instructions. The algorithm was tested in instances based on real-world data and could find good solutions in reasonable computing times.

Keywords

• vehicle routing problem
• static bike-sharing repositioning problem
• matheuristic based on variable neighborhood search