The Bicycle Sharing Systems (BSS) have emerged as a sustainable and convenient mode of urban transportation, providing an alternative to traditional commuting methods. Despite its benefits, BSS’s efficient management and optimization face inherent challenges, ranging from system demand variations to station capacity constraints. This paper addresses a tactical problem in BSS, namely the districting problem. The districting BSS problem aims to find a network configuration where the stations are allocated to cluster centres so that each cluster meets balance constraints. The problem is modelled as an integer programming problem. In a previous work [4], we implemented a matheuristic based on a local search algorithm which selects the centre of each cluster of stations. Then, a mathematical solver solves the allocation of the stations to the centres, considering balancing constraints. In that paper, we limited our local search to choosing a cluster centre within predefined clusters to reduce the search space. This paper investigates the effect of the clustering strategy on the local search’s performance. Thus, this paper implements a clustering strategy to provide the local search algorithm with better clusters or grids. We try the well-known k-means algorithm to provide our local search matheuristic algorithm with different grids to seek on. The obtained results significantly improve the algorithms’ performance compared to the arbitrary pre-defined grid used in our previous work. Also, results show that some grid designs tend to be better than others and, thus, impact the final results.