A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-30032012-122542 |
| Date | 19 December 2011 |
| Creators | Rosin, Rafael Alzuguir |
| Contributors | Yoshizaki, Hugo Tsugunobu Yoshida |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0021 seconds