The Traveling Backpacker Problem: A computational comparison of two formulations
研究了背包客旅行问题，提出基于网络流的建模方法，并与传统路径规划模型比较，发现新模型在求解现实规模实例时更高效、解质量更高。
The rise of low-cost airlines has influenced the tourism industry, particularly in trips known as backpacking. This form of travelling is mostly adopted by people on a tight budget, intending to visit a large number of touristic attractions. In the Travelling Backpacker Problem (TBP), the objective is to find the best sequence of visits, so as to minimise the total travel cost. This problem was first modelled as a routing problem. Nevertheless, for small-sized instances, an exact solver could not find any feasible solutions. In this paper, we propose a new formulation for the TBP, which is based on a network flow representation of the problem. We tested both models using a state-of-the-art MIP solver on instances generated from real data obtained from low-cost airlines. Computational experiments indicate that the network flow-based formulation outperforms the routing-based formulation and can yield high-quality solutions for instances of realistic size.