ARARUNA, A. R. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 88f. Dissertação (Mestrado em Ciência da Computação) - Departamento de Computação, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Aline Mendes (alinemendes.ufc@gmail.com) on 2015-09-18T13:05:49Z
No. of bitstreams: 1
2013_dis_arararuna.pdf: 2056638 bytes, checksum: f70ff44a38a60bdeaddc2fbf6e8fd0cf (MD5) / Approved for entry into archive by Aline Mendes(alinemendes.ufc@gmail.com) on 2015-09-18T13:06:28Z (GMT) No. of bitstreams: 1
2013_dis_arararuna.pdf: 2056638 bytes, checksum: f70ff44a38a60bdeaddc2fbf6e8fd0cf (MD5) / Made available in DSpace on 2015-09-18T13:06:28Z (GMT). No. of bitstreams: 1
2013_dis_arararuna.pdf: 2056638 bytes, checksum: f70ff44a38a60bdeaddc2fbf6e8fd0cf (MD5)
Previous issue date: 2013 / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/13307 |
| Date | January 2013 |
| Creators | Araruna, Arthur Rodrigues |
| Contributors | Andrade, Rafael Castro de |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds