Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/9489
Tipo: Dissertação
Título: Single-objective and bi-objetive parallel heuristics for the travel planning problem
Heurísticas paralelas para o problema de planejamento de viagens mono- objetivo e bi-objetivo
Autor(es): Beirigo, Breno Alves
Abstract: In this study we apply single-objective and bi-objective parallel heuristics to solve broad and realistic formulations of the travel planning problem. Given a travel time window and a set of destinations with their corresponding dwelling times, the goal of our single-objective approach is to find a route that produces a budget travel’s itinerary, involving flights, hotels and departure/arrival times. In turn, our bi-objective approach adds a complexity level in the problem’s formulation once we are seeking for a Pareto set of detailed travel itineraries, which are both cost and time efficient. When the sequence of cities is fixed, the single-objective version of the problem is commonly modeled in literature as a time-dependent network and the best itinerary is computed using shortest path algorithms. However, in this study, finding the order of cities that minimizes the total cost, and besides that, a set of good trade-off solutions, are also goals. Therefore, our single-objective formulation stands for a TDSPP (Time Dependent Shortest Path Problem) embedded in the TSP (Travel Salesman Problem) whereas our bi-objective formulation stands for a TDSPP embedded in a bi-objective TSP. On the first formulation we apply an ILS (Iterated Local Search) heuristic and on the second formulation we apply the NSGA-II (Nondominated Sorting Genetic Algorithm II) framework. For performance assessing, the results of both heuristics were compared to the results of corresponding exact methods with no time constraints. All test cases simulate realistic travel itineraries and run upon real-world travel data collected in advance, besides having to comply with an execution threshold of approximately 1 minute. For 285 single-objective test cases, our ILS heuristic was able to reach solutions in average less than 4.1% divergent from an exact implementation, besides reaching the optimal solution in about 30% of the test cases. In turn, for 180 bi-objective test cases, our NSGA-II implementation was able to reach an approximated solution in average up to 8% divergent from an exact implementation.
Nesse trabalho são aplicadas heurísticas paralelas mono-objetivas e bi-objetivas para solucionar formulações abrangentes e realistas do problema de planejamento de viagens. Dado o intervalo de tempo que uma viagem pode ocorrer e um conjunto de destinos com seus respectivos tempos de permanência, a abordagem mono-objetiva procura determinar um itinerário de baixo custo que compreenda voos, hotéis e horários de partida/chegada. Por sua vez, a abordagem bi-objetiva adiciona complexidade a formulação do problema, uma vez que pretende determinar o conjunto Pareto de itinerários de viagem capazes de equilibrar custo e tempo. Quando a sequência de cidades é fixa, a versão mono-objetiva do problema é comumente modelada na literatura como uma rede dependente do tempo e o melhor itinerário é calculado usando algoritmos de caminho míınimo. Contudo, nesse trabalho, determinar a ordem de visitação das cidades também é um objetivo. Portanto, a formulação mono-objetiva proposta representa um TDSPP (Time Dependent Shortest Path Problem) incorporado ao TSP (Travel Salesman Problem) e a formulação bi-objetiva representa um TDSPP incorporado em um TSP bi-objetivo. Na primeira formulação foi aplicada a heurística ILS (Iterated Local Search) e na segunda formulação o framework NSGA-II (Nondominated Sorting Genetic Algorithm II). Os resultados de ambas as heurísticas foram comparados com os resultados produzidos por métodos exatos executados sem restrições temporais. Todos os casos de teste simulam itinerários de viagem realistas e foram executados em um banco de dados de viagens e hospedagens coletadas com antecedência. Além disso, independentemente da abordagem utilizada, estabeleceu-se que o tempo de execução de cada caso deve ser de aproximadamente 1 minuto. A heurística ILS proposta para a versão mono-objetiva do problema foi executada em 285 instâncias e alcançou, em média, soluçõoes no máximo 4.1% divergentes de uma implementa ̧ao exata, além de atingir a melhor solução em cerca de 30% dos casos de teste. Por sua vez, o framework NSGA-II foi capaz de produzir soluções no máximo 8% divergentes da implementação exata para 180 instâncias.
Palavras-chave: Pesquisa operacional
Otimização combinatória
Solução de problemas
Heurística
CNPq: Ciência da Computação
Editor: Universidade Federal de Viçosa
Citação: BEIRIGO, Breno Alves. Single-objective and bi-objetive parallel heuristics for the travel planning problem. 2016. 92f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2016.
Tipo de Acesso: Acesso Aberto
URI: http://www.locus.ufv.br/handle/123456789/9489
Data do documento: 21-Set-2016
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdftexto completo2,67 MBAdobe PDFThumbnail
Visualizar/Abrir


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