A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems

Abstract

A matheuristic approach that combines a reduced variable neighbourhood search (rVNS) algorithm and a mathematical programming (MP) solver to solve a novel model for the districting problem in a public bicycle-sharing system is presented. The problem is modelled as an integer programming problem. While the rVNS algorithm aims to find a high-quality set of centres for the repositioning zones, the MP solver computes the optimal allocation network of the stations to the centres of the repositioning zones. We use a predefined grid to reduce the search space the rVNS needs to explore. The proposed approach obtains promising results for small and medium-sized instances, and is also able to handle large-sized models.

Keywords

• balancing strategy
• repositioning zone
• demand zone
• bicycle-sharing system
• variable neighbourhood search
• mathematical programming