Modèle d'optimisation de la redistribution des vélos d'un système de vélopartage

Les systèmes de vélopartage de troisième et quatrième génération comme le système BIXI de Montréal sont de plus en plus populaires partout à travers le monde. Le nombre d'usagers grandissant et la grande variabilité de la demande entraînent plusieurs difficultés au niveau de la gestion quotidienne. Un des principaux enjeux opérationnels des systèmes de vélopartage est le problème de redistribution des vélos dans le but de balancer les stations. En effet, les systèmes de vélopartage à sens unique, c'est-à-dire sans retour du vélo à sa station de départ, présentent des débalancements importants entre les stations au cours de la journée. La redistribution est donc nécessaire pour assurer à l'usager qu'il trouvera un vélo ou un stationnement lorsqu'il en aura besoin. Cependant, cette opération est coûteuse et difficile à planifier puisqu'elle nécessite une bonne compréhension des comportements des utilisateurs et implique une modélisation mathématique complexe. La contribution de cette recherche se situe au niveau du développement d'un outil opérationnel applicable dans un contexte réel permettant d'optimiser les activités de redistribution statique et dynamique. En effet, les problèmes de redistribution statique de nuit et dynamique de jour ont été abordés dans la littérature, mais aucun auteur n'apporte une solution concrète et applicable par l'industrie. En outre, la majorité des opérateurs de systèmes de vélopartage basent présentement leur redistribution sur leur expérience acquise de l'utilisation des vélos. En premier lieu, une revue de littérature a donc été réalisée sur les différents systèmes de vélopartage et leur fonctionnement en mettant l'accent sur le système BIXI de Montréal, sur les trois principaux enjeux liés à la redistribution (le problème de design de système, le problème de redistribution statique de nuit et le problème de redistribution dynamique de jour), sur l'analyse des patrons de demande des vélos ainsi que sur les indicateurs de performance utilisés pour qualifier la redistribution dans les systèmes de vélopartage. L'outil développé dans le cadre de cette recherche s'appuie sur des modèles d'optimisation en programmation par contraintes développés à l'aide du logiciel AIMMS. La méthodologie qui a permis le développement des modèles d'optimisation a débuté par l'examen des données BIXI. Cette analyse a permis de bien comprendre les données disponibles, les besoins en termes de redistribution et la performance actuelle des systèmes. Par la suite, le logiciel AIMMS ainsi que la programmation par contraintes ont été choisis pour la modélisation. Finalement, les différents modèles pour le problème de redistribution statique et pour le problème de redistribution dynamique ont été développés de façon itérative. Le processus méthodologique a permis de développer six différents modèles qui résolvent les deux problèmes de différentes façons. Trois modèles résolvent le problème statique : le modèle statique avec objectif précis, le modèle statique avec objectif précis et demande insatisfaite ainsi que le modèle statique avec intervalle objectif et demande insatisfaite. Trois modèles résolvent le problème dynamique : le modèle dynamique avec objectif précis, le modèle dynamique avec objectif précis et demande insatisfaite ainsi que le modèle dynamique avec niveau de service. L'objectif de la recherche étant de développer un outil facilement utilisable par les opérateurs de systèmes de vélopartage, une interface utilisateur a été développée dans AIMMS. L'interface utilisateur permet à l'opérateur de facilement comprendre et analyser les résultats du modèle en plus de modifier facilement les paramètres pour pouvoir tester différents scénarios. La nuit, l'opérateur exécute le modèle une fois et les routes optimales des camions de redistribution sont calculées. Le jour, l'opérateur peut exécuter le modèle à chaque fois qu'un camion termine une opération de redistribution. Les routes des camions sont donc calculées pour les deux prochaines heures par exemple. Plus la fréquence à laquelle l'opérateur exécute le modèle est importante, plus les résultats sont précis et optimaux. Pour valider son efficacité, l'outil a été testé sur les données de la journée du 16 juin 2011 du système BIXI. Les modèles les plus intéressants sont le modèle statique avec intervalle objectif et demande insatisfaite pour le problème statique de nuit et le modèle dynamique avec objectif précis et demande insatisfaite pour le problème dynamique de jour. Une analyse sommaire a permis de conclure que les modèles généraient de bonnes solutions. En effet, le modèle dynamique avec niveau de service a, par exemple, permis de générer une solution qui diminuait de 50% le nombre de périodes de non-service par rapport à ce qui a été calculé avec les données du 16 juin 2011. Une analyse de sensibilité a aussi été faite sur certains paramètres pour démontrer leur influence sur la solution. Ainsi, il a été possible de conclure que les paramètres initiaux influençaient beaucoup le résultat obtenu. L'outil est donc efficace, flexible, il s'implante facilement et est un bon point de départ pour le développement d'un logiciel de redistribution plus complet.

Abstract

Bikesharing systems of third and fourth generation like the BIXI system in Montreal are gaining in popularity across the world. The rapidly growing number of users and the important variability of the demand lead to important challenges in the daily management of a bikesharing system. One of the most important operational challenges in the bikesharing systems is the redistribution of the bicycles in order to balance the stations. The one-way bikesharing systems (with no return of the bike at its original location) present important unbalances between stations during the day. A redistribution system becomes necessary to insure that a user will find a bicycle or a parking spot when needed. However, the redistribution is costly and hard to plan because it is based on a good understanding of the users' behavior and implies a complex mathematical modeling. The contribution of this research is to develop an operational tool that can be used in a real operating context. The tool developed needs to support the optimization of the static and dynamic redistribution of the bicycles. Researches on static (at night) and dynamic (during the day) redistribution are present in the literature but no author brings a concrete solution easily applicable in an operational context. Moreover, the majority of bikesharing system operators based their redistribution on their empirical knowledge of the bicycles' demand. Firstly, a literature review was conducted on the different bikesharing systems and the way they operate focusing on the BIXI system in Montreal, the principal redistribution challenges (system design, static redistribution and dynamic redistribution), the demand analysis and the key performance indicators used to qualify the redistribution in bikesharing systems. The tool that has been developed in this research is based on optimization models in constraint programming developed on the AIMMS platform. The development of these models started with an analysis of BIXI's data to better understand available data, need in terms of redistribution and actual performance of the system. Subsequently, AIMMS and constraint programming were chosen for the modeling. Finally, the models for static and dynamic redistribution were developed iteratively. The methodology used has led to the development of six different models addressing in different ways the static and dynamic problem. Three models addressed the static problem, the static model with precise target, the static model with precise target and unsatisfied demand, the static model with target interval and satisfy demand. Three other models addressed the dynamic problem: the dynamic model with precise target, the dynamic model with precise target and unsatisfied demand and the dynamic model with service level. The main objective of the model is to develop a tool easily usable by bikesharing systems' operators; a user interface has been developed in AIMMS. With the user interface, the operator can easily understand and analyze the output data of a model. In addition, he can also modify parameters to test different scenarios. At night, the operator runs the model one time and the optimal truck routes are calculated. During the day, the operator can run the model every time a truck completes a redistribution operation. The truck routes are then calculated for the next two hours for example. The more often the model is run, better are the results. To validate the effectiveness of the tool, it has been tested on data from the BIXI system from June 16th 2011. The most interesting models are the static model with target interval and unsatisfied demand for the static problem at night and the dynamic model with precise target and unsatisfied demand for the dynamic problem during the day. By performing a summary analysis, it was possible to conclude that the models were generating good solutions. For example, the dynamic model with service level has generated a solution decreasing the number of non-service periods by 50% in relation to the data from June 16th 2011. A sensibility analysis has also been conducted on some of the parameters to demonstrate their influence on the solution. From those analyses, it is possible to conclude that the starting point of a model influences significantly the results achieved at the end. The tool that has been developed is effective, flexible, easy to implement and it is also a good starting point for the development of a more complete redistribution software.