Show item record

dc.contributor.advisorFrejinger, Emma
dc.contributor.advisorCordeau, Jean-François
dc.contributor.authorPham, Hoang Giang
dc.date.accessioned2021-01-22T14:47:59Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2021-01-22T14:47:59Z
dc.date.issued2020-12-16
dc.date.submitted2020-10
dc.identifier.urihttp://hdl.handle.net/1866/24331
dc.subjectProblème du Routage des Locomotivesfr
dc.subjectApproche par Horizon Roulantfr
dc.subjectLocomotive Routing Problemfr
dc.subjectRolling Horizon Approachfr
dc.subject.otherApplied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)fr
dc.titleA rolling horizon approach for the locomotive routing problem at the Canadian National Railway Companyfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractCette thèse étudie le problème du routage des locomotives qui se pose à la Compagnie des chemins de fer nationaux du Canada (CN) - le plus grand chemin de fer au Canada en termes de revenus et de taille physique de son réseau ferroviaire. Le problème vise à déterminer la séquence des activités de chaque locomotive sur un horizon de planification donné. Dans ce contexte, il faut prendre des décisions liées à l'affectation de locomotives aux trains planifiés en tenant compte des besoins d'entretien des locomotives. D’autres décisions traitant l'envoi de locomotives aux gares par mouvements à vide, les déplacements légers (sans tirer des wagons) et la location de locomotives tierces doivent également être prises en compte. Sur la base d'une formulation de programmation en nombres entiers et d'un réseau espace-temps présentés dans la littérature, nous introduisons une approche par horizon roulant pour trouver des solutions sous-optimales de ce problème dans un temps de calcul acceptable. Une formulation mathématique et un réseau espace-temps issus de la littérature sont adaptés à notre problème. Nous introduisons un nouveau type d'arcs pour le réseau et de nouvelles contraintes pour le modèle pour faire face aux problèmes qui se posent lors de la division de l'horizon de planification en plus petits morceaux. Les expériences numériques sur des instances réelles montrent les avantages et les inconvénients de notre algorithme par rapport à une approche exacte.fr
dcterms.abstractThis thesis addresses the locomotive routing problem arising at the Canadian National Railway Company (CN) - the largest railway in Canada in terms of both revenue and the physical size of its rail network. The problem aims to determine the sequence of activities for each locomotive over the planning horizon. Besides assigning locomotives to scheduled trains and considering scheduled locomotive maintenance requirements, the problem also includes other decisions, such as sending locomotives to stations by deadheading, light traveling, and leasing of third-party locomotives. Based on an Integer Programming formulation and a Time-Expanded Network presented in the literature, we introduce a Rolling Horizon Approach (RHA) as a method to find near-optimal solutions of this problem in acceptable computing time. We adapt a mathematical formulation and a space-time network from the literature. We introduce a new type of arcs for the network and new constraints for the model to cope with issues arising when dividing the planning horizon into smaller ones. Computational experiments on real-life instances show the pros and cons of our algorithm when compared to an exact solution approach.fr
dcterms.languageengfr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record


DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace