Solutions innovantes pour le repositionnement du partage de vélos

Les systèmes de vélos en libre-service existent depuis plus de 50 ans, surtout en Europe du Nord. Ils aident les gens à se déplacer et complètent les transports en commun. Ces systèmes ont plein d'avantages, comme être écologiques et rentables par rapport à d'autres moyens de transport. Pourtant, il y a encore des problèmes à régler, comme quand une station de vélos n'a plus de places libres pour garer les vélos, ou quand il n'y a pas assez de vélos dispo pour les utilisateurs. De plus, si les vélos disponibles sont endommagés, ça complique le fonctionnement global du système.

#Le défi du repositionnement

Ces problèmes mènent à ce qu'on appelle le Problème de Repositionnement des Vélos en Libre-Service (BRP). En gros, ça consiste à déplacer des vélos dans le système avec différents véhicules. L'objectif est de s'assurer que chaque station a le bon nombre de vélos en état de marche pour les utilisateurs tout en gérant les vélos endommagés.

Dans les systèmes de vélos en libre-service, il y a deux grands types. Le premier type est le système de Vélos en Libre-Service Basé sur des Stations (SBBS), qui permet aux utilisateurs de louer des vélos à des stations spécifiques et de les rendre à la même station ou à une autre station désignée. Le deuxième type est le système de Vélos Flottants (FFBS), où les utilisateurs peuvent prendre et déposer des vélos n'importe où.

#Repositionnement dynamique vs statique

Il y a deux stratégies pour repositionner les vélos : dynamique et statique. Dans le repositionnement dynamique, les vélos sont déplacés pendant que le système est utilisé, généralement pendant la journée. Dans le repositionnement statique, les vélos sont organisés pendant les moments où le système est moins utilisé, comme la nuit.

Cette discussion se concentre sur le repositionnement statique, spécifiquement dans les installations basées sur des stations. On appelle ça le Problème de Repositionnement Statique des Vélos en Libre-Service Basé sur des Stations (SBRP). Cette approche apporte des améliorations importantes au problème de repositionnement statique standard en incluant des éléments plus réalistes comme les vélos opérationnels et endommagés, ainsi qu'une variété de véhicules et plusieurs trajets entre les stations et le dépôt.

#Aperçu du problème

Dans le SBRP, on travaille avec un réseau représentant les stations de vélos et un dépôt. Chaque station de vélos a un nombre certain de places de parking libres, un stock initial de vélos (opérationnels et endommagés), et un nombre cible de vélos qu'elle devrait avoir à la fin d'une opération de repositionnement.

Un groupe de véhicules est responsable du déplacement des vélos. Chaque véhicule a sa propre capacité de charge et doit terminer son parcours dans un délai fixé, en commençant et en terminant au dépôt.

Une solution valide à ce problème implique de planifier des trajets pour les véhicules, ainsi que de spécifier combien de vélos (opérationnels et endommagés) seront déplacés à chaque station ou dépôt lors de chaque visite.

#Objectifs de l'effort de repositionnement

L'objectif principal de cet effort de repositionnement est de minimiser trois facteurs clés :

1. La différence entre le nombre cible de vélos à chaque station et le nombre réel après repositionnement.
2. Le nombre de vélos endommagés qui restent non collectés.
3. Le temps total dépensé par les véhicules.

#Méthode de solution proposée

Pour s'attaquer au SBRP, une nouvelle approche appelée matheuristique a été introduite. Ça combine des éléments de randomisation avec des méthodes d'optimisation mathématique.

#Phase 1 : Algorithme Multi-Démarrage Aléatoire

La première phase de la solution proposée construit des trajets pour chaque véhicule en utilisant un Algorithme Multi-Démarrage Aléatoire (RMS). Cette méthode construit une solution étape par étape. Chaque fois qu'une nouvelle station de vélos est ajoutée au trajet, elle vérifie quelle station serait la meilleure à visiter ensuite en fonction du nombre de vélos à déplacer et du temps que ça prendrait.

À chaque étape, l'état actuel du système est mis à jour. Ça veut dire qu'à chaque visite, le nombre de vélos au dépôt et aux stations est ajusté selon ce qui a été ramassé ou livré.

L'algorithme inclut un moyen d'encourager la sélection de stations plus proches et plus faciles d'accès tout en permettant encore des visites à des stations qui pourraient avoir plus de vélos disponibles. Chaque fois qu'une station potentielle est envisagée pour le prochain arrêt, un choix aléatoire est fait parmi les meilleures options disponibles.

#Phase 2 : Optimisation des instructions de chargement

Une fois qu'un trajet faisable est construit à chaque itération, l'étape suivante consiste à déterminer le meilleur plan de chargement pour ce trajet. Cela se fait à l'aide d'un modèle mathématique qui vise à minimiser les déséquilibres dans la disponibilité des vélos et le nombre de vélos endommagés qui restent non collectés.

Le modèle considère le nombre de vélos au dépôt et à chaque station, en s'assurant que les procédures de chargement et de déchargement respectent les contraintes de capacité des véhicules et le calendrier établi pour le trajet.

#Tests computationnels

Pour vérifier comment cette méthode proposée performe, une série de tests a été réalisée en utilisant des données réelles provenant de différents systèmes de vélos en libre-service.

Les tests étaient organisés en deux groupes de scénarios : l'un basé sur un système de vélos en libre-service à Palma, en Espagne, et l'autre à Vienne, en Autriche. Chaque scénario variait en termes de nombre de stations, d'inventaires initiaux de vélos, de capacités des véhicules et de temps maximums autorisés pour effectuer les trajets.

Les résultats ont montré que la méthode était capable de équilibrer efficacement les stations de vélos et de retirer les vélos endommagés dans la plupart des cas. Par exemple, dans le groupe de tests de Palma, l'algorithme a atteint un équilibre complet et a collecté tous les vélos endommagés dans près de 97 % des cas. En revanche, le groupe de Vienne a rencontré plus de défis, surtout avec un nombre plus important de stations. Cependant, même dans ces cas, des améliorations ont été observées avec davantage de véhicules ou des temps plus longs.

En termes de rapidité, l'algorithme était capable de trouver des solutions rapidement, souvent en quelques secondes.

#Comparaison avec les solutions existantes

La performance de cette nouvelle méthode a été comparée avec les approches précédentes trouvées dans la littérature. Dans les cas où des références étaient possibles, les résultats étaient similaires, ce qui indique que cette nouvelle méthode se défend bien et peut traiter les défis présentés dans le SBRP.

Bien que les méthodes existantes aient été conçues spécifiquement pour leurs problèmes, les ajustements faits pour intégrer les nouvelles variables ont donné des résultats comparables dans environ 83 % des cas testés.

#Conclusion

Cette recherche introduit une nouvelle façon de s'attaquer au Problème de Repositionnement Statique des Vélos en Libre-Service Basé sur des Stations. En tenant compte des vélos opérationnels et endommagés, des types de véhicules divers et de plusieurs visites, elle offre une solution plus réaliste pour gérer les systèmes de vélos en libre-service.

L'approche matheuristique combine efficacement randomisation et optimisation mathématique, ce qui aboutit à des solutions de haute qualité en peu de temps.

Des recherches supplémentaires visent à établir de meilleures méthodes pour évaluer l'efficacité de ces solutions, en fournissant des critères plus clairs pour évaluer leur performance dans des situations réelles.

Les méthodes développées dans cette étude peuvent être appliquées à d'autres variantes de problèmes de repositionnement de vélos en libre-service et servir de base pour de futures études sur l'optimisation des opérations de vélos en libre-service. Cela pourrait finalement mener à un meilleur service pour les utilisateurs et à une gestion plus efficace des réseaux de vélos en libre-service.