Hyper-Heuristics for the Time-Dependent ATSP Variants Applied to Air Travel
Autores
|
7362 |
3204,330,257
|
|
|
7363 |
3204,330,257
|
|
|
7364 |
3204,330,257
|
Informações:
Publicações do PESC
Hiper-heurística é um método de busca, que pode incluir um mecanismo de aprendizado, para selecionar ou gerar heurísticas de baixo nível para resolver problemas computacionais difíceis. Uma particularidade deste método é que ele opera em um espaço de busca de heurísticas ao invés de diretamente no espaço de busca de soluções. É parcialmente motivado pela ideia de desenvolver uma metodologia de busca mais geral que não exija muito conhecimento prévio sobre o problema específico e suas instâncias.
Este trabalho explora o uso da Hiper-heurística perturbativa de seleção em duas variantes do problema do Caixeiro-Viajante Assimétrico Dependente do Tempo no contexto de viagens aéreas. Na primeira, heurísticas utilizadas em algoritmos de busca local apresentados na literatura são incorporadas à hiper-heurística para mostrar sua eficiência. Na segunda, as particularidades e a dificuldade do problema impactaram o desempenho da Hiper-heurística simples e sua hibridização com o Simulated Annealing, levando a propostas de modificação do método. Um critério de aceitação adaptado do “melhor ou igual” e a adição de Path Relinking mostraram-se capazes de gerar soluções de boa qualidade.
Duas soluções iniciais foram geradas para cada instância a partir de diferentes heurísticas construtivas com comportamento complementar e várias estratégias de seleção de heurísticas de baixo nível foram implementadas, como Simple Random, Random Descendent, Random Permutation e Reinforcement Learning. Melhores custos foram encontrados na maioria das instâncias para ambos os problemas em pelo menos uma das estratégias de seleção da hiper-heurística quando comparado a outros métodos da literatura.
Hyper-heuristic is a search method, that may include a learning mechanism, for selecting or generating low level heuristics to solve computational hard problems. A particularity of this method is that it operates on a search space of heuristics instead of directly on the search space of solutions. It is partially motivated by the idea of developing a more generally applicable search methodology that does not require much prior knowledge about the specific problem and its instances.
This work explore the use of the selection perturbative Hyper-heuristic framework in two Time-dependent Asymmetric Traveling Salesman problem variants in the context of air travel. In the first, heuristics used in local search algorithms presented in the literature are embedded into the hyper-heuristic framework to show its efficiency. In the second, particularities and the difficulty of the problem impacted the performance of the simple Hyper-heuristic and its hybridization with Simulated Annealing, leading to proposals for modifying the method. An adapted acceptance criterion of the “improve or equal” and the addition of Path Relinking proved capable of generating good quality solutions.
Two initial solutions were generated for each instance from different constructive heuristics with complementary behavior and several low level heuristic selection strategies were implemented, such as Simple Random, Random Descendent, Random Permutation and Reinforcement Learning. Better solution costs were found in most of the instances for both problems in at least one of the hyper-heuristic selection strategies when compared to other methods in the literature.