Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

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

Les travaux présentés dans cette thèse ont porté sur l'étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l'analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l'impact de l'intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l'approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d'optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l'hypermarché pris deux à deux

Cette thèse s'intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d'ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l'avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l'analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d'abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n'est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d'un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail.

Cette thèse s’intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d’ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l’avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l’analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d’abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n’est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d’un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail. / In this thesis, we study the Cyclic Hoist Scheduling Problem (CHSP) in automated electroplating lines, when a mass production must be achieved. The CHSP is characterized by specific constraints related to processing and transport resources. To solve it in a multi-parts context, we first elaborate a 2-degree cyclic model and an associated branch and bound algorithm. Then we extend it to more complex configurations. Then, we develop a dedicated heuristic to find a feasible repetitive sequence of hoist moves that minimizes the cycle time, without a priori fixing the cycle degree. Comparisons with existing algorithms are presented to show the efficiency of the proposed heuristic. To reduce the cycle time, we integrate in the general heuristic an algorithm with a set of Minimum Part Set (MPS) configurations’. This one allows us to find the best order in which jobs should be introduced into the line. Finally, we describe a genetic algorithm approach to find a schedule which can reach the optimal 2-cycle. We finally discuss the interest of those various models, based on the promising results obtained and we provide some perspectives which could be explored.

Les ateliers de traitement de surface automatisés, qui utilisent des robots de manutention commandés par ordinateur pour le transport de la pièce, ont été largement mis en place dans différents types d'entreprises industrielles, en raison de ses nombreux avantages par rapport à un mode de production manuel, tels que : une plus grande productivité, une meilleure qualité des produits, et l’impact sur les rythmes de travail. Notre recherche porte sur trois types de problèmes d'ordonnancement associés à ces systèmes, appelés Hoist Scheduling Problems, caractérisés par des contraintes de fenêtres de temps de traitement: (I) un problème à une seule ressource de transport où l’objectif est de minimiser le temps de cycle; (II) un problème bi-objectif avec une seule ressource de transport où il faut minimiser le temps de cycle et la consommation de ressources de traitement (et par conséquent le coût de production); et (III) un problème d'ordonnancement cyclique mono-objectif mais multi-robots.En raison de la NP-complétude des problèmes étudiés et de nombreux avantages de les outils de type quantum-inspired evolutionary algorithm (QEA), nous proposons d'abord un QEA hybride comprenant un mécanisme de décodage amélioré et une procédure réparation dédiée pour trouver le meilleur temps de cycle pour le premier problème. Après cela, afin d'améliorer à la fois la performance économique et environnementale qui constituent deux des trois piliers de la stratégie de développement durable de nos jours déployée dans de nombreuses industries, nous formulons un modèle mathématique bi-objectif pour le deuxième problème en utilisant la méthode de l'intervalle interdit. Ensuite, nous proposons un QEA bi-objectif couplé avec une procédure de recherche locale pour minimiser simultanément le temps de cycle et les coûts de production, en générant un ensemble de solutions Pareto-optimales pour ce problème. Quant au troisième problème, nous constatons que la plupart des approches utilisées dans les recherches actuelles, telles que la programmation entière mixte (MIP), peuvent conduire à l’obtention d’une solution non optimale en raison de la prise en compte courante d’une hypothèse limitant l’exploration de l’espace de recherche et relative aux mouvements en charge des robots. Par conséquent, nous proposons une approche de MIP améliorée qui peut garantir l'optimalité des solutions obtenues pour ce problème, en relaxant l'hypothèse mentionnée ci-dessus.Pour chaque problème, une étude expérimentale a été menée sur des cas industriels ainsi que sur des instances générées aléatoirement. Les résultats obtenus montrent que l’efficacité des algorithmes d'ordonnancement proposés, ce qui justifie les choix que nous avons faits. / Automated treatment surface facilities, which employ computer-controlled hoists for part transportation, have been extensively established in various kinds of industrial companies, because of its numerous advantages over manual system, such as higher productivity, better product quality, and reduced labor intensity. Our research investigates three typical hoist scheduling problems with processing time windows in treatment surface facilities, which are: (I) cyclic single-hoist scheduling problem to minimize the cycle time; (II) cyclic single-hoist scheduling problem to minimize the cycle time and processing resource consumption (and consequently production cost); and (III) cyclic multi-hoist scheduling problem to minimize the cycle time.Due to the NP-completeness of the studied problems and numerous advantages of quantum-inspired evolutionary algorithm (QEA), we first propose a hybrid QEA with improved decoding mechanism and repairing procedure to find the best cycle time for the first problem. After that, to enhance with both the economic and environmental performance, which constitute two of the three pillars of the sustainable strategy nowadays deployed in many industries, we formulate a bi-objective mathematical model for the second problem by using the method of prohibited interval. Then we propose a bi-objective QEA with local search procedure to simultaneously minimize the cycle time and production cost, and we find a set of Pareto-optimal solutions for this problem. As for the third problem, we find that most existing approaches, such as mixed integer programming (MIP) approach, may identify a non-optimal solution to be an optimal one due to an assumption related to the loaded hoist moves which is made in many existing researches. Consequently, we propose an improved MIP approach for this problem by relaxing the above-mentioned assumption. Our approach can guarantee the optimality of its obtained solutions.For each problem, experimental study on industrial instances and random instances has been conducted. Computational results demonstrate that the proposed scheduling algorithms are effective and justify the choices we made.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. 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. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. / We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.