Intelligent-Guided Adaptive Search For The Traveling Backpacker Problem

The solution of combinatorial problems has been largely performed by heuristics for their ability to obtain good solutions faster than exact methods. In this paper, we propose heuristic methods to approach a hard-to-solve combinatorial optimization problem. The target routing problem is the recently proposed Traveling Backpacker Problem (TBP), which has not been investigated by a heuristic method yet. The difficulty in constructing feasible solutions for such a problem drove us to approach the TBP by a metaheuristic with a learning stage in the search, the Intelligent Greedy Adaptive Search (IGAS). To validate the introduced solution methods, they were compared to the exact solution obtained by CPLEX. Besides, we analyze isolate parts of the methods to infer about the performance of the construction of the solution and the local search, the main phases of IGAS. The results of computational experiments show that IGAS outperformed the other introduced methods in small-sized and medium-sized instances, being competitive in larger instances. Moreover, IGAS presented reasonable gaps to the solutions obtained by the exact commercial solver.