Nous présentons dans cette thèse, un outil d'aide à la décision pour la régulation du trafic ferroviaire dans une usine sidérurgique. La particularité de ce système est qu'il repose sur une utilisation en temps réel, et qu'il est soumis à des contraintes spécifiques liées au processus de fabrication de l'acier. Nous décrivons ses spécificités et son rapprochement avec le problème de tournées de véhicules avec fenêtres de temps. La méthode de résolution que nous avons mise en oeuvre repose sur la coopération d'une heuristique de construction parallèle des tournées avec une heuristique d'amélioration des tournées. Les applications aux cas réels que nous avons menées montrent une amélioration de la satisfaction client en terme de nombre de retards et de durée totale des retards. La mise en oeuvre dans un site industriel est également présentée dans ce mémoire.

Dans le problème de tournées avec gestion de stock ou "Inventory Routing Problem" (IRP), le fournisseur a pour mission de surveiller les niveaux de stock d'un ensemble de clients et gérer leur approvisionnement en prenant simultanément en compte les coûts de transport et de stockage. Etant données les nouvelles exigences de développement durable et de transport écologique, nous étudions l'IRP sous une perspective énergétique, peu de travaux s'étant intéressés à cet aspect. Plus précisément, la thèse identifie les facteurs principaux influençant la consommation d'énergie et évalue les gains potentiels qu'une meilleure planification des approvisionnements permet de réaliser. Un problème relatif à l'approvisionnement en composants de chaînes d'assemblage d'automobiles est tout d'abord considéré pour lequel la masse transportée, la dynamique du véhicule et la distance parcourue sont identifiés comme les principaux facteurs impactant la consommation énergétique. Ce résultat est étendu à l'IRP classique et les gains potentiels en termes d'énergie sont analysés. Un problème industriel de tournées avec gestion de stock est ensuite étudié et résolu, notamment à l'aide d'une méthode de génération de colonnes. Ce problème met en évidence les limitations du modèle IRP classique, ce qui nous a amené à définir un modèle d'IRP plus réaliste. Finalement, une méthode de décomposition basée sur la relaxation lagrangienne est développée pour la résolution de ce problème dans le but de minimiser la consommation énergétique / The thesis studies the Inventory Routing Problem (IRP) with explicit energy consideration. Under the Vendor Managed Inventory (VMI) model, the IRP is an integration of the inventory management and routing, where both inventory storage and transportation costs are taken into account. Under the new sustainability paradigm, green transport and logistics has become an emerging area of study, but few research focus on the ecological aspect of the classical IRP. Since the classical IRP concentrates solely on the economic benefits, it is worth studying under the energy perspective. The thesis gives an estimation of the energetic gain that a better supplying plan can provide. More specifically, this thesis integrates the energy consumption into the decision of the inventory replenishment and routing. It starts with a part supplying problem in car assembly lines, where the transported mass, the vehicle dynamics and the travelled distance are identified as main energy influencing factors. This result is extended to the classical IRP with energy objective to show the potential energy reduction that can be achieved. Then, an industrial challenge of IRP is presented and solved using a column generation approach. This problem put the limitations of the classical IRP model in evidence, which brings us to define a more realistic IRP model on a multigraph. Finally, a Lagrangian relaxation method is presented for solving this new model with the aim of energy minimization.

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. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

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. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Les entreprises de transport et de distribution sont confrontées à des difficultés d'exploitation liées à la taille et à la complexité de leur processus de livraison. Dans cette problématique, nous proposons une approche globale du Problème Général de Livraison (PGL).Au niveau méthodologique, c'est une approche hiérarchique (stratégique, tactique, opérationnelle) et structurée. Il s'agit de concevoir et d'exploiter un PGL en le décomposant en problèmes de livraisons élémentaires identifiés et le plus possible indépendants les uns des autres (problèmes de transport, de hubs, d'agences, de tournées...).Au niveau algorithmique, des modèles et algorithmes de résolution ont été proposés pour résoudre ces problèmes élémentaires de livraison dans la phase opérationnelle en tenant compte, en particulier, du nombre et de la capacité limités des moyens de transport.Au niveau applicatif, deux exemples réels sont traités : le système de livraison d'une entreprise de Vente à Distance et le système de livraison des casernes de pompiers du Nord de la France à partir de la pharmacie centrale de Lille

Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.

Dans cette thèse, nous proposons d'aborder l'ordonnancement des transports par une approche interdisciplinaire. L'idée est d'intégrer les facteurs humains dans le système d'aide à la décision réalisé, de façon à ce que l'homme puisse agir sur la modélisation et la résolution du problème. Le système proposé doit offrir de la flexibilité, afin d'être capable de s'adapter aux nouvelles situations et aux changements, même si ceux-ci n'ont pas été prévus initialement par le concepteur du système. Pour atteindre l'objectif fixé, nous nous sommes notamment appuyé sur une analyse du domaine de travail (" Work Domain Analysis ") basée sur une hiérarchie d'abstraction des entités (physiques ou plus abstraites) manipulées dans ce type de problèmes. Nous avons proposé une architecture pour le système d'aide à la décision basée sur cette analyse du domaine et la programmation par contraintes. Nous avons également conçu, et intégré dans le système, des algorithmes dédiés et des méthodes de résolution basés sur le principe d'inversion de modèle. Enfin, nous avons proposé une architecture d'interfaces avec l'objectif d'assister efficacement l'opérateur humain dans la réalisation des différentes sous-tâches nécessaires à la résolution globale du problème. L'étude du sujet interdisciplinaire a été précédée d'une analyse focalisée sur la résolution de problèmes théoriques d'ordonnancement à machines parallèles avec contraintes de précédence et temps de préparation des machines entre opérations, utilisant des méthodes de recherche arborescente basée sur les divergences.

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

La performance logistique des entreprises et l’optimisation des transports sont devenues un grand problème ces dernières années. La planification et l’optimisation des services constituent en particulier un nouveau défi. Afin d’accroître la productivité et de réduire les coûts de la logistique, ce travail de recherche contribue à l’optimisation d’un problème de tournées de service à domicile multi-dépôt, multi-période avec fenêtres de temps de vie réelle. Le problème vient d’un contexte réaliste et est formulé comme un modèle en Mixed Integer Programming (MIP). Les résultats avec Cplex montrent que ce problème ne peut être résolu par des méthodes exactes dans un délai raisonnable pour une utilisation pratique. Par conséquent, nous introduisons des heuristiques. Premièrement, les heuristiques de recherche locales sont utilisées pour résoudre le problème. Les solutions réalisables initiales sont générées par une heuristique de construction et plusieurs heuristiques de recherche locales sont appliquées pour obtenir des solutions dans un temps de calcul assez court. Ensuite, nous proposons un algorithme génétique avec une nouvelle représentation du chromosome et de nouveaux opérateurs génétiques pour le problème abordé. Enfin, nous considérons un algorithme génétique avec contrôle de la diversité pour problèmes à grande échelle. Les solutions infaisables sont prises en compte dans la population et la contribution à la diversité fait partie de l’évaluation afin d’éviter une recherche prématurée. Ces méthodes ont été mises en œuvre avec succès pour optimiser le problème de routage. / The logistics performance of enterprises and the optimization of transportation have become a great issue in recent years. Field force planning and optimization is a new challenge for the service sector. In order to increase productivity and reduce cost of logistics, this research contributes to the optimization of a real-life multi-depot multi-period field service routing problem with time window. The problem is abstracted from the realistic problem and formulated as a Mixed Integer Programming (MIP) model. Computational results with Cplex show that this problem cannot be solved by exact methods in reasonable time for practical use. First, local search heuristics are used for solving the problem. Initial feasible solutions are generated by a constructive heuristic and several local search heuristics are applied to obtain solutions in a very short computing time. Then we propose a genetic algorithm with new representation of chromosome and new genetic operators for the addressed problem. Finally we consider a genetic algorithm with diversity control to deal with large scale problems. Infeasible solutions are taken account in the population and the diversity contribution is part of the evaluation to avoid premature of search. These methods have been successfully implemented to the optimization of the routing problem

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. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.