| Full text | |
| Author(s): |
Nakamura, Katia Y.
[1]
;
Coelho, Leandro C.
[2, 3]
;
Renaud, Jacques
[2, 3]
;
Nascimento, Maria C. V.
[1]
Total Authors: 4
|
| Affiliation: | [1] Univ Fed Sao Paulo, Inst Sci & Technol, Sao Paulo - Brazil
[2] Univ Laval, Fac Sci Adm, Quebec City, PQ - Canada
[3] CIRRELT, Quebec City, PQ - Canada
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | Journal of the Operational Research Society; v. 69, n. 1, p. 108-114, 2018. |
| Web of Science Citations: | 0 |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 15/21660-4 - Hibridizing heuristic and exact methods to approach combinatorial optimization problems |
| Grantee: | Mariá Cristina Vasconcelos Nascimento Rosset |
| Support Opportunities: | Regular Research Grants |