Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/18291
Título: Caminho mínimo com restrição probabilística de atraso máximo
Título em inglês: Probabilisticaly delay constrained shortest path problem
Autor(es): Araruna, Arthur Rodrigues
Orientador(es): Andrade, Rafael Castro de
Palavras-chave: Matemática discreta e combinatória
Caminho mínimo
Restrição probabilística
Otimização inteira
Shortest path
Probabilistic constraint
Data do documento: 2013
Citação: ARARUNA, A. R. (2013)
Resumo: No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.
Abstract: In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem.
Descrição: ARARUMA Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013.
URI: http://www.repositorio.ufc.br/handle/riufc/18291
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2013_dis_arararuna.pdf2,12 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.