Open Access Open Access  Restricted Access Subscription or Fee Access

A New Combinatorial Algorithm for Effective Itinerary Planning

A. Ambeth Raja, K. Nirmala


Selecting and creating an efficient and optimal trip plan is the most aggravating job and a knapsack problem. Although existing recommender systems can provide some predefined travel packages, they are not customized for each specific customer according to their POI. Past endeavors address the issue by giving an automatic travel planning service which sorts out the points-of-interests (POIs) into a modified travel package. Using this customized recommender system which is elaborated as a hybrid model, the user can get optimal package based on the points selected by them. To address the above limitations, the system provides a hybrid recommendation system with rank based recommender model with the use of self organizing feature maps. The current proposal provides an automatic itinerary suggestion and generation service for the backpack travelers, which results in the knapsack problem. The proposed service creates a customized and effective multiday itinerary based on the user’s POI. This handles the famous NP-complete problem, and optimal service selection problem. To obtain the optimal solution, a two-stage scheme is adopted which happened to be SOM and tabu search. This paper proposed genetic algorithm based recommendation, which helps to select optimal package based on the customized POI and attribute given by the user. This greatly improves the searching and filtering performance by leveraging the genetic algorithm. Genetic algorithms remain in the wider class of evolutionary algorithms (EA), which helps to create solutions to optimization problems using techniques inspired by natural evolution.


Genetic Algorithm; Tabu Search; Itinerary Planning; Tsp; Combinatorial Optimized Package Evocation.

Full Text:



Applegate, D. L., Bixby, R. E., Chvatal, V., & Cook, W. J. (2011). The traveling salesman problem: a computational study. Princeton University Press.

Liao, Y. F., Yau, D. H., & Chen, C. L. (2012). Evolutionary algorithm to traveling salesman problems. Computers & Mathematics with Applications, 64(5), 788-797.

Yang, R. (1997). Solving large travelling salesman problems with small populations.

Moon, C., Kim, J., Choi, G., & Seo, Y. (2002). An efficient genetic algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research, 140(3), 606-617.

Snyder, L. V., & Daskin, M. S. (2006). A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, 174(1), 38-53.

Penev, M. K. V. S. S. (2005). Genetic operators crossover and mutation in solving the TSP problem. In International Conference on Computer Systems and Technologies.

Ding, C., Cheng, Y., & He, M. (2007). Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Science & Technology, 12(4), 459-465.

Al-Dulaimi, B. F., & Ali, H. A. (2008). Enhanced traveling salesman problem solving by genetic algorithm technique (TSPGA). World Academy of Science, Engineering and Technology, 38, 296-302.

Chen, G., Wu, S., Zhou, J., & Tung, A. K. (2014). Automatic itinerary planning for traveling services. Knowledge and Data Engineering, IEEE Transactions on,26(3), 514-527.

Basu Roy, S., Das, G., Amer-Yahia, S., & Yu, C. (2011, April). Interactive itinerary planning. In Data Engineering (ICDE), 2011 IEEE 27th International Conference on (pp. 15-26). IEEE.

Saranya, B., & Venkatesh, M. Customized Travel Itinerary Mining for Tourism Services.

Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. (2014). Mobile recommender systems in tourism. Journal of Network and Computer Applications, 39, 319-333.

Adomavicius, G., & Tuzhilin, A. (2005). Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. Knowledge and Data Engineering, IEEE Transactions on, 17(6), 734-749.

Tam, H., & Pun-Cheng, L. S. C. (2012). Evaluation of Online Itinerary Planner and Investigation of Possible Enhancement Features. In Advances in Spatial Data Handling and GIS (pp. 195-210). Springer Berlin Heidelberg.

Jain, N., & Sharma, V. Distance Weight Optimization of Association Rule Mining with Improved Genetic Algorithm.

Kuo, R. J., Chao, C. M., & Chiu, Y. T. (2011). Application of particle swarm optimization to association rule mining. Applied Soft Computing, 11(1), 326-336

Bajpai, P., & Kumar, M. (2010). Genetic algorithm–an approach to solve global optimization problems. Indian Journal of computer science and engineering,1(3), 199-206.

Haldulakar, R., & Agrawal, J. (2011). Optimization of Association Rule Mining through Genetic Algorithm. International Journal on Computer Science and Engineering (IJCSE) Vol, 3.

Sivaraj, R., & Ravichandran, D. T. (2011). An Efficient Grouping Genetic Algorithm. International Journal of Computer Applications, 21(7), 38-42.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.