In this Dissertation, the Vehicle Routing Problem with Drones (VRPD), motivated by the growing interest on Unmanned Aerial Vehicles (UAVs, or Drones) by the industry and their applications in logistics is studied. A pioneer work by (MURRAY; CHU, 2015) shows a combination between UAV and a truck to deliver products, presenting an adaptation to the Traveling Salesman Problem (TSP). After a literature review, an extension of the model from Murray and Chu (2015) we present a model for the problem with multiple vehicles. This model is developed as a Mixed Integer Linear Programming (MILP) problem and solved with the solver CPLEX. A heuristic based on a Hybrid Genetic Algorithm (HGA) is also developed and presented. Our results show that the use of drones reduces the total mileage of the trucks by a significant percentage. / Nessa monografia estuda-se o Problema do Roteamento de Veículos com Drones (PRVD), motivado pelo crescente interesse da indústria em Veículos Aéreos Não Tripulados (VANTs) e suas aplicações em logística. O trabalho pioneiro de (MURRAY; CHU, 2015) mostra uma combinação entre VANT e um caminhão para realização de entregas de produtos, no qual foi proposta uma adaptação do Problema do Caixeiro Viajante (PCV). Após uma revisão de literatura, apresenta-se uma extensão do modelo de Murray and Chu (2015) para o problema com múltiplos veículos. Desenvolveu-se um modelo de Programação Linear Inteira Mista que foi resolvido com o solver CPLEX. Uma heurística basead em um Algoritmo Genético Híbrido também foi desenvolvido e é apresentada. Resultados mostram que a utilização dos VANTs reduzem a quilometragem dos caminhões significativamente.

Il y a soixante ans, le 4 octobre 1957, Spoutnik, le premier satellite artificiel conçu par l’homme, est envoyé dans l’espace. Sa seule fonction est d’émettre un bip radio à des fréquences de 20 et 40 MHz pour démontrer la puissance spatiale de l’URSS. Depuis cette époque les satellites se sont multipliés et leurs missions se sont diversifiées. Aujourd’hui, les missions des satellites sont si variées que certains quittent l’orbite terrestre. On parle dans ce cas de sondes, même si, dans le reste de cette thèse, ils seront inclus dans le terme "satellite". La mission des satellites la plus connue du grand public est la découverte de l’univers et l’exploration interplanétaire avec de célèbres satellites comme le télescope spatial international Hubble ou des sondes comme Rosetta, Voyager 1 et 2, ... Cependant de nos jours, même si l’exploration spatiale reste un enjeu majeur de l’humanité, la plupart des satellites ont des missions plus modestes qui ont pourtant un impact important sur la vie économique et politique. Les satellites en question ont aujourd’hui deux buts : la défense et le commercial. Dans les deux cas on peut diviser les satellites en deux groupes distincts : les satellites d’observation et les satellites de télécommunication. Pour fonctionner tous ces satellites utilisent un harnais électrique. Le harnais électrique regroupe tous les câbles présents dans le satellite et qui ne transportent pas de données client. Dans le cadre de cette thèse nous nous intéressons à l’optimisation de la conception du harnais électrique des satellites. / Sixty years ago, on October 4, 1957, Sputnik, the first man-made artificial satellite, was sent into space. Its only function is to emit a radio beep at frequencies of 20 and 40 MHz to demonstrate the space power of the USSR. Since then, satellites have been multiple and their missions have diversified. Today, the missions of the satellites are so varied that some leave Earth's orbit. We speak in the case of probes, even if, in the rest of this thesis, they will be included in the term "satellite". The best-known satellite mission of the general public is the discovery of the universe and interplanetary exploration with satellite satellites such as the Hubble International Space Telescope or probes such as Rosetta, Voyager 1 and 2, ... nevertheless nowadays Although space exploration remains a major issue for humanity, most satellites have smaller missions that have a significant impact on economic and political life. The satellites in question today have two goals: defense and commercial. In both cases the satellites can be divided into two distinct groups: observation satellites and telecommunication satellites. To operate all these satellites, use an electrical harness. The electrical harness includes all the cables present in the satellite and which does not carry any customer data. As part of this we are interested in optimizing the design of the electrical harness of satellites.

A Roteirização de Veículos desempenha papel fundamental nos processos modernos de distribuição de produtos e realização de serviços. A atual disseminação de recursos de tecnologia de informação e comunicação, de forma confiável e economicamente acessível, permite trabalhar com informações em tempo real e melhoram os padrões de nível de serviço associados. O presente trabalho apresenta uma solução para roteirização de veículos cujas equipes de bordo realizam serviços que justificam seu deslocamento, uma vez que as demandas estão geograficamente dispersas. Tais demandas são, em parte, conhecidas antes do despacho (permitem programação antecipada) dos veículos e suas equipes; outra parte surge durante a jornada de trabalho. Como exemplos podem-se citar os casos de serviços de montagem e manutenção de instalações, equipamentos, engenharia e inspeção de tráfego, policiamento etc. Trata-se da aplicação da roteirização parcialmente dinâmica, conforme Larsen (2000), cujas bases foram definidas por Psaraftis (1988,1995), Bertsimas et al (1993) no problema DTRP (Dynamic Travelling Repairman Problem). A função objetivo apresenta uma combinação de minimização dos custos de deslocamento, para os pedidos de serviços conhecidos antes da saída dos veículos e de minimização do tempo de resposta (chegada no local do cliente ou da ocorrência) para os casos de pedidos imediatos ou emergenciais. A solução do problema envolve um modelo computacional de testes e avaliação, heurística de Clarke e Wright (1964) para formação das rotas estáticas, no Método Húngaro (Kuhn, 1955) para designar o veículo que resulta no menor tempo de resposta no atendimento a um pedido emergencial e a heurística de Clarke e Wright modificada na otimização do restante dos pedidos quando o veículo voltar a sua rota original. O modelo computacional foi testado em uma empresa de manutenção de elevadores na cidade de São Paulo, Brasil, onde demonstrou resultados comparativamente melhores em relação ao sistema de roteirização utilizado atualmente pela empresa. / The Vehicle Routing Problem plays a critical role on modern processes related to physical distribution of goods and services. The present expansion of information and communication technology in a reliable, economic and accessible way allows real time information and requires the utilization of appropriate tools for real time decisions resulting in significant improvements in quality and service level related to dynamic vehicle routing. A dynamic routing problem is presented, in which vehicles serve geographic dispersed service demands that justify their movement in a fixed area. Such service demands are partially known before vehicles dispatching (allowing prior programming) whilst others are known during the work journey. As examples, one can mention cases concerning installation and maintenance of utilities, equipment, engineering and surveillance services that refer to applications of Partially Dynamic Routing according to Larsen (2000), the groundings of which were defined by Psaraftis (1988,1995), Bertsimas et al (1993) in the Dynamic Travelling Repairman Problem (DTRP). The objective function is a combination of the minimization of movement costs to serve the prior demands and the minimization of time to reach (time to response) Dynamic-or-emergency-demand sites. The proposed solution involves a computational model for testing and evaluating a set of heuristics and methods comprising the Clarke and Wright (1964) Heuristic to compose the static routes, the Hungarian Method (Kuhn, 1955) to assign vehicles to the dynamic demands that produces the lowest response time and, finally, a Clarke and Wright Modified Heuristic used to optimize the remainder of the route when each diverted vehicle returns to its static route. The Computational Model was applied to a lift maintenance company located in the city of São Paulo (Brazil) demonstrating better results as compared to the present routing system.

Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème. / The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem.

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2018-10-19T11:51:51Z No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) / Made available in DSpace on 2018-10-19T11:51:51Z (GMT). No. of bitstreams: 1 Rafael Emídio Murata Rodrigues.pdf: 1071545 bytes, checksum: 468e0f7e27e278e12eed0dd52f4198cc (MD5) Previous issue date: 2018-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In our lives, we constantly move in streets and neighborhoods. In general, we consider time and (or distance) when planning the route. However, their solutions may face complex problems arising from the different possibilities of solutions. Similar to route planning, the Vehicle Routing Problem was introduced by George B. Dantzig and John H. Ramser in 1959 and consists of delivering gasoline to several fuel stations; at first a mathematical proposal, later became an algorithmic approach, for planning of routes of delivery of products in an optimized way (searching the "shortest path"). Although, during the search of shortest path, they are limited to the use of the streets. In this context emerges the Human Routing Problem, such an approach is not limited to streets, but makes use of all possible paths, by vehicles and humans. Such a problem can be observed in route planning at airports, museums and a supply chain company that wants to optimize the route of delivery of its products and increase customer satisfaction. Based on the Vehicle Routing Problem, the Human Routing Problem will be proposed. Its problematic will be demonstrated in a prototype, capable of assisting in the planning of human routes and three use cases. Ideas of Human Routing Problem had inspiration in the collective foraging insects / Na nossa vida, nos locomovemos constantemente em ruas e bairros. Em geral, consideramos o tempo e (ou a distância), ao planejar a rota. Contudo, suas soluções podem enfrentar problemas complexos, decorrentes das diversas possibilidades de soluções. Semelhante a planejamento de rotas, o Problema de Roteamento de Veículos foi introduzido por George B. Dantzig, e John H. Ramser em 1959 e consiste em entregar gasolina diversos postos de combustível; a princípio uma proposta matemática, mais tarde tornou-se uma abordagem algorítmica, para planejamento de rotas de entrega de produtos de forma otimizada (buscando o “menor caminho”). Embora, durante a busca de menor caminho, limitam-se ao uso de ruas. Neste contexto emerge o Problema de Roteamento Humano, tal abordagem não se limita a ruas, mas faz uso de todos os caminhos possíveis, por veículos e humanos. Tal problemática, pode ser observada nos planejamentos de rotas em aeroportos, museus e em uma empresa de supply chain que deseja otimizar a rota de entrega dos seus produtos, e aumentar a satisfação dos seus clientes. Tomando como base central, o Problema de Roteamento de Veículos será proposto o Problema de Roteamento Humano. Sua problemática, será demonstrado em um protótipo, capaz de auxiliar no planejamento de rotas humanas e três casos de uso. As ideias do Problema de Roteamento Humano tiveram inspiração no forrageamento dos insetos coletivos

Submitted by CARLA MARIA GOULART DE MORAES (carlagm) on 2015-04-01T18:43:13Z No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) / Made available in DSpace on 2015-04-01T18:43:13Z (GMT). No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) Previous issue date: 2011 / CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Janelas de Tempo, onde devem ser atendidas as restrições de capacidade do veículo e as janelas de tempo de atendimento do cliente. Para resolver tal problema serão utilizadas as metaheurísticas Busca Tabu e Algoritmos Genéticos, além do desenvolvimento de um Algoritmo Híbrido baseado nas duas metaheurísticas. Busca-se contribuir com o desenvolvimento de um Algoritmo Híbrido focado no Problema de Roteamento de Veículos que utilize o poder de intensificação da Busca Tabu e o poder de diversificação do Algoritmo Genético, objetivando a obtenção de soluções de boa qualidade sem comprometer o tempo computacional. Nos experimentos, no que tange a Busca Tabu, analisa-se o processo de busca da através da variação do tamanho da Lista Tabu e do número máximo de iterações sem melhora do valor da função objetivo, como critério de parada, aplicados a uma política de intensificação. Para o Algoritmo Genético, é analisada a influência e o comportamento da busca com base em três operadores de cruzamento aplicados a duas políticas de elitismo. Ainda assim, para o Algoritmo Híbrido, analisa-se o impacto do tamanho da Lista Tabu e das taxas de Mutação e Cruzamento. Por fim, os resultados obtidos são comparados com os melhores métodos heurísticos encontrados na literatura e com métodos exatos, onde o Algoritmo Híbrido mostra-se robusto, obtendo soluções ótimas para diversas instancias de problemas. / This paper approaches the Capacitated Vehicle Routing Problem with Time Windows, which must obey the restrictions on vehicle capacity and time windows for customer service. To solve this problem will be used two metaheuristics, Tabu Search and Genetic Algorithms, and are developed an hybrid algorithm based on this two metaheuristics. The aim is to contribute with the development of a Hybrid Algorithm focused on Vehicle Routing Problem that uses the Tabu Search intensification power and the Genetic Algorithms diversification power, in order to obtain good quality solutions without compromising the computational time. In the experiments, with respect to Tabu Search, we analyze the search process by varying the size of the Tabu List and the maximum number of iterations without improvement in objective function value, such as stopping criterion, applied to an intensification policy. For the genetic algorithm are analyzed the influence and the search behavior on the basis of three crossover operators, applied to two elitism policies. Still, for the hybrid algorithm, we analyze the impact of the Tabu List size and rates of mutation and crossover. Finally, the results are compared with the best heuristics in the literature and with exact methods, where the Hybrid Algorithm shows robust, getting several optimal solutions.

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 soins de santé à domicile (HHC) sont un large éventail de services de santé pouvant être dispensés à domicile pour une maladie ou une blessure. Ces dernières années, le secteur des soins de santé est devenu l'un des plus grands secteurs de l'économie des pays développés. L'un des défis les plus importants dans le domaine des HHC consiste à affecter plus efficacement les ressources en main-d'œuvre et les équipements sous des ressources limitées. Étant donné que le coût du transport est l’une des dépenses les plus critiques dans les activités de l’entreprise, il est très important d’optimiser le problème de routage des véhicules pour les sociétés HHC.Cependant, la majorité des travaux existants ne prennent en compte que le modèle déterministe. Dans la pratique de HHC, le décideur et les aidants rencontrent souvent des incertitudes. Il est donc essentiel d'intégrer l'incertitude dans le modèle pour établir un calendrier raisonnable pour la société HHC. Cette thèse aborde le problème du routage et de la planification HHC en prenant en compte respectivement la demande non déterministe, le service et le temps de parcours. Le corps principal de la thèse est composé de trois œuvres indépendantes.(1) Sur la base de la théorie de la crédibilité floue, nous avons proposé un modèle de programmation par contraintes de hasard flou (FCCP) pour le problème de routage HHC avec une demande floue. Ce modèle présente à la fois des caractéristiques d'optimisation combinatoire et de FCCP. Pour faire face au problème à grande échelle, nous avons développé un algorithme génétique hybride avec la simulation de Monte Carlo. Trois séries d'expériences ont été menées pour valider les performances du modèle et de l'algorithme proposés. Enfin, l’analyse de sensibilité a également porté sur l’observation du paramètre variable impliqué dans la prise de décision floue.(2) En fonction de l'activité des soignants de HHC, nous avons proposé un modèle de programmation stochastique en deux étapes avec recours (SPR) pour la livraison et la reprise simultanées avec des temps de trajet et de service stochastiques dans HHC. Pour résoudre le modèle, nous avons d’une part réduit le modèle au cas déterministe. Le solveur de Gurobi, le recuit simulé (SA), l’algorithme de chauve-souris, l’algorithme de luciole ont été proposés pour résoudre le modèle déterministe pour 56 instances respectivement. Enfin, le SA a été adopté pour traiter le modèle SPR. Une comparaison entre les solutions obtenues par les deux modèles a également été réalisée pour mettre en évidence la prise en compte des temps de parcours et de service stochastiques.(3) Pour garantir la qualité du service, sur la base d’un budget de la théorie de l’incertitude, nous avons proposé un modèle d’optimisation robuste (RO) pour HHC Routing, prenant en compte les exigences en termes de temps de déplacement et de service. La vérification de la solution réalisable a été réécrite en tant que fonction récursive complexe. Recherche tabou, SA, Recherche de voisinage variable sont également adaptés pour résoudre le modèle. Un grand nombre d'expériences ont été réalisées pour évaluer le modèle déterministe et le modèle RO. Une analyse de sensibilité des paramètres a également été effectuée. / Home health care (HHC) is a wide range of healthcare services that can be given in one's home for an illness or injury. In recent years, the healthcare industry has become one of the largest sectors of the economy in developed countries. One of the most significant challenges in HHC domain is to assign the labor resources and equipment more efficiently under limited resources. Since the transportation cost is one of the most critical spendings in the company activities, it is of great significance to optimize the vehicle routing problem for HHC companies.However, a majority of the existing work only considers the deterministic model. In the practical of HHC, the decision-makers and caregivers often encounter with uncertainties. So, it is essential to incorporate the uncertainty into the model to make a reasonable and robust schedule for HHC company. This thesis addresses the HHC routing and scheduling problem with taking into account the non-deterministic demand, uncertain service and travel time respectively. The main body the thesis is composed of three independent works.(1) Based on the Fuzzy Credibility Theory, we proposed a fuzzy chance constraint programming (FCCP) model for HHC routing problem with fuzzy demand. This model has both characteristics of combinatorial optimization and FCCP. To deal with the large-scale problem, we developed a Hybrid Genetic Algorithm with the Monte Carlo simulation. Three series of experiments were conducted to validate the performance of the proposed model and algorithm. At last the sensitivity analysis was also carried out the observe the variable parameter involved in the fuzzy decision-making.(2) According to the activity of the caregivers in HHC, we proposed a two-stage stochastic programming model with recourse (SPR) for the simultaneous delivery and pick-up with stochastic travel and service times in HHC. To solve the model, firstly, we reduced the model to the deterministic one. Gurobi Solver, Simulated Annealing (SA), Bat Algorithm (BA), Firefly Algorithm (FA) were proposed to solve the deterministic model for 56 instances respectively. At last the SA was adopted to address the SPR model. Comparison between the solutions obtained by the two models was also conducted to highlight the consideration of the stochastic travel and service times.(3) To guarantee the service quality, based on a budget of uncertainty theory, we proposed a Robust Optimization (RO) model for HHC Routing with considering skill requirements under travel and service times uncertainty. The feasible solution check was rewritten as a complex recursive function. Tabu Search, SA, Variable Neighborhood Search are adapted to solve the model. A large number of experiments had been performed to evaluate the deterministic model and the RO model.

[pt] Desde a sua origem, as abordagens a problemas de Otimização Combinatória polarizam-se entre métodos exatos e heurísticos. Recentemente, porém, estratégias que combinam ambos os métodos têm sido propostas para os mais variados problemas, apresentando resultados promissores. Nesse contexto, destacam-se os conceitos de vizinhaças de bola e elipsoidal, que realizam buscas em relação a uma ou mais soluções de referência. Este trabalho estuda a aplicação de tais vizinhanças para o Problema de Roteamento de Veículos com Restrição de Capacidade (CVRP), sobre o algoritmo de Branch-and-Cut-and-Price Robusto. Experimentos foram realizados e seus resultados analisados. / [en] Since its inception, approaches to Combinatorial Optimization were polarized between exact and heuristic methods. Recently, however, strategies that combine both methods have been proposed for various problems, showing promising results. In this context, the concepts of ball and ellipsoidal neighborhood appear, which perform a search regarding one or more reference solutions. This work studies the application of such neighborhoods for the Capacitated Vehicle Routing Problem (CVRP), using the Robust Branchand- Cut-and-Price algorithm. Experiments were made and its results were analyzed.

This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.