XINFORMAÇÕES SOBRE DIREITOS AUTORAIS
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital
Título: MODELOS E ALGORITMOS PARA O TEAM ORIENTEERING PROBLEM Autor: FRANCISCO HENRIQUE DE FREITAS VIANA
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
MARCUS VINICIUS S P DE ARAGAO - ORIENTADOR
EDUARDO UCHOA BARBOZA - COORIENTADOR
Nº do Conteudo: 19542
Catalogação: 18/05/2012 Idioma(s): PORTUGUÊS - BRASIL
Tipo: TEXTO Subtipo: TESE
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=19542@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=19542@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.19542
Resumo:
Título: MODELOS E ALGORITMOS PARA O TEAM ORIENTEERING PROBLEM Autor: FRANCISCO HENRIQUE DE FREITAS VIANA
EDUARDO UCHOA BARBOZA - COORIENTADOR
Nº do Conteudo: 19542
Catalogação: 18/05/2012 Idioma(s): PORTUGUÊS - BRASIL
Tipo: TEXTO Subtipo: TESE
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=19542@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=19542@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.19542
Resumo:
O Team Orienteering Problem é um problema de roteamento de veículos
sobre um grafo com durações associadas aos arcos e prêmios atribuídos à
visitação de cada vértice. Neste problema, considera-se que as visitas são
realizadas por uma frota com um número fixo de veículos idênticos e que
existe uma duração total máxima para as rotas serem finalizadas. Cada
vértice pode ser visitado no máximo uma vez, não havendo obrigatoriedade
de se visitar todos os vértices, devido à restrição que limita o tempo m´aximo
de duração das rotas. O objetivo do problema é maximizar o prêmio total
ganho por todas as rotas. Neste trabalho, foram propostas duas abordagens:
uma exata e uma heurística. Na abordagem exata, foi desenvolvida uma
formulação baseada em arcos e uma formulação estendida na qual cada
arco tem um índice extra. Esse índice representa o tempo de partida de um
veículo ao percorrer o arco. Através de transformações sobre a formulação
estendida, foi obtida uma formulação, cuja relaxação, problema mestre
restrito, foi resolvida pela técnica de geração de colunas. O subproblema
de geração de colunas foi resolvido por programação dinâmica em tempo
pseudo-polinomial. Este algoritmo gera rotas não elementares, que são rotas
nas quais subciclos são permitidos. Com o objetivo de eliminar os subciclos
das rotas não elementares, uma nova classe de desigualdades denominada
min cut foi proposta. Aplicando-se um algoritmo Branch-Cut-and-Price
(BCP) foram obtidos alguns novos limites superiores. A abordagem exata
obteve resultados competitivos quando comparada ao melhor algoritmo
exato já proposto para esse problema. Na abordagem heurística, além de
uma vizinhança k-opt, foi explorada também uma busca elipsoidal que
adiciona um corte à formulação do algoritmo Branch-Cut-and-Price. Esse
novo corte reduz o espa¸co de busca a uma vizinhança em torno de um
conjunto de soluções conhecidas. Essa busca é utilizada como um operador
de crossover executado em todas as iterações de um algoritmo evolutivo.
Essa abordagem converge em um tempo computacional razoável e encontra
soluções ótimas ou próximas da ótima para algumas instâncias da literatura.