Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-24012018-102912 |
| Date | 25 April 2001 |
| Creators | Oliveira, Rúbia Mara de |
| Contributors | Arenales, Marcos Nereu |
| 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.0017 seconds