The Traveling Backpacker Problem: A computational comparison of two formulations

Kátia Y. Nakamura, Leandro C. Coelho, Jacques Renaud and Mariá C. V. Nascimento

Journal of the Operational Research Society, 2018, vol. 69, issue 1, 108-114

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.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1057/s41274-017-0205-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:69:y:2018:i:1:p:108-114

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1057/s41274-017-0205-8

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().