Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

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

Titre: Title: Modèle d'optimisation de la redistribution des vélos d'un système de vélopartage Auteur: Author: Andréanne Leduc Date: 2013 Type: Mémoire ou thèse / Dissertation or Thesis Référence: Citation: Leduc, A. (2013). Modèle d'optimisation de la redistribution des vélos d'un système de vélopartage [Mémoire de maîtrise, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/1178/ Document en libre accès dans PolyPublie Open Access document in PolyPublie URL de PolyPublie: PolyPublie URL: https://publications.polymtl.ca/1178/ Directeurs de recherche: Advisors: Louis-Martin Rousseau, & Martin T répanier Programme: Program: Génie industriel Ce fichier a été téléchargé à partir de PolyPublie, le dépôt institutionnel de Polytechnique Montréal This file has been downloaded from PolyPublie, the institutional repository of Polytechnique Montréal https://publications.polymtl.ca UNIVERSITÉ DE MONTRÉAL MODÈLE D’OPTIMISATION DE LA REDISTRIBUTION DES VÉLOS D’UN SYSTÈME DE VÉLOPARTAGE ANDRÉANNE LEDUC DÉPARTEMENT DE MATHÉMATIQUES ET DE GÉNIE INDUSTRIEL ÉCOLE POLYTECHNIQUE DE MONTRÉAL MÉMOIRE PRÉSENTÉ EN VUE DE L’OBTENTION DU DIPLÔME DE MAÎTRISE ÈS SCIENCES APPLIQUÉES (GÉNIE INDUSTRIEL) AOÛT 2013 © Andréanne Leduc, 2013. UNIVERSITÉ DE MONTRÉAL ÉCOLE POLYTECHNIQUE DE MONTRÉAL Ce mémoire intitulé: MODÈLE D’OPTIMISATION DE LA REDISTRIBUTION DES VÉLOS D’UN SYSTÈME DE VÉLOPARTAGE présenté par : LEDUC Andréanne en vue de l’obtention du diplôme de : Maîtrise ès sciences appliquées a été dûment accepté par le jury d’examen constitué de : Mme MORENCY Catherine, Ph.D., présidente M. ROUSSEAU Louis-Martin, Ph.D., membre et directeur de recherche M. TRÉPANIER Martin, ing., Ph.D., membre et codirecteur M. CONTARDO Claudio, Ph.D., membre iii REMERCIEMENTS J’aimerais remercier grandement mon directeur de recherche le professeur Louis-Martin Rousseau du département de mathématiques et de génie industriel pour m’avoir guidé et soutenu et pour m’avoir aidé à résoudre les innombrables problèmes dans les modèles. Je tiens aussi à remercier mon co-directeur de recherche le professeur Martin Trépanier aussi du département de mathématiques et de génie industriel pour son support, sa rigueur et sa motivation. Mes remerciements vont également à Bixi pour les données qu’ils m’ont offertes ainsi qu’à la professeure Catherine Morency du département des génies civil, géologique et des mines et à Hubert Verreault pour leurs commentaires pertinents et leur aide dans l’obtention des données. Pour leur appui financier, je tiens à remercier le conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), les fonds de recherche du Québec – Nature et technologies (FQRNT) ainsi que le centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (CIRRELT). Finalement, j’aimerais remercier l’ensemble du département de génie industriel de l’École Polytechnique de Montréal. iv RÉSUMÉ 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 v 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. vi 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 uploads/Science et Technologie/ ba-lacing.pdf