Submitted by MARCOS LEANDRO TEIXEIRA DE OLIVEIRA (marcosteixeira@ufv.br) on 2018-09-04T13:38:28Z No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) / Made available in DSpace on 2018-09-04T13:38:28Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) Previous issue date: 2018-01-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o Problema de Roteamento de Veículos para Coleta de Lixo com Janelas de Tempo (WCVRPTW), cujo objetivo é encontrar as rotas para os veículos coletores de lixo de modo que todos os clientes sejam plenamente atendidos e a distância total percorrida pelos veículos seja a menor possível, minimizando assim os custos de transporte. Para alcançar este objetivo é necessário que algumas restrições sejam atendidas: os clientes devem ser atendidos dentro de um período de tempo; existe horário de saída e retorno dos veículos ao depósito; os veículos possuem restrições de capacidade; as rotas possuem restrições de volume de carregamento e número de clientes atendidos; os veículos devem sair e retornar vazios ao depósito, e, quando cheios, devem ir para o aterro sanitário mais próximo para descarga do lixo. Além disso, os motoristas dos veículos devem realizar uma parada de almoço. O WCVRPTW é um problema real que pertence à classe NP-difícil. Para resolvê-lo, são desenvolvidos quatro algoritmos heurísticos: Simulated Annealing (SA), Tabu Search (TS), e dois algoritmos híbridos baseados nas metaheurísticas Iterated Local Search (ILS) e Variable Neighborhood Descent (VND), denominados ILS-VND e ILS-RVND. Os desempenhos dos algoritmos propostos são analisados em instâncias de pequeno e médio porte geradas para este trabalho, e também em instâncias de grande porte disponíveis na literatura. Os experimentos computacionais mostram que os algoritmos propostos são eficientes, competitivos e rápidos. / In this work we address The Waste Collection Vehicle Routing Problem with Time Windows (WCVRPTW), whose objective is to find the routes for garbage collection vehicles so that all customers are fully served and the total distance traveled by the vehicles is the smallest possible, thus minimizing transportation costs. In order to achieve this objective, some constraints must be satisfied: customers must be ser- ved within a period of time; there are departing and return times of the vehicles to the warehouse; vehicles have capacity constraints; the routes have loading volume constraints and number of customers served; the vehicles should leave and return empty to the depot, and when full should go to the nearest landfill for garbage disposal. In addition, drivers of the vehicles must have a lunch break. WCVRPTW is a real problem that belongs to the NP-hard class. In this work, to solve it, four heuristic algorithms are developed: Simulated Annealing (SA), Tabu Search (TS), and two hybrid methods based on the Iterated Local Search (ILS) and Varia- ble Neighborhood Descent (VND) metaheuristics, called ILS-VND and ILS-RVND. The performances of the proposed methods are analyzed in small and medium-sized instances generated in this work, and also in large instances available in the lite- rature. Computational experiments show that the proposed methods are efficient, competitive and fast.