Opérateur-réseau et approche relationnelle : l'industrie du fret aérien au Canada

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Développement d’un algorithme de branch-and-price-and-cut pour le problème de conception de réseau avec coûts fixes et capacités

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides.

Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.

L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits.

Droit du transport intermodal international de marchandises : une perspective « supply chain management ».

La thèse propose d’introduire une perspective globale dans le traitement juridique du transport intermodal international qui prendrait racine dans la stratégie logistique des entreprises. La conception juridique se heurte, en effet, aux évolutions opérationnelles et organisationnelles des transports et aboutit à une incertitude juridique. Les transporteurs ont dû s’adapter aux exigences d’optimisation des flux des chargeurs dont les modes de production et de distribution reposent sur le supply chain management (SCM). Ce concept est le fruit de la mondialisation et des technologies de l’information. La concurrence induite par la mondialisation et le pilotage optimal des flux ont impulsé de nouvelles stratégies de la part des entreprises qui tentent d’avoir un avantage concurrentiel sur le marché. Ces stratégies reposent sur l’intégration interfonctionnelle et interoganisationnelle. Dans cette chaîne logistique globale (ou SCM) l’intermodal est crucial. Il lie et coordonne les réseaux de production et de distribution spatialement désagrégés des entreprises et, répond aux exigences de maîtrise de l’espace et du temps, à moindre coût. Ainsi, le transporteur doit d’une part, intégrer les opérations de transport en optimisant les déplacements et, d’autre part, s’intégrer à la chaîne logistique du client en proposant des services de valeur ajoutée pour renforcer la compétitivité de la chaîne de valeur. Il en découle une unité technique et économique de la chaîne intermodale qui est pourtant, juridiquement fragmentée. Les Conventions internationales en vigueur ont été élaborées pour chaque mode de transport en faisant fi de l’interaction entre les modes et entre les opérateurs. L’intermodal est considéré comme une juxtaposition des modes et des régimes juridiques. Ce dépeçage juridique contraste avec la gestion de la chaîne intermodale dont les composantes individuelles s’effacent au profit de l’objectif global à atteindre. L’on expose d’abord l’ampleur de l’incertitude juridique due aux difficultés de circonscrire le champ d’opérations couvert par les Conventions en vigueur. Une attention est portée aux divergences d’interprétations qui débouchent sur la « désunification » du droit du transport. On s’intéresse ensuite aux interactions entre le transport et la chaîne logistique des chargeurs. Pour cela, on retrace l’évolution des modes de production et de distribution de ces derniers. C’est effectivement de la stratégie logistique que découle la conception de la chaîne intermodale. Partant de ce système, on identifie les caractéristiques fondamentales de l’intermodal. La thèse aboutit à dissiper les confusions liées à la qualification de l’intermodal et qui sont à la base des divergences d’interprétations et de l’incertitude juridique. De plus, elle met en exergue l’unité économique du contrat de transport intermodal qui devrait guider la fixation d’un régime de responsabilité dédié à ce système intégré de transport. Enfin, elle initie une approche ignorée des débats juridiques.

A heuristic algorithm for the Capacitated Vehicle Routing Problem with Synchronized Pick-ups and Drop-offs : a case study for medications delivery and supervision in DR Congo

Dans des contextes de post-urgence tels que le vit la partie occidentale de la République Démocratique du Congo (RDC), l’un des défis cruciaux auxquels font face les hôpitaux ruraux est de maintenir un niveau de médicaments essentiels dans la pharmacie. Sans ces médicaments pour traiter les maladies graves, l’impact sur la santé de la population est significatif. Les hôpitaux encourent également des pertes financières dues à la péremption lorsque trop de médicaments sont commandés. De plus, les coûts du transport des médicaments ainsi que du superviseur sont très élevés pour les hôpitaux isolés ; les coûts du transport peuvent à eux seuls dépasser ceux des médicaments. En utilisant la province du Bandundu, RDC pour une étude de cas, notre recherche tente de déterminer la faisabilité (en termes et de la complexité du problème et des économies potentielles) d’un problème de routage synchronisé pour la livraison de médicaments et pour les visites de supervision. Nous proposons une formulation du problème de tournées de véhicules avec capacité limitée qui gère plusieurs exigences nouvelles, soit la synchronisation des activités, la préséance et deux fréquences d’activités. Nous mettons en œuvre une heuristique « cluster first, route second » avec une base de données géospatiales qui permet de résoudre le problème. Nous présentons également un outil Internet qui permet de visualiser les solutions sur des cartes. Les résultats préliminaires de notre étude suggèrent qu’une solution synchronisée pourrait offrir la possibilité aux hôpitaux ruraux d’augmenter l’accessibilité des services médicaux aux populations rurales avec une augmentation modique du coût de transport actuel.

SUPPLY CHAIN MANAGEMENT IN INDIAN PETROLEUM REFINING INDUSTRY

Model development for selection of location for refinery in India and identification of characteristics to be looked into when configuring it and to develop models for integrated supply chain planning for a refinery. Locating and removing inbound, internal and outbound logistic problems in an existing refinery and overall design of a logistic information system for a refinery are the main objectives of the study. A brief description of supply chain management (SCM), elements of SCM and their significance, logistics cost in petroleum industry and its impacts, and dynamics of petroleum its logistic practices are also to be presented. Scope of application of SCM in petroleum refinery will also be discussed. A review of the investigations carried out by earlier researches in the area of supply chain management in general and with specific reference to petroleum refining.

Packaging materials for shrimp, fish and fish products, their properties, selection and effect of different packaging materials on their shelf life

Packaging is important not only in extending the shellife of fish and fishery products but also improving their marketability. In the recent years, significant development have taken place in the packaging industry. During the past decade in India, there is almost a packaging revolution with the availability of variety packaging materials, thus generating better packaging consciousness in other producer/manufacturing industries. But unfortunately, such realisation is not forthcoming in the fisheries sector and packaging techniques for local and export trade continues to be on traditional lines with their inherent drawbacks and limitations. Better packaging ensures improved quality and presentation of the products and ensures higher returns to the producer. Among several packaging materials used in fishery industry, ISI specifications had been formulated only for corrugated fibre board boxes for export of seafoods and froglegs. This standard was formulated before containersiation came into existance in the export of marine products. Before containerisation, the standards were stringent in view of the rough handling, transportation and storage. Two of the common defects reported in the master cartons exported from India are low mechanical strength and tendency to get wet. They are weakened by the deposits of moisture caused by temperature fluctuations during loading, unloading and other handling stages. It is necessary to rectify the above defects in packaging aquatic products and hence in the present study extensive investigations are carried out to find out the reasons for the damage of master cartons, to evolve code of practice for the packaging oi frozen shrimp for exports, development of alternative style of packaging for the shipping container, development of suitable consumer packaging materials for fish soup powder, cured dried mackeral, fish pickles in oil and frozen shrimp. For the development of suitable packaging materials, it is absolutely essential to know the properties of packaging materials, effect of different packaging materials on theirshelf life and their suitability for food contact applications.

Polypropylene/metal oxide nanocomposites: fiber spinning and evaluation”

PP has been getting much attention over the years because it is a very durable polymer commonly used in aggressive environments including automotive battery casings, fuel containers etc. They are used to make bottles, fibers for clothing, components in cars etc. However, it has some shortcomings such as low dimensional and thermal stability. Materials such as metal oxides with sizes of the order 1–50 nm have received a great deal of attention because of their versatile applications in polymer/ inorganic nanocomposites, optoelectronic devices, biomedical materials, and other areas. They are stable under harsh process conditions and also regarded as safe materials to human beings and animals. In the present investigation, PP is modified by incorporating metal oxide nanoparticles such as ZnO and TiO2 by simple melt mixing method. Melt spinning method was used to prepare PP/metal oxide nanocomposite fibers. Various studies have been carried out on these composites and fibers. In the first part of the study, ZnO nanoparticles were prepared from ZnCl2 and NaOH in presence of chitosan, PVA, ethanol and starch. This is a simple and inexpensive method compared to other methods. Change in morphology and particle size of ZnO were studied. Least particle size was obtained in chitosan medium. The particles were characterized by using XRD, SEM, TEM, TGA and EDAX. Antibacterial properties of ZnO prepared in chitosan medium (NZO) and commercial zinc oxide (CZO) were evaluated using a gram positive and a gram negative bacteria

‘Studies on some topics in product graphs’

For routing problems in interconnection networks it is important to find the shortest containers between any two vertices, since the w-wide diameter gives the maximum communication delay when there are up to w−1 faulty nodes in a network modeled by a graph. The concept of ‘wide diameter’ was introduced by Hsu [41] to unify the concepts of diameter and The concept of ‘domination’ has attracted interest due to its wide applications in many real world situations [38]. A connected dominating set serves as a virtual backbone of a network and it is a set of vertices that helps in routing. In this thesis, we make an earnest attempt to study some of these notions in graph products. This include, the diameter variability, the diameter vulnerability, the component factors and the domination criticality.connectivity

Planning And Operation Problems Of Indian Major Ports With Special Emphasis On Cochin Port

Rapid changes in the technological environment of marine logistics and the increasing integration of waterborne, air and land transport systems have fostered a revolution in the design and operations of transport vehicles, cargo handling technology, and terminal facilities. This in turn has caused major changes in the functions of and uses of ports. From literature, it was found that these changes were very slow in case of Indian ports and the performances of port operations were poor when compared with similar ports in the same region. It was also found that a very few studies were conducted to identify the reasons for slow improvements in the performances of Indian major ports. In this thesis, an attempt is made to find out the operational problems of Indian major ports and to analyze the reasons for it. Some solutions have also been found out using management tools