The traveling backpacker problem : a computational comparison of two formulations

Authors: Nakamura, Katia Y.; Coelho, Leandro CallegariRenaud, Jacques; Nascimento, Mariá C. V.
Abstract: The rise of low-cost airlines has influenced the tourism industry, particularly in trips known as backpacking. This form of traveling is mostly adopted by people on a tight budget, intending to visit a large number of touristic attractions. In the Traveling Backpacker Problem (TBP), the objective is to find the best sequence of visits, so as to minimize the total travel cost. This problem was first modeled 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.
Document Type: Article de recherche
Issue Date: 10 March 2017
Open Access Date: Restricted access
Document version: VoR
Permalink: http://hdl.handle.net/20.500.11794/13713
This document was published in: Journal of the Operational Research Society, (2017)
https://doi.org/10.1057/s41274-017-0205-8
Springer
Alternative version: 10.1057/s41274-017-0205-8
Collection:Articles publiés dans des revues avec comité de lecture

Files in this item:
SizeFormat 
paper_JORS final Accepte.pdf
267.95 kBAdobe PDF    Request a copy
All documents in CorpusUL are protected by Copyright Act of Canada.