Traveling Backpacker Problem with priorities: mono-objective and multi-objective formulations
Data
2023-04-28
Autores
Costa, Calvin Rodrigues da 
Tipo
Tese de doutorado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
The Traveling Backpacker Problem (TBP) is a combinatorial optimization problem whose goal is to define a minimum-cost route in low-cost airlines. In the TBP, a limited travel time is imposed, as well as the number of stay days associated with each destination and time-varying air ticket costs. Furthermore, the traveler must visit all predefined locations and a length of stay at each destination. The cost to move from one specific location to another varies according to the moment the travel occurs. The literature on the TBP is still scarce and lacks investigation in considering new particularities of the application and heuristic methods. In line with this, the contributions of this Ph.D. thesis are: (i) a heuristic method for the TBP; (ii) the investigation of the TBP in scenarios where the traveler has a limited budget and subjective scores linked to the destinations of interest. In the second contribution, we approach the problem of deciding, besides the route, which places to visit considering the involved costs, preferences, and other constraints (available air tickets and the number of stay days, for example). For such, first, we present a study on the Prize Collecting Traveling Backpacker Problem (PCTBP). In the PCTBP, prizes are assigned to the places according to the user's preferences for the destinations. Two PCTBP models were introduced: (i) one that minimizes the air ticket costs plus the penalties for unvisited destinations (PCTBP-I); (ii) another that maximizes the prizes associated with the destinations but limits the budget according to a predefined value (PCTBP-II). To evaluate the first problem an exact solver to solve several diverse real instances was considered. The results of this experiment indicated that, depending on how the user assigns the prizes, the pattern of the routes differs significantly. Based on our observations of the PCTBP, we also propose the bi-objective PCTBP (BO-PCTBP). The goal of BO-PCTBP is to maximize priorities while minimizing air ticket costs. To solve this problem, two adaptations of the evolutionary multi-objective optimization algorithm, Nondominated Sorting Genetic Algorithm II (NSGA-II), were presented. Furthermore, we introduced a new set of instances based on real-world data and conducted experiments using both the instances used in the PCTBP experiments. The results suggest that the proposed NSGA-II obtains, in general, a diversified approximate Pareto frontier. To further improve the results, however, a more robust parameter tuning is needed as indicated by the analysis of the results.