[pt] O crescimento da população no mundo inteiro tem gerado nos últimos anos o nascimento de novas economias e o aumento nos níveis de demanda dos produtos. Com os novos perfis dos consumidores e as novas tendências das mercadorias, as empresas estão criando produtos com ciclo de vida curto, aumentando a geração de Resíduos Sólidos Domiciliares nos municípios. Devido ao fenômeno anterior, o número de pontos de coleta nos itinerários dos veículos aumenta, gerando custos e distâncias maiores, diminuindo a produtividade e qualidade do Sistema de Transporte das empresas de limpeza. Nesta dissertação apresenta-se o planejamento das rotas de coleta de Resíduos Sólidos Domiciliares do Programa de Remoção Gratuita da Companhia Municipal de Limpeza Urbana – COMLURB na zona sul da cidade do Rio de Janeiro, como método de apoio na logística de transporte do sistema de limpeza da cidade. Para tal objetivo, utilizou-se o Sistema de Informação Geográfica para Transporte (SIG-T) TransCAD versão 5.0 Academic Licence com a aplicação do Problema de Roteirização dos Veículos com Janela de Tempo (PRVJT). Os resultados obtidos nas análises reduziram a distância total executada pelos veículos em 30,34 por cento, demostrando a importância da metodologia em problemas de transporte reais. / [en] Population growth worldwide has generated in recent years the emergence of new economies and the increased levels of demand for products. With the new profiles of consumers and new trends of goods, companies are creating products with short life cycle, increasing the generation of Household Solid Waste in the municipalities. Due to the previous phenomenon, the number of collection points on the routes of vehicles increases, generating costs and greater distances, decreasing the productivity and quality of the transport system of cleaning companies. In this dissertation presents the planning of the waste collection routes of Household Solid Free Removal Program of the Municipal Company of Urban Cleaning - COMLURB in the south of the city of Rio de Janeiro, as a support method in the Transport Logistics of city cleaning system . For this purpose, we used the Geographic Information System for Transportation (GIS-T) TransCAD version 5.0 Academic License to the implementation of the Vehicle Routing Problem with Time Windows (VRPTW). The results obtained in this study reduced the overall distance traveled by vehicles in 30, 34 per cent, showing the importance of the methodology in real transportation problems.

[pt] Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados. Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS. / [en] This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.