Scheduled service network design for integrated planning of rail freight transportation

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles.

ITEM : An Integrated Transport Economy Model - Price Elasticities of Freight Transport Demand in Canada : Three Canadian Markets and Four Commodities.

Rapport de recherche

Analyse de la performance du système portuaire de l'Arctique canadien

Les changements climatiques amènent des transformations profondes de l’environnement arctique. La diminution de l’étendue de la couverture de glace permet un accès facilité aux ressources naturelles et aux communautés nordiques. Au Canada, la région arctique est caractérisée par une géographie archipélagique et un réseau de transport rudimentaire. Le transport maritime est le mode privilégié pour l’acheminement du fret aux communautés et aux sites industriels de l’Arctique. La littérature scientifique présente des lacunes importantes au sujet de la navigation commerciale dans l’Arctique canadien. Peu d’études portent sur le trafic de ravitaillement en raison de son volume peu élevé et de la faible diversité des types de produits transportés, bien qu’il s’agisse d’une activité grandement significative pour les populations et l’économie du Nord. Cette recherche vise à combler cette lacune en dressant un portrait du transport maritime et de la performance des opérations portuaires dans l’Arctique canadien. L’étude est structurée en quatre parties. Une analyse du trafic et des échanges maritimes est d’abord réalisée sous trois échelles : internationale, nationale et intra-arctique. Ensuite, l’étude de la flotte et des routes fait ressortir la distribution géographique des transporteurs. Puis, la performance des ports est mesurée grâce à des indicateurs et un système de cotation. Finalement, une évaluation des opérations maritimes arctiques est menée par l’entremise d’informations récoltées lors d’entrevues avec les membres de l’industrie maritime, de conférences et de travail de terrain. Les sujets abordés concernent l’évolution de la desserte, les défis posés par la navigation en milieu arctique et le développement des ports du Nord canadien. Les résultats de l’étude mènent à la conclusion que le transport maritime dans l’Arctique est caractérisé par une croissance positive du volume acheminé et une implication profonde des transporteurs dédiés à la desserte nordique, mais des infrastructures portuaires et maritimes sous-développées.

Un protocole de diffusion des messages dans les réseaux véhiculaires

De nos jours, la voiture est devenue le mode de transport le plus utilisé, mais malheureusement, il est accompagné d’un certain nombre de problèmes (accidents, pollution, embouteillages, etc.), qui vont aller en s’aggravant avec l’augmentation prévue du nombre de voitures particulières, malgré les efforts très importants mis en œuvre pour tenter de les réduire ; le nombre de morts sur les routes demeure très important. Les réseaux sans fil de véhicules, appelés VANET, qui consistent de plusieurs véhicules mobiles sans infrastructure préexistante pour communiquer, font actuellement l’objet d'une attention accrue de la part des constructeurs et des chercheurs, afin d’améliorer la sécurité sur les routes ou encore les aides proposées aux conducteurs. Par exemple, ils peuvent avertir d’autres automobilistes que les routes sont glissantes ou qu’un accident vient de se produire. Dans VANET, les protocoles de diffusion (broadcast) jouent un rôle très important par rapport aux messages unicast, car ils sont conçus pour transmettre des messages de sécurité importants à tous les nœuds. Ces protocoles de diffusion ne sont pas fiables et ils souffrent de plusieurs problèmes, à savoir : (1) Tempête de diffusion (broadcast storm) ; (2) Nœud caché (hidden node) ; (3) Échec de la transmission. Ces problèmes doivent être résolus afin de fournir une diffusion fiable et rapide. L’objectif de notre recherche est de résoudre certains de ces problèmes, tout en assurant le meilleur compromis entre fiabilité, délai garanti, et débit garanti (Qualité de Service : QdS). Le travail de recherche de ce mémoire a porté sur le développement d’une nouvelle technique qui peut être utilisée pour gérer le droit d’accès aux médias (protocole de gestion des émissions), la gestion de grappe (cluster) et la communication. Ce protocole intègre l'approche de gestion centralisée des grappes stables et la transmission des données. Dans cette technique, le temps est divisé en cycles, chaque cycle est partagé entre les canaux de service et de contrôle, et divisé en deux parties. La première partie s’appuie sur TDMA (Time Division Multiple Access). La deuxième partie s’appuie sur CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) pour gérer l’accès au medium. En outre, notre protocole ajuste d’une manière adaptative le temps consommé dans la diffusion des messages de sécurité, ce qui permettra une amélioration de la capacité des canaux. Il est implanté dans la couche MAC (Medium Access Control), centralisé dans les têtes de grappes (CH, cluster-head) qui s’adaptent continuellement à la dynamique des véhicules. Ainsi, l’utilisation de ce protocole centralisé nous assure une consommation efficace d’intervalles de temps pour le nombre exact de véhicules actifs, y compris les nœuds/véhicules cachés; notre protocole assure également un délai limité pour les applications de sécurité, afin d’accéder au canal de communication, et il permet aussi de réduire le surplus (overhead) à l’aide d’une propagation dirigée de diffusion.

The relationship between product design and business models in the context of sustainability

Dans les sphères du développement durable, des modèles d’affaires et du design de produit, certains leviers rendent le croisement de ces trois sphères de plus en plus pertinent. Au croisement de ces trois sphères se trouve une opportunité de comprendre les relations existantes entre le design de produit et les modèles d’affaires afin d’aider les décideurs à développer des solutions davantage durables. L’approche méthodologique de cette recherche utilise un système complexe et est basée sur un paradigme pragmatique. En vue de répondre à la question « Dans quelle mesure des modèles d’affaires et le design de produit sont liés dans un contexte de développement durable? », cette recherche a soigneusement analysé trois cas: Better Place, une compagnie californienne ayant développé une infrastructure permettant le chargement des voitures électriques; Interface Inc., un manufacturier mondial de tuiles de tapis commerciales établi à Atlanta; et Métacycle, un concept d’entreprise développé par une équipe de chercheurs en design à Montréal. Chaque cas a été analysé en corrélant des aspects du design de produit à des éléments de leur modèle d’affaires. Les résultats montrent que dans le contexte du développement durable, le design de produit et les modèles d’affaires sont interdépendants. Les résultats peuvent être résumés en six points: il existe des relations applicables universellement; les innovations de design substantielles jouent un rôle important dans le développement durable; la « durabilité » peut être une qualité émergente d’un modèle d’affaires; les partenariats peuvent être vitaux pour l’intégration des systèmes; un modèle de services a des bénéfices et des limitations considérables; le design peut agir comme levier à l’utilisation d’énergies renouvelables. Pratiquer simultanément l’innovation du modèle d’affaires et du produit peut apporter une valeur ajoutée, susciter des opportunités et augmenter l’efficience sur plusieurs facettes. Toutefois, les risques et les coûts de tels procédés sont souvent très élevés. En aidant à comprendre et définir comment les trois sphères mentionnées plus tôt sont interdépendantes, cette recherche pourrait idéalement inspirer des recherches supplémentaires sur le sujet. L’application par des organisations de la méthodologie et des apprentissages résultant de cette recherche peut permettre à d’autres d’utiliser le croisement entre l’innovation de produit et l’innovation du modèle d’affaires afin de résoudre des enjeux sociaux et environnementaux complexes.

À travers le pare-brise : la création des territoires touristiques à l’ère de l’automobile (Québec et Ontario, 1920-1967)

Cette thèse fait la lumière sur les différentes manières dont, historiquement, a été perçu, conçu et vécu le territoire, à travers l’expérience et l’essor de la mobilité. Cette étude montre le rôle crucial de l’automobilité dans le développement touristique du Québec et de l’Ontario et les manières dont elle a façonné certains de leurs territoires. La thèse reconstitue ces processus en examinant les différentes mesures adoptées pour mettre en tourisme ces territoires et les transformer sur le plan matériel comme symbolique, entre 1920 et 1967. Elle répond à la question suivante : en quoi et comment la mobilité associée à l’automobile transforme et crée les territoires touristiques? La période étudiée s’ouvre au moment où débute l’intervention gouvernementale en matière de tourisme et s’amorce l’aménagement d’infrastructures favorisant une plus grande automobilité. Elle se clôt sur les célébrations entourant le Centenaire du Canada et la tenue de l’Expo 1967 à Montréal, qui donnent lieu à un aménagement intense du territoire afin d’accommoder un nombre sans précédent de touristes motorisés en provenance des autres provinces canadiennes et des États-Unis. La thèse reconstitue d’abord le processus de mise en tourisme des territoires par la conception, la construction et la promotion du système routier, l’élaboration d’itinéraires et de circuits touristiques et le développement d’outils accompagnant le touriste dans sa mobilité. L’embellissement en tant qu’élément structurant de la transformation des territoires est ensuite examiné. Enfin, la publicité, les récits et les pratiques touristiques sont étudiés de manière détaillée afin d’identifier les mécanismes par lesquels se construisent les représentations des territoires par l’apport de différents acteurs. Cette thèse révèle ainsi les liens étroits et complexes qui se développent à partir des années 1920 entre l’automobilité, le tourisme et la modification des territoires. Elle contribue à mettre au jour l’historicité de certains réflexes et orientations qui ont encore cours dans l’industrie touristique canadienne soit ceux d’aborder son développement en fonction de l’accessibilité du territoire à l’automobile et du regard à travers le pare-brise. En montrant le rôle du système automobile dans l’expérience touristique, l’étude ajoute un élément nouveau à la compréhension de la démocratisation des loisirs. Souvent expliquée par la hausse du niveau de vie, du temps libre et de la généralisation des congés payés, cette démocratisation se trouve aussi favorisée par l’accessibilité à l’automobile qui, à son tour, rend accessible des territoires de plus en plus éloignés à des fins de loisirs. La dimension récréative de l’automobile permet d’expliquer son adoption rapide par les Nord-Américains et les Canadiens ainsi que la dépendance qu’ils ont progressivement développée à son égard.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.