The hiking tourist problem

Hiking is among the most popular outdoor activities. In this paper, we introduce the hiking tourist problem (HTP) to support hikers in their trip planning to attractive hiking spots in a certain region. In the HTP, a set of hikes out of a larger set of potential hikes is selected and the mode of transport between the hiking locations is determined. The considered constraints involve a minimum and a maximum number of travel days, a maximum total cumulative elevation gain of all selected hikes and a maximum number of hikes. Two objectives are optimized concurrently: the total attractiveness of the travel plan is maximized and its total emissions are minimized. Several families of valid inequalities are discussed and a bi-objective branch-and-bound algorithm is tailored to solve the proposed problem. In a computational study on realistic instances for different regions in France, the impact of the proposed valid inequalities is analyzed and the trade-off between attractiveness and emissions is discussed.