Abstract
Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Archetti, C., Hertz, A., & Speranza, M. (2007). Metaheuristics for the team orienteering problem. Journal of Heuristics, 13, 49–76.
Buhalis, D. (2003). eTourism: information technology for strategic tourism management. London: Prentice Hall.
Buhalis, D., & Law, R. (2008). Twenty years on and 10 years after the internet: the state of eTourism research. Tourism Management, 29(4), 609–623.
Chao, I., Golden, B., & Wasil, E. (1996). The team orienteering problem. European Journal of Operational Research, 88, 464–474.
Fesenmainer, D. R., Ricci, F., Schaumlechner, E., Wober, K., & Zanella, C. (2003). DIETORECS: travel advisory for multiple decision styles. In Information and communication technologies in tourism (pp. 232–241). New York: Springer.
Hannes, W. (2003). Intelligent system in travel and tourism. In Proceedings of international joint conference on artificial intelligence 2003.
Ke, L., Archetti, C., & Feng, Z. (2008). Ants can solve the team orienteering problem. Computers & Industrial Engineering, 54, 648–665.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44, 2245–2269.
Or, I. (1976). Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. Ph.D. thesis, Department of industrial engineering and management science, Northwest University, Evanston, IL.
Potvin, J. Y., Kervahut, T., & Rousseau, J. M. (1996). The vehicle routing problem with time windows part I: tabu search. INFORMS Journal on Computing, 8(2), 158–164.
Potvin, J. Y., & Rousseau, J. M. (1995). An exchange heuristic for routing problems with time windows. Journal of Operational Research Society, 46, 1433–1446.
Ricci, F. (2002). Travel recommender systems. IEEE Intelligent Systems, 17(6), 55–57.
Ricci, F., & Wether, H. (2002). Case base querying for travel planning recommendation. Information Technology & Tourism, 4(3–4), 215–226.
Schafer, J. B., Konstan, J., & Riedi, J. (1999). Recommender Systems in e-commerce. In Proceedings of the 1st acm conference on Electronic commerce 1999.
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2008). A greedy randomized adaptive search procedure for the team orienteering problem. In Proceedings of EU/Meeting 2008, France, 23–24 October 2008.
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009). A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research, 196(1), 118–127.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported in part by a grant from IBM China Research Laboratory, by the National Natural Science Foundation of China under Grant NSFC No. 70832002 and 70771028, and by the Shanghai Science and Technology PuJiang Funds under Grant 09PJ1401500. The authors would like to thank two anonymous reviewers for their comments and suggestions.
Rights and permissions
About this article
Cite this article
Zhu, C., Hu, J.Q., Wang, F. et al. On the tour planning problem. Ann Oper Res 192, 67–86 (2012). https://doi.org/10.1007/s10479-010-0763-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-010-0763-5