EURO 2025 Leeds
Abstract Submission

2791. A Hybrid Matheuristic and Clustering Algorithm to Solve the Districting Problem in Public Bicycles Shared Systems

Invited abstract in session WD-38: Privacy-Aware and Optimization-Driven AI Systems, stream Data Science meets Optimization.

Wednesday, 14:30-16:00
Room: Michael Sadler LG19

Authors (first author is the speaker)

1. Guillermo Cabrera-Guerrero
Pontificia Universidad Catolica de Valparaiso
2. Pablo Andrés Maya Duque
Industrial Engineering, Universidad de Antioquia
3. Jalid Danoun
Pontificia Universidad Católica de Valparaiso
4. Carolina Lagos
Pontificia Universidad Católica de Valparaíso

Abstract

Bicycle Sharing Systems (BSS) have emerged as 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 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 IP problem.
Previously, 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, we implement two clustering strategies to provide the local search algorithm with better clusters.
We try the well-known k-means and fuzzy c-means algorithms to provide our local search matheuristic algorithm with different grids to seek. The results significantly improve performance compared to the arbitrary predefined 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.

Keywords

Status: accepted

Back to the list of papers