In this study, three different algorithms are implemented to solve thecapacitated vehicle routing problem with and without time windows:ant colony optimization, a genetic algorithm and a genetic algorithmwith self-organizing map. For the capacitated vehicle routing problemthe Augerat et al’s benchmark problems were used and for the capaci-tated vehicle routing problem with time windows the Solomon’sbenchmark problems. All three algorithms were tuned over thirtyinstances per problem with the tuners SPOT and ParamILS. The tuningresults from all instances were combined to the final parameter valuesand tested on a larger set of instances. The test results were used tocompare the algorithms and tuners against each other. The ant colonyoptimization algorithm outperformed the other algorithms on bothproblems when considering all instances. The genetic algorithm withself-organizing map found more best known solutions than any otheralgorithm when using parameters, on the capacitated vehicle routingproblem. The algorithms performed well and several new best knownresults were discovered for the capacitated vehicle routing problem andnew best solutions found by heuristics were discovered for the 100customer Solomon problems. When comparing the tuners they bothworked well and no clear winner emerged.

Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.

abstract: This thesis presents a successful application of operations research techniques in nonprofit distribution system to improve the distribution efficiency and increase customer service quality. It focuses on truck routing problems faced by St. Mary’s Food Bank Distribution Center. This problem is modeled as a capacitated vehicle routing problem to improve the distribution efficiency and is extended to capacitated vehicle routing problem with time windows to increase customer service quality. Several heuristics are applied to solve these vehicle routing problems and tested in well-known benchmark problems. Algorithms are tested by comparing the results with the plan currently used by St. Mary’s Food Bank Distribution Center. The results suggest heuristics are quite completive: average 17% less trucks and 28.52% less travel time are used in heuristics’ solution. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2015

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T16:00:19Z No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) / Made available in DSpace on 2015-07-17T16:00:19Z (GMT). No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) Previous issue date: 2015-01-27 / In recent years, the Vehicle Routing Problem (VRP) has attracted an increasing attention from researchers due to the great difficulty of its solution and its presence in various practical situations. As consequence, there has been great effort to develop more robust, agile and flexible algorithms that can be modeled according to the scenario that describes the problem. The Capacitated Vehicle Routing Problem (CVRP) is a version of VRP and consists in determining a set of routes to be followed by a fleet of homogeneous vehicles, which must serve a set of customers. The objective is to minimize the total cost of the routes subject to the following restrictions: i) routes must start and end in the same distribution center; ii) each customer must be visited once and its demand must be met in full by only one vehicle and iii) the sum of customers' demands included in a route cannot exceed the vehicle capacity. The CVRP belongs to the class of NP-hard problems, that is, problems whose the solution usually requires non-polynomial complexity time algorithms and because of this are usually resolved with the use of heuristic and metaheuristics algorithms. In this work, it was investigated the optimization of CVRP using Genetic Algorithm (GA) with alternative chromosome representations and heuristics. To this end, three strategies, each one employing a different model of chromosome representation for encoding solution in AG were proposed. In addition, the heuristics of Gillett and Miller to generate solutions that are included in the initial population of GA and Hill-climbing for refinement of GA solutions, after a number of generations without improvement, were adopted. In the performed experiments, the results obtained by the proposed strategies were compared with each other and also with the best results found in the literature for a set of known instances. These experiments showed that the proposed strategies provided good results with respect to quality of solutions well as the computational cost. In addition, it was possible to evaluate the viability of each employed chromosome representation and the contribution of the heuristics in the convergence process of GA. / Nos últimos anos o Problema de Roteamento de Veículos (PRV) tem atraído cada vez mais a atenção de pesquisadores devido à grande dificuldade de solução e sua presença em várias situações do cotidiano. Em decorrência disso, tem havido um grande esforço para desenvolver algoritmos cada vez mais robustos, ágeis e flexíveis e que possam ser modelados com base no cenário que descreve o problema. O Problema de Roteamento de Veículos Capacitado (PRVC) é uma versão do PRV e consiste em encontrar um conjunto de rotas a serem seguidas por uma frota de veículos homogêneos, os quais devem atender a um conjunto de clientes. O objetivo é minimizar o custo total das rotas respeitando as seguintes restrições: i) as rotas devem iniciar e terminar no mesmo centro de distribuição; ii) cada cliente deve ser visitado uma única vez e sua demanda deve ser atendida integralmente por apenas um veículo e iii) a soma das demandas dos clientes incluídos em uma rota não pode exceder a capacidade do veículo. Problemas desta natureza podem ser classificados como NP-Hard, ou seja, possuem ordem de complexidade não polinomial e normalmente são resolvidos com uso de algoritmos heurísticos e meta-heurísticos. Neste trabalho investigou-se a otimização do PRVC usando Algoritmo Genético (AG) com representações cromossômicas e heurísticas alternativas. Para tanto, foram propostas três estratégias, cada uma delas empregando um modelo diferente de representação cromossômica para codificação da solução no AG. Além disso, foram empregadas as heurísticas de Gillett e Miller para gerar soluções que são incluídas na população inicial do AG e Subida/Descida de Encosta para refinamento das soluções, após um certo número de gerações sem melhoria. Nos experimentos realizados, os resultados obtidos pelas estratégias propostas foram comparados entre si e também com os melhores resultados encontrados na literatura para um conjunto de instâncias conhecidas. Pode-se constatar, a partir desses experimentos, que as estratégias apresentaram bons resultados tanto no que tange a qualidade das soluções quanto ao tempo computacional dispendido. Em adição, foi possível avaliar a viabilidade de cada uma das representações cromossômicas empregadas, além da contribuição das heurísticas no processo de convergência do ag.

Environmental issues are a vital concern in today’s world. The Swedish government and local businesses are developing a sustainable business and eco-friendly environment for city inhabitants. Last-mile pickup and delivery services are a key concern, which significantly impacts the environment and society. The Norwegian/Swedish parcel delivery company Bring, the reusable waste management company Ragn-Sells, the city of Stockholm, the research institute Sustainable Innovation, and the KTH Royal Institute of Technology are jointly working together in the Intercitylog2 project with a vision to handle better last-mile pickups or deliveries that are jointly serviced by small electric vehicles from an urban micro terminal. This thesis addresses the optimizations of simultaneous pickup and delivery operations using homogeneous vehicles and considering vehicle capacity, time windows and environmental constraints. A mathematical model is developed to address the problem using an exact commercial solver. The quality of the solutions has been evaluated with real pickup and deliveries of the participating company. The primary objective function is formulated to minimize the travel cost by finding the shortest path, and the results are compared with current routing operation data. KPIs are developed and evaluated based on the facts and figures from the obtained results of the experiments. The two scenarios, big vehicles and small vehicles are also developed and evaluated to find the best route optimization opportunity for the companies. The results show that the optimized operation could decrease delivery distance by 36.72% and 37.13% and delivery time by 43.65% and 47.08% for big and small vehicles operations, respectively, compared to the current routing operations. A round trip can complete within a defined time frame to avoid the battery running out during a route. Energy constraints demonstrate that using electric vehicles considerably reduce significant amounts of CO2 emission from the environment. / Miljöfrågor är en viktig fråga i dagens värld. Den svenska regeringen och lokala företag arbetar tillsammans för att utveckla ett hållbart företagande och miljövänlig miljö för stadens invånare. Last-mile hämtning och leveranstjänster är en viktig fråga, som avsevärt påverkar miljön och samhället.Det norsk/svenska paketleveransföretaget Bring, återanvändbara avfallshanteringsföretaget Ragn- Sells, Stockholms stad, forskningsinstitutet Sustainable Innovation och Kungliga Tekniska Högskolan arbetar tillsammans i Intercitylog2-projektet för en vision för att bättre hantera last-mile pickuper eller leveranser som gemensamt betjänas av små elfordon från en urban mikroterminal. Detta examensarbete behandlar optimering av samtidiga hämtnings- och leveransoperationer med homogena fordon och med hänsyn till fordonskapacitet, tidsfönster och miljömässiga begränsningar. En matematisk modell utvecklas för att ta itu med problemet med en exakt kommersiell lösare och kvaliteten på lösningarna har utvärderats med verklig upphämtning och leveranser från det deltagande företaget. Den primära målfunktionen är formulerad för att minimera reskostnaden genom att hitta den kortaste vägen, och resultaten jämförs med aktuella ruttoperationsdata. KPI:er utvecklas och utvärderas utifrån fakta och siffror från de erhållna resultaten av experimenten. De två scenarierna, stora fordon och små fordon, är också utvecklade och utvärderade för att hitta den bästa ruttoptimeringsmöjligheten för företagen. Resultaten visar att den optimerade driften kan minska leveransavståndet med 36,72% och 37,13% och leveranstiden med 43,65% och 47,08% för stora och små fordonsoperationer, jämfört med nuvarande ruttoperationer. En tur och retur kan genomföras inom en definierad tidsram för att undvika att batteriet tar slut under en rutt. Energibegränsningar visar att användning av elfordon avsevärt minskar betydande mängder CO2-utsläpp från miljön.

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 / Transport and delivery companies are confronted by difficulties in their transportation process due to the scale and the complexity of their distribution process. In this context, we propose a comprehensive approach to General Delivery Problem (GDP). In terms of methodology, it is a hierarchical (strategic, tactical and operational) and structured approach. It consists of designing and decomposing the GDP into well identified basic delivery problems as independent as possible. These basic transport problems involve the problems about transportation, intermediate facility, agencies, routings, etc. At the algorithm level, models and solution algorithms have been proposed to solve these basic delivery problems in the operational phase, taking account in particular transportation restriction about the number and capacity of vehicles.At the application level, two real examples are discussed: one is the delivery system of a delivery company; the other one is the delivery system of the Regional Fire and Emergency Center in the north of France

Reliable electricity distribution systems are crucial; hence, the maintenance of such systems is highly important, and in Sweden strictly regulated. Poorly planned maintenance scheduling leads unnecessary driving which contributes to increased emissions and costs.  Maintenance planning is similar to the capacitated vehicle routing problem, CVRP, a combinatorial optimization problem. Each route has an origin location, in this case is the office of the maintenance worker. The origin is the starting and ending point of each route. In addition, conditions such as due date for inspection has an impact on how components in the network are prioritized. The maintenance planning problem is likely NP-hard.  Given the above, the aim for this study is to develop a heuristic algorithm that efficiently generates daily inspection schedules on a yearly basis. There are multiple tools and algorithms already developed to solve these kinds of problems, for example the Google’s OR-Tools library, which provide optimal or near optimal solutions to VRP problems. The time complexity of those tools makes them impractical to use when planning maintenance of electrical networks since they can contain many thousands of components i.e., nodes. The main aim of this study is to develop an algorithm that provides a solution good enough compared to the solutions computed by the tools mentioned above but with a lower time complexity.  In order to develop and test the algorithm an electrical distribution network data is required. Due to the sensitive nature of this data, a simulated network is generated in place of using real data. The simulated network is based on land use data from the city of Uppsala, Sweden, and is based on the spatial distribution of an existing electrical distribution network in Örebro, Sweden. The scheduling and routing algorithm developed works by dividing candidate nodes into subsets. The division is done by using Density-based spatial clustering of applications with noise (DBSCAN). The clustering is made by querying all objects that requires an inspection to be performed that year. As a post-processing step all noise points are appended to the closest neighboring cluster. Then a distance map is computed for the objects within each cluster. An inspection day route is computed by applying a greedy forward selection in each cluster, always selecting a random unvisited starting node until all nodes within the cluster has been visited. This is then repeated 100 times for each cluster, finally keeping the best iteration. The number of iterations is based on evaluating the gain per additional iteration which appear to be logarithmic. The greedy forward selection means that the algorithm has a linear time complexity after the clustering and distance map computation is done.  The algorithm is evaluated by comparing the total driving time for the computed route to the output routes of a modified Concorde TSP solution and the solution of Google’s VRP solver.  The results show that the algorithm performs better in areas with shorter average neighborhood distance and driving time of the output route decrease with higher number of iterations. Although the VRP based baselines methods return solutions with inspection routes that are roughly 25% shorter than the proposed method, for realistic problem sizes the proposed method uses less compute resources i.e., time and memory. Furthermore, while the proposed method has a linear time and space complexity whereas the baselines have exponential time complexity. Finally, the VRP based back-optimization solutions are not practical in real settings when inspection tasks are added / changed daily due to service tasks and unfinished routes or when the number of nodes is substantially larger than the roughly 1 000 nodes used in the evaluation.Due to the sensitive nature of electrical distribution data the performance of the algorithm could not be compared to actual maintenance schedules. But with all likelihood the computed schedules should be significantly more efficient than manually planned schedules. / Att ha pålitliga elnät är essentiellt för ett välfungerande samhälle därav är underhållet av sådana system av stor vikt och i Sverige strikt reglerat. Dåligt planerade besiktningar leder till onödig körning inom nätet vilket bidrar till ökade utsläpp och kostnader. Underhållsplanering liknar problemet, CVRP, ett kombinatoriskt optimeringsproblem. Varje rutt har en ursprungsplats, i detta fall är besiktningsmannens kontor. Kontoret är start- och slutpunkten för varje rutt. Dessutom har villkor som sista besiktningsdatum en inverkan på hur komponenter i nätet prioriteras. Underhållsplaneringsproblemet är sannolikt NP-svårt. Mot bakgrund av ovanstående är syftet med denna studie att utveckla en algoritm som effektivt genererar dagliga besiktningsscheman på årsbasis. Det finns redan flera verktyg och algoritmer som har utvecklats för att lösa den här typen av problem, till exempel Googles OR-Tools, som beräknar optimala eller nästan optimala lösningar på VRP-problem. Tidskomplexiteten hos dessa verktyg gör dem opraktiska att använda vid planering av underhåll av elnät eftersom dessa kan innehålla många tusen komponenter, dvs noder. Huvudsyftet med denna studie är att utveckla en algoritm som ger en lösning som är tillräckligt bra jämfört med de lösningar som beräknas av de verktyg som finns idag men med en lägre tidskomplexitet.För att utveckla och testa algoritmen krävs elnätsdata. På grund av denna datas känsliga natur genereras ett simulerat nätverk istället för att använda riktiga data. Det simulerade nätet är baserat på markanvändningsdata från Uppsala, Sverige, och på den rumsliga distributionen av ett befintligt eldistributionsnät i Örebro, Sverige. Schemaläggnings- och ruttalgoritmen som utvecklats fungerar genom att dela upp kandidatnoder i delmängder. Uppdelningen görs genom att använda densitetsbaserad spatial klustring (DBSCAN). Klustringen görs genom att välja ut alla objekt som behöver besiktigas det året. Som ett efterbehandlingssteg läggs alla bruspunkter till det närmaste intilliggande klustret. Sedan beräknas en distansmatris för objekten inom varje kluster. En besiktningsrutt beräknas genom att inom varje kluster alltid starta på en slumpmässig vald ej besökt startnod. Därefter väljs den närmsta nod tills alla noder inom klustret har besökts. Detta upprepas sedan 100 gånger för varje kluster, och slutligen behålls den bästa iterationen. Antalet iterationer baseras på att utvärdera förbättringen per ytterligare iteration - som verkar vara logaritmisk. Det här innebär att algoritmen har en linjär tidskomplexitet efter att klustringen och beräkningen av distansmatrisen har genomförts. Algoritmen utvärderas genom att jämföra den totala körtiden för den beräknade rutten med rutterna för en modifierad Concorde TSP-lösning och lösningen från Googles VRP-solver. Resultaten visar att algoritmen presterar bättre i områden med kortare genomsnittligt avstånd mellan noderna och körtiden för besiktningsrutterna minskar med ett högre antal iterationer. Även om de existerande VRP-algoritmerna returnerar lösningar med besiktningsrutter som är cirka 25 % kortare än den föreslagna metoden, så är dessa inte realistiska att använda när antalet noder närmar sig de av ett riktigt elnät.Dessutom, medan den föreslagna metoden har en linjär tids-och rymdkomplexitet medan de existerande VRP-algoritmerna har en exponentiell tidskomplexitet. Slutligen är de VRP-baserade algoritmerna inte praktiska i verkligheten när besiktningar läggs till eller ändras eller när antalet noder är avsevärt större än de cirka 1 000 noder som används i utvärderingen. På grund av den känsliga karaktären hos elnätsdata kunde algoritmens prestanda inte jämföras med faktiska besiktningsscheman. Men med all sannolikhet borde de beräknade besiktningsschemana vara betydligt effektivare än manuellt planerade scheman.

Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-03-08T14:57:43Z No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-12T11:16:50Z (GMT) No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-12T11:16:50Z (GMT). No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the resolution of problems that involve the location, routing, and packing decisions with focus on the location routing problem, capacitated vehicle routing problem with two-dimensional loading constraints, and location routing problem with two-dimensional loading constraints. For that, it is proposed a framework that reuses part of the algorithms, which are of a common domain, such that the development of the project is systematized. The objective of the framework is allowing the resolution of different variants of problems that integrate location, routing, and packing decisions without the need to replicate algorithms. As a proposal for an algorithm, it is developed a hybrid heuristic, which involves the cooperation between the simulated annealing and the artificial algae algorithm. The simulated annealing has four neighborhood operators, local search, and three procedures to diversify the solution. The artificial algae algorithm is combined with the skyline method in order to verify the feasibility of the two-dimensional packing constraints. Once the framework and heuristics have been codified, computational experiments are performed to test its performance, as well as comparisons are made with the most recent results published in the literature. The results show that the heuristic is competitive with other methods from the literature since it could obtain 36.25% solutions equal to the best ones reported in the literature of the location routing problem, besides the average GAP being 0.57%. For the vehicle routing problem with two-dimensional loading constraints, the heuristic could obtain 43.05% solutions equal to the best known in the literature, besides the average GAP being 3.33%. The results obtained for the location routing problem with twodimensional loading constraints were satisfactory. / Este trabalho trata da resolução de problemas que envolvem decisões de localização, roteamento e empacotamento com foco nos problemas de localização e roteamento, roteamento de veículos capacitado com restrições de empacotamento bidimensional, e localização e roteamento com restrições de empacotamento bidimensional. Para tanto, propõe-se um framework capaz de reutilizar parte dos algoritmos, que são de domínio comum, para que o desenvolvimento do projeto seja sistematizado. O objetivo é que o framework possibilite a resolução de diferentes variantes do problema que integram as decisões de localização, roteamento e empacotamento sem ter que replicar algoritmos. Como proposta de algoritmo, desenvolve-se uma heurística híbrida, a qual envolve a cooperação entre dois métodos, o recozimento simulado e o algoritmo artificial de algas. O recozimento simulado possui quatro operadores de vizinhança, procedimentos de busca local e três procedimentos para diversificar a solução. O algoritmo artificial de algas é combinado com a técnica Skyline para verificar as restrições de empacotamento bidimensional. A partir da codificação do framework e da heurística, experimentos computacionais foram realizados para testar o seu desempenho e comparar os resultados com os mais recentes da literatura. Os resultados indicam que a heurística é competitiva com os demais métodos da literatura, sendo possível obter 36,25% de soluções iguais às melhores reportadas na literatura do problema de localização e roteamento, além do GAP médio ter sido de 0,57%. No problema de roteamento de veículos com restrições de empacotamento bidimensional, a heurística obteve 43,05% soluções iguais às melhores conhecidas na literatura, além do GAP médio ter sido de 3,33%. Os resultados obtidos para o problema de localização e roteamento com restrições de empacotamento bidimensional foram satisfatórios.

Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le problème est défini sur un réseau routier où différents chemins alternatifs peuvent être utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine. S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite au transfert de leur demande d’un grand à un petit véhicule à un point de transfert. Comme un point de transfert n’a pas de capacité, une problématique de synchronisation apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les résultats numériques montrent que la métaheuristique proposée exploite les opportunités d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points de transfert. Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions. Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail, le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap- prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les instances utilisées pour tester notre approche hybride sont les mêmes que celles du second article. Nous avons observé que notre algorithme ne peut produire que des solutions lé- gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem (CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ). In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris- tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic is based on the ruin and recreate principle and removes strings of consecutive customers in the routes of the current solution and then reinserts the removed customers to create a new solution. The problem is formulated in a full road network where different alternative paths can be used to go from one customer to the next. Also, the travel time on each arc of the road network is not fixed, but depends on the departure time from the origin node. Motivated from city logistics applications, we also consider two types of vehicles, large and small, with large vehicles being forbidden from the downtown area. Thus, downtown customers can only be served through a transfer of their goods from large to small vehicles at designated transfer points. Since transfer points have no capacity, synchronization issues arise when a large vehicle must meet one or more small vehicles to transfer goods. As opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex than the CVRP, important modifications to the original SISR metaheuristic were required. To evaluate the performance of our algorithm, we generated a set of test instances by extending existing instances of the TDVRPTW-RN . The road networks are divided into three regions: downtown, boundary and outside. The downtown and outside areas are the realm of small and large vehicles, respectively, while the boundary area that contains the transfer points can be visited by both small and large vehicles. The results show that the proposed metaheuristic exploits optimization opportunities by moving as much as possible neutral customers (which can be served by either small or large vehicles) from the routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points. The second and third papers examine more fundamental issues, using the classical CVRP as a testbed. In the second paper, an experimental study is designed to examine the impact of inaccurate data (distances) on the performance of different types of heuristics, as well as one exact method, for the CVRP. For this purpose, different levels of distance inaccuracies were introduced into well-known benchmark instances for the CVRP with 100 to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the best, even in the presence of high inaccuracy levels, and that they are not as much affected by inaccuracies when compared to a simple heuristic. Some experiments performed on real-world instances led to the same conclusions. The third paper focuses on the integration of learning into the state-of-the-art SISR for the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced by a reinforcement learning technique inspired from ant colony systems. The learning component is aimed at identifying promising edges, namely those that are often found in previously encountered high-quality solutions. The inclusion of these promising edges is then favored during the reinsertion of removed customers. The benchmark instances of the second paper were also used here to test the new hybrid algorithm. We observed that the latter can produce only slightly better solutions than the original SISR, due to the quasi-optimality of the original solutions.