Le problème de tournées de véhicules est un des problèmes d’optimisation combinatoire les plus connus et les plus difficiles. Il s’agit de déterminer les tournées optimales pour une flotte de véhicules afin de servir un ensemble donné de clients. Dans les problèmes classiques de transport, chaque client est normalement servi à partir d’un seul nœud (ou arc). Pour cela, on définit toujours un ensemble donné de nœuds (ou arcs) obligatoires à visiter ou traverser, et on recherche la solution à partir de cet ensemble de nœuds (ou arcs). Mais dans plusieurs applications réelles où un client peut être servi à partir de plus d’un nœud, (ou arc), les problèmes généralisés qui en résultent sont plus complexes. Le but principal de cette thèse est d’étudier trois problèmes généralisés de tournées de véhicules. Le premier problème de la tournée sur arcs suffisamment proche (CEARP), comporte une application réelle intéressante en routage pour le relevé des compteurs à distance ; les deux autres problèmes, problème de tournées couvrantes multi-véhicules (mCTP) et problème généralisé de tournées sur nœuds (GVRP), permettent de modéliser des problèmes de conception des réseaux de transport à deux niveaux. Pour résoudre ces problèmes, nous proposons une approche exacte ainsi que des métaheuristiques. Pour développer la méthode exacte, nous formulons chaque problème comme un programme mathématique, puis nous construisons des algorithmes de type branchement et coupes. Les métaheuristiques sont basées sur le ELS (ou Evolutionary Local Search) et sur le GRASP (ou Greedy Randomized Adaptive Search Procedure). De nombreuses expérimentations montrent la performance de nos méthodes. / The Routing Problem is one of the most popular and challenging combinatorial optimization problems. It involves finding the optimal set of routes for fleet of vehicles in order to serve a given set of customers. In the classic transportation problems, each customer is normally served by only one node (or arc). Therefore, there is always a given set of required nodes (or arcs) that have to be visited or traversed, and we just need to find the solution from this set of nodes (or arcs). But in many real applications where a customer can be served by from more than one node (or arc), the generalized resulting problems are more complex. The primary goal of this thesis is to study three generalized routing problems. The first one, the Close-Enough Arc Routing Problem(CEARP), has an interesting real-life application to routing for meter reading while the others two, the multi-vehicle Covering Tour Problem (mCTP) and the Generalized Vehicle Routing Problem(GVRP), can model problems concerned with the design of bilevel transportation networks. The problems are solved by exact methods as well as metaheuristics. To develop exact methods, we formulate each problem as a mathematical program, and then develop branch-and-cut algorithms. The metaheuristics are based on the evolutionary local search (ELS) method et on the greedy randomized adaptive search procedure (GRASP) method. The extensive computational experiments show the performance of our methods.

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-01-31T14:48:27Z No. of bitstreams: 1 Roberto da Silva Araujo_.pdf: 903723 bytes, checksum: ae702a685139c36126c0bfef5f707282 (MD5) / Made available in DSpace on 2018-01-31T14:48:27Z (GMT). No. of bitstreams: 1 Roberto da Silva Araujo_.pdf: 903723 bytes, checksum: ae702a685139c36126c0bfef5f707282 (MD5) Previous issue date: 2017-10-31 / Nenhuma / Neste trabalho é apresentado um Algoritmo Híbrido (AH) aplicado ao Problema de Roteamento de Veículos com Múltiplos Depósitos e Frota Heterogênea (PRVMDFH). Um conjunto de clientes é atendido por um número fixo de veículos de diferentes tamanhos, por múltiplos depósitos, sujeito a restrições da capacidade do veículo. As meta-heurísticas utilizadas na construção do AH são o Algoritmo Genético (AG) e a Busca Tabu (BT). O AG usa operadores de cruzamento Mapeado Parcialmente (PMX), Cromossomo de Duas Partes (TCX) e de Ordem (OX), o operador de mutação Troca e o Algoritmo de Busca Local (ABL). A BT usa os métodos de Troca, Retirada e Inserção e Deslocamento. São analisadas as políticas de diversificação no ABL e a intensificação com as estratégias de geração de vizinhança na BT. São utilizados conjuntos de dados padrões de problemas testes, para executar os algoritmos propostos. Os resultados obtidos, comparados a outros autores, apresentaram boas soluções para diferentes tamanhos de problemas testes. / This paper presents a Hybrid Algorithm (AH) applied to the Problem of Vehicle Routing with Multiple-Deposit and Heterogeneous Fleet (MDFHPRV). A number of customers are served with a fixed number of vehicles of different sizes by multi-depot, subject to capacity constraints of the vehicle. The meta-heuristics used in AH construction are Genetic Algorithm (GA) and Tabu Search (BT). The AG uses Partial Mapped Crossover (PMX), Two Part Chromosome Crossover (TCX) and Order Crossover (OX) operators, the Exchange mutation operator, and the Local Search Algorithm (ABL). BT uses the Exchange, Retrieve, and Insertion and Displacement methods. Diversification policies was analyzed in the ABL and the intensification with the neighborhood generation strategies in BT. Standard sets of test problems are used to execute the proposed algorithms. The obtained results, compared to other authors, presented good solutions for different sizes of test problems.

Le problème de tournées de véhicules avec contrainte de capacité est un problème important en optimisation combinatoire. L'objectif du problème est de déterminer l'ensemble des routes, nécessaire pour servir les demandes déterministes des clients ayant un cout minimal, tout en respectant la capacité limite des véhicules. Cependant, dans de nombreuses applications réelles, nous sommes confrontés à des incertitudes sur les demandes des clients. La plupart des travaux qui ont traité ce problème ont supposé que les demandes des clients étaient des variables aléatoires. Nous nous proposons dans cette thèse de représenter l'incertitude sur les demandes des clients dans le cadre de la théorie de l'évidence - un formalisme alternatif pour modéliser les incertitudes. Pour résoudre le problème d'optimisation qui résulte, nous généralisons les approches de modélisation classiques en programmation stochastique. Précisément, nous proposons deux modèles pour ce problème. Le premier modèle, est une extension de l'approche chance-constrained programming, qui impose des bornes minimales pour la croyance et la plausibilité que la somme des demandes sur chaque route respecte la capacité des véhicules. Le deuxième modèle étend l'approche stochastic programming with recourse: l'incertitude sur les recours (actions correctives) possibles sur chaque route est représentée par une fonction de croyance et le coût d'une route est alors son coût classique (sans recours) additionné du pire coût espéré des recours. Certaines propriétés de ces deux modèles sont étudiées. Un algorithme de recuit simulé est adapté pour résoudre les deux modèles et est testé expérimentalement. / The capacitated vehicle routing problem is an important combinatorial optimisation problem. Its objective is to find a set of routes of minimum cost, such that a fleet of vehicles initially located at a depot service the deterministic demands of a set of customers, while respecting capacity limits of the vehicles. Still, in many real-life applications, we are faced with uncertainty on customer demands. Most of the research papers that handled this situation, assumed that customer demands are random variables. In this thesis, we propose to represent uncertainty on customer demands using evidence theory - an alternative uncertainty theory. To tackle the resulting optimisation problem, we extend classical stochastic programming modelling approaches. Specifically, we propose two models for this problem. The first model is an extension of the chance-constrained programming approach, which imposes certain minimum bounds on the belief and plausibility that the sum of the demands on each route respects the vehicle capacity. The second model extends the stochastic programming with recourse approach: it represents by a belief function for each route the uncertainty on its recourses (corrective actions) and defines the cost of a route as its classical cost (without recourse) plus the worst expected cost of its recourses. Some properties of these two models are studied. A simulated annealing algorithm is adapted to solve both models and is experimentally tested.

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances. / In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.

Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers). Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème. Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison. Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers. / In this thesis, we study mixed vehicle routing and loading problems where a constraint is imposed on delivery sequences. More precisely, the items in the loading area of a vehicle must be directly accessible, without moving any other item, at delivery time. These problems are often found in the transportation of large objects (furniture, appliances). The first paper proposes a branch-and-cut algorithm for a variant of the single vehicle pickup and delivery problem, where the loading area of the vehicle is divided into several stacks. When an item is picked up, it must be placed on the top of one of these stacks. Conversely, an item must be on the top of one of these stacks to be delivered. This requirement is called “Last In First Out” or LIFO constraint. The second paper presents another branch-and-cut algorithm for a vehicle routing and loading problem with two-dimensional rectangular items. The loading area of the vehicles is also a rectangular area where the items are taken out from one side. A constraint states that the items of a given customer must be directly accessible at delivery time. The last paper considers a stochastic vehicle routing and loading problem with two- dimensional rectangular items where the dimensions of some items are unknown when the routes are planned. However, it is possible to associate a discrete probability distribution on the dimensions of these items. The problem is solved with the Integer L-Shaped method.

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 (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques. Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire. Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques. Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée. L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire. / The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require. This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review. A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed. New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks. To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance. This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems. / Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Made available in DSpace on 2014-12-17T15:48:00Z (GMT). No. of bitstreams: 1 GustavoAS_DISSERT.pdf: 3060399 bytes, checksum: 659289bc757f2443a1b6902094747b13 (MD5) Previous issue date: 2012-02-27 / This work approaches the Scheduling Workover Rigs Problem (SWRP) to maintain the wells of an oil field, although difficult to resolve, is extremely important economical, technical and environmental. A mathematical formulation of this problem is presented, where an algorithmic approach was developed. The problem can be considered to find the best scheduling service to the wells by the workover rigs, taking into account the minimization of the composition related to the costs of the workover rigs and the total loss of oil suffered by the wells. This problem is similar to the Vehicle Routing Problem (VRP), which is classified as belonging to the NP-hard class. The goal of this research is to develop an algorithmic approach to solve the SWRP, using the fundamentals of metaheuristics like Memetic Algorithm and GRASP. Instances are generated for the tests to analyze the computational performance of the approaches mentioned above, using data that are close to reality. Thereafter, is performed a comparison of performance and quality of the results obtained by each one of techniques used / O trabalho em quest?o aborda o Problema da Programa??o das Sondas de Produ??o (PPSP) para atender os po?os de um campo de petr?leo. Embora de dif?cil resolu??o, ele ? de extrema import?ncia econ?mica, t?cnica e ambiental. Uma formula??o matem?tica deste problema ? apresentada, assim como desenvolvida uma abordagem algor?tmica. O problema abordado pode ser considerado como o de encontrar o melhor escalonamento de atendimento aos po?os pelas sondas, levando em considera??o a minimiza??o da composi??o dos custos relativos ?s sondas e da perda total da produ??o de petr?leo associada aos po?os que est?o aguardando por atendimento. Tal problema assemelha-se ao Problema de Roteamento de Ve?culos (PRV), que ? classificado como pertencente ? classe de problemas NP-Dif?cil. O objetivo da presente pesquisa ? desenvolver uma abordagem algor?tmica para resolver o PPSP, utilizando os fundamentos de metaheur?sticas como o Algoritmo Mem?tico e o GRASP. Inst?ncias s?o geradas para a realiza??o dos testes computacionais para an?lise do desempenho das abordagens acima citadas, utilizando dados que se aproximam da realidade. A partir da?, ? realizada uma compara??o de desempenho e qualidade dos resultados obtidos por cada uma das t?cnicas utilizadas

Le domaine de la logistique implique souvent la résolution de problèmes combinatoires complexes. Ces derniers font également implicitement référence à des processus, acteurs, activités et méthodes concernant divers aspects qu'il faut considérer. Ainsi, un même problème peut faire intervenir des processus de vente/achat, transport/livraison et gestion de stock. Ces processus sont tellement divers et interconnectés qu'il est difficile pour un logisticien de tous les maîtriser. Dans cette thèse, nous proposons l'explicitation, par le biais d'ontologies, de connaissances conceptuelles et sémantiques concernant les processus logistiques. Ces connaissances explicites sont alors mises à contribution pour construire un système à base de connaissances permettant de guider les logisticiens dans la construction, de façon incrémentale et semi-automatique, de solutions informatiques à un problème qui leur est posé à un moment donné. Nous mettons en oeuvre une ontologie concernant le domaine de la logistique connectée à une ontologie associée à la problématique de l'optimisation. Nous établissons ainsi un lien sémantique explicite entre le domaine de la logistique et celui de l'optimisation. Cela permet aux logisticiens d'identifier de façon précise et sans ambigüité le problème logistique auquel il est confronté et les problèmes d'optimisation associés. L'identification des problèmes conduit alors à un processus de choix des solutions allant du choix du processus logistique précis à mettre en oeuvre à celui de la méthode de résolution du problème combinatoire et cela jusqu'à la découverte du composant informatique à invoquer et qui est matérialisé par un service web. L'approche que nous avons adoptée et mise en oeuvre a été expérimentée avec les problèmes de routage de véhicules, le problème de transport ferroviaire de passagers et le problème de terminaux de conteneurs. / Logistics problems are often complex combinatorial problems. These may also implicitly refer to the processes, actors, activities, and methods concerning various aspects that need to be considered. Thus the same process may involve the processes of sale/purchase, transport/delivery, and stock management. These processes are so diverse and interconnected that it is difficult for a logistic expert to compete all of them. In this thesis, we propose the explications with the help of ontologies of conceptual ans semantic knowledge concerning the logistic processes. This explicit knowledge is then used to develop a reasoning system to guide the logistic expert for an incremental and semi-automatic construction of a software solution to an instantly posed problem. We define an ontology concerning the inter-connected logistics and associated optimization problem. We, henceforth, establish an explicit semantic link between the domains of logistics and the optimization. It may allow the logistic expert to identify precisely and unambiguously the confronted logistic problem and the associated optimization problem. The identification of the problems then leads to a process to choose the solutions ranging from the choice of the precise logistic process to be implemented to that of the method to solve the combinatorial problem until the discovery of the software component to be invoked and which is implemented by a web service. The approach we have adopted and implemented has been experimented with the "Vehicle Routing Problems", the "Passenger Train Problem" and the "Container Terminal problems".