Problema do caixeiro viajante mochileiro: formulações e métodos de soluções
Data
2015-04-28
Autores
Nakamura, Katia Yoshime 
Orientadores
Nascimento, Maria Cristina Vasconcelos Nascimento
Tipo
Dissertação de mestrado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
Backpacking is a way of traveling adopted mostly by young adults who usually have limited financial resources. Moreover, this audience aims at visiting several different places in a same itinerary. In order to optimize the travel schedule, they must specify their itineraries, with days of stay that may vary depending on the destination. The rise of low cost airline companies allowed the passengers who consider air transportation as the major mode of transport between destinations due to its rapid displacement. These companies offer low fares by not offering some usual standard procedures, like the onboard services. Along the years go, air transportation, mainly because of these low cost companies, has become one of the main options amongst the backpackers, those travelers who practice the backpacking. In spite of the benefits and great interest of the users, we can only find one planning system in the literature that is effective in defining and optimizing air routes, when considering the best conditions of ticket fares, that may vary depending on several external factors. Several web services were created in the last few years to support the travel planning, attesting the strengthening of the independent tourism. This Dissertation approaches the problem of planning of air routes, here named Traveling Backpacker Problem (TBP). Two new integer programs are here proposed. The first one, result of the improvement of an existent formulation, a flow-based, and the second, a graph-based modeling. According to the experiments performed using real data, the second formulation presented better results when compared to the flow-based modeling. The results showed that the graph-based modeling had a lower computational time for all the tested instances in comparison to the flow-based. As the instances got harder, e.g., by including more destinations in the route, it was no longer possible to solve the exact problem employing an optimization solver. In some cases they can find a feasible solution, however, after 3 hours of execution. The computational cost had a major impact on the results. Meta-heuristics then are proposed. As a result of the experiments, they can find feasible solutions within a few seconds for a number of hard instances.
O Mochilão é uma prática de viagem adotada por alguns viajantes, em sua maioria, jovens, que dispõem de pouco recurso financeiro e que desejam visitar um grande número de lugares em um mesmo roteiro de viagem. Para um melhor planejamento, os viajantes devem estabelecer seus roteiros, com tempos de estadias que podem ser diferentes em cada destino. O surgimento de empresas aéreas de baixo custo têm auxiliado positivamente os passageiros que consideram o transporte aéreo como meio principal de translado entre destinos devido à sua agilidade de deslocamento. Essas empresas oferecem baixas tarifas nas suas passagens, eliminando alguns serviços de empresas aéreas tradicionais, como, por exemplo, o serviço de bordo. Com os anos, o transporte aéreo, principalmente devido a essas empresas de baixo custo, tem sido alvo de interesse dos mochileiros, usuários que praticam o mochilão. Apesar dessas facilidades e do grande interesse por diversos usuários, foi encontrado na literatura apenas um sistema de planejamento mais efetivo para definir rotas aéreas de menor custo, tendo em vista as condições dos preços das passagens aéreas, que oscilam dependendo de diversos fatores. Entretanto, muitos serviços web foram criados nos últimos anos para auxiliar neste planejamento, demonstrando o fortalecimento do setor de turismo independente. Nesta Dissertação, aborda-se esse problema de planejamento de rotas, aqui denominado de Problema do Caixeiro Viajante Mochileiro (Traveling Backpacker Problem ou TBP). São introduzidas duas novas formulações de programação inteira, uma resultado do melhoramento de formulação anterior baseada em fluxo e outra baseada na modelagem do problema em grafos. De acordo com os experimentos realizados com instâncias reais, o segundo modelo, baseado em grafos, apresentou melhores resultados se comparados aos do modelo baseado em fluxo. Para todas as instâncias testadas, o tempo computacional do modelo em grafos foi bem inferior em relação ao modelo de fluxo. À medida que as instâncias ficam mais difíceis, ou seja, com mais destinos, resolver de forma exata com um pacote de otimização se tornou inviável, principalmente devido ao alto custo computacional. Meta-heurísticas foram propostas e as mesmas atingem resultados factíveis em dezenas de segundos para a maioria das instâncias difíceis cujos modelos, quando possível, são capazes de encontrar soluções viáveis com valor de gap relativamente altos após 3 horas de execução.
O Mochilão é uma prática de viagem adotada por alguns viajantes, em sua maioria, jovens, que dispõem de pouco recurso financeiro e que desejam visitar um grande número de lugares em um mesmo roteiro de viagem. Para um melhor planejamento, os viajantes devem estabelecer seus roteiros, com tempos de estadias que podem ser diferentes em cada destino. O surgimento de empresas aéreas de baixo custo têm auxiliado positivamente os passageiros que consideram o transporte aéreo como meio principal de translado entre destinos devido à sua agilidade de deslocamento. Essas empresas oferecem baixas tarifas nas suas passagens, eliminando alguns serviços de empresas aéreas tradicionais, como, por exemplo, o serviço de bordo. Com os anos, o transporte aéreo, principalmente devido a essas empresas de baixo custo, tem sido alvo de interesse dos mochileiros, usuários que praticam o mochilão. Apesar dessas facilidades e do grande interesse por diversos usuários, foi encontrado na literatura apenas um sistema de planejamento mais efetivo para definir rotas aéreas de menor custo, tendo em vista as condições dos preços das passagens aéreas, que oscilam dependendo de diversos fatores. Entretanto, muitos serviços web foram criados nos últimos anos para auxiliar neste planejamento, demonstrando o fortalecimento do setor de turismo independente. Nesta Dissertação, aborda-se esse problema de planejamento de rotas, aqui denominado de Problema do Caixeiro Viajante Mochileiro (Traveling Backpacker Problem ou TBP). São introduzidas duas novas formulações de programação inteira, uma resultado do melhoramento de formulação anterior baseada em fluxo e outra baseada na modelagem do problema em grafos. De acordo com os experimentos realizados com instâncias reais, o segundo modelo, baseado em grafos, apresentou melhores resultados se comparados aos do modelo baseado em fluxo. Para todas as instâncias testadas, o tempo computacional do modelo em grafos foi bem inferior em relação ao modelo de fluxo. À medida que as instâncias ficam mais difíceis, ou seja, com mais destinos, resolver de forma exata com um pacote de otimização se tornou inviável, principalmente devido ao alto custo computacional. Meta-heurísticas foram propostas e as mesmas atingem resultados factíveis em dezenas de segundos para a maioria das instâncias difíceis cujos modelos, quando possível, são capazes de encontrar soluções viáveis com valor de gap relativamente altos após 3 horas de execução.
Descrição
Citação
NAKAMURA, Katia Yoshime. Problema do caixeiro viajante mochileiro: formulações e métodos de soluções. 2015. Dissertação (Mestrado) - Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo (UNIFESP), São José dos Campos, 2015.