Traveling Backpacker Problem with priorities: mono-objective and multi-objective formulations

The Traveling Backpacker Problem (TBP) is an optimization problem that seeks to find the least cost route for a backpacker using low-cost airlines. The backpacker has limited travel time, specific length of stay at each destination, and variable airfare costs. There are few studies on TBP, especially on heuristic methods and the balance between cost and sites visited. This doctoral thesis contributes by proposing metaheuristics for TBP and new scenarios considering limited budget and classification of destinations by traveler preference. Based on these scenarios, the Prize Collecting Traveling Backpacker Problem (PCTBP) is presented in two models, which provide different route patterns in experiments. The Bi-objective PCTBP (BO-PCTBP) is proposed to minimize costs and maximize prize collection. New instances are proposed and experiments using  NSGA-II metaheuristics have shown a diverse Pareto frontier in tests with real data.