Greedy heuristic algorithms for multi-objective tourist trip design problem on Penang Island

Tze Yuan Louis Lim; Aida Mauziah Benjamin

doi:10.32890/jcia2025.4.2.8

Authors

Tze Yuan Louis Lim Universiti Utara Malaysia, Malaysia
Aida Mauziah Benjamin Universiti Utara Malaysia, Malaysia

DOI:

https://doi.org/10.32890/jcia2025.4.2.8

Keywords:

nearest greedy insertion, nearest neighbour, Penang Island, tourist trip design problem

Abstract

Tourism is a vital sector in the global economy, significantly contributing to the development of many countries by creating jobs, generating income, and promoting cultural exchange. However, planning a tour itinerary presents a significant challenge due to the necessity of identifying points of interest (POI) and organizing them into a proper itinerary. This study focused on solving the multi-objective TTDP for Penang Island by developing two greedy heuristic techniques: Nearest Neighbour (NN) and Nearest Greedy Insertion (NGI). The study aimed to achieve three objectives: identifying tourists’ preferences and constraints relevant to the TTDP, proposing solutions using NN and NGI techniques, and evaluating the effectiveness of these methods. Adopted a hybrid weighted objective, both algorithms balanced maximizing the number of POIs visited and popularity index while satisfying several constraints such as time windows, popularity index, restaurant selection, POI categories, and budget limitations. The findings showed that the NN technique performed better for a one-day tour, delivering a higher popularity index (212.66) compared to NGI (171.43). However, the NGI technique outperformed in a two-day tour by balancing POI coverage and popularity index of 294.91, while NN had 268.68. For a three-day tour, NN achieved a higher popularity index (359.86) than NGI (337.03), while NGI visited more POIs. Future studies should explore metaheuristic methods, broader geographic applications, incorporate time-dependent variables, and tailored solutions for halal-conscious travellers.

References

Ab Dulhamid, H., Isa, M. I., Mohamed, B., & Sazali, M. F. (2022). Motivational factors in influencing the international tourists travel to tourism attractions in Penang. Planning Malaysia, 20(1), 13–24. https://doi.org/10.21837/pm.v20i20.1075

Benjamin, A. M., Abdullah, A. S., Abdul-Rahman, S., Nazri, E. M., & Yahaya, H. Z. (2019). Developing a comprehensive tour package using an improved greedy algorithm with tourist preferences. Journal of Sustainability Science and Management, 14(4), 93–104.

Choachaicharoenkul, S., Coit, D., & Wattanapongsakorn, N. (2022). Multi-objective trip planning with solution ranking based on user preference and restaurant selection. IEEE Access, 10, 10688–10705. https://doi.org/10.1109/ACCESS.2022.3144883

Divsalar, A., Jandaghi, H., & Emami, S. (2019). A multi-day tourist trip planning with multiple time windows and multiple levels of service. International Journal of Industrial Engineering and Management Science, 6(1), 98–107.

Divsalar, G., Divsalar, A., Jabbarzadeh, A., & Sahebi, H. (2021). An optimization approach for green tourist trip design. Soft Computing, 26(9), 4303–4332. https://doi.org/10.1007/s00500-021-06518-2

Du, J., Zhou, J., Li, X., Li, L., & Guo, A. (2021). Integrated self-driving travel scheme planning. International Journal of Production Economics, 232, 107936. https://doi.org/10.1016/j.ijpe.2020.107936

Expósito, A., Mancini, S., Brito, J., & Moreno, J. A. (2019). A fuzzy GRASP for the tourist trip design with clustered POIs. Expert Systems with Applications, 127, 210–227. https://doi.org/10.1016/j.eswa.2019.03.011

Filho, A. A., & Morabito, R. (2024). An effective approach for bi-objective multi-period touristic itinerary planning. Expert Systems with Applications, 240, 122497. https://doi.org/10.1016/j.eswa.2023.122497

Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., & Vathis, N. (2015). Heuristics for the time dependent team orienteering problem: Application to tourist route planning. Computers & Operations Research, 62, 36–50. https://doi.org/10.1016/j.cor.2015.03.016

Google. (2024). Penang Island, Malaysia [Google Maps]. Retrieved August 14, 2024, from https://www.google.com.my/maps/

Gündling, F., & Witzel, T. (2020). Time-dependent tourist tour planning with adjustable profits. 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). https://doi.org/10.4230/OASIcs.ATMOS.2020.6

Hashim, Z., Mat Desa, W. L. H., Aziz, H. A., & Mohd Zaki, N. M. Z. (2018). Greedy method for solving the Langkawi tourist route: A case study. Journal of Technology and Operations Management, 13(1), 21–29.

Ho, J. W. (2024, April 30). Malaysia sees 32.5% more tourists in the first quarter of 2024, says Tiong. The Star. Retrieved June 15, 2024, from https://www.thestar.com.my/news/nation/2024/04/30/malaysia-sees-325-more-tourists-in-first-quarter-of-2024-says-tiong

Jriji, D., Krichen, S., & Madany, F. (2020). A memetic algorithm for the tourist trip design with clustered points of interest. In 2020 International Multi-Conference on “Organization of Knowledge and Advanced Technologies” (OCTA). IEEE. https://doi.org/10.1109/OCTA49274.2020.9151838

Kolaee, M. H., Jabbarzadeh, A., & Al-e-hashem, S. M. J. M. (2024). Sustainable group tourist trip planning: An adaptive large neighborhood search algorithm. Expert Systems with Applications, 237, 121544. https://doi.org/10.1016/j.eswa.2023.121544

Li, Z., & Hu, X. (2011). The team orienteering problem with capacity constraint and time window. The Tenth International Symposium on Operations Research and Its Applications (ISORA 2011).

Liao, Z., & Zheng, W. (2018). Using a heuristic algorithm to design a personalized day tour route in a time-dependent stochastic environment. Tourism Management, 68, 284–300. https://doi.org/10.1016/j.tourman.2018.03.021

Lim, K. H., Chan, J., Karunasekera, S., & Leckie, C. (2019). Tour recommendation and trip planning using location-based social media: A survey. Knowledge and Information Systems, 60, 1247–1275. https://doi.org/10.1007/s10115-018-1297-4

Linganathan, S., & Singamsetty, P. (2024). Genetic algorithm to the bi-objective multiple travelling salesman problem. Alexandria Engineering Journal, 90, 98–111. https://doi.org/10.1016/j.aej.2024.01.034

Ndoloe, L. A., & Rumlaklak, N. D. (2018). Application design in determining the shortest route using tabu search algorithm. International Journal of Physical Sciences and Engineering, 2(3), 77–91. https://doi.org/10.29332/ijpse.v2n3.233

Palomo-Martínez, P. J., Salazar-Aguilar, M. A., Laporte, G., & Langevin, A. (2017). A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints. Computers & Operations Research, 78, 408–419. https://doi.org/10.1016/j.cor.2016.10.007

Paulavičius, R., Stripinis, L., Sutavičiūtė, S., Kočegarov, D., & Filatovas, E. (2023). A novel greedy genetic algorithm-based personalized travel recommendation system. Expert Systems with Applications, 230, 120580. https://doi.org/10.1016/j.eswa.2023.120580

Pitakaso, R., Srichok, T., Khonjun, S., Gonwirat, S., Nanthasamroeng, N., & Boonmee, C. (2024). Multi-objective sustainability tourist trip design: An innovative approach for balancing tourists' preferences with key sustainability considerations. Journal of Cleaner Production, 449, 141755. https://doi.org/10.1016/j.jclepro.2024.141755

Rachmad, A., Syarief, M., Rochman, E. M. S., Husni, H., & Rahmatullah, G. (2022). Ant colony optimization model for determining the shortest route in Madura-Indonesia tourism places. Journal of Mathematical and Computational Science, 12, 1–18. https://doi.org/10.28919/jmcs/7027

Rahman, S. A., Benjamin, A. M., & Bakar, E. M. N. E. A. (2014). Economic tour package model using heuristic. AIP Conference Proceedings, 1605(1), 1083–1087.

Roozbeh, I., Hearne, J. W., & Pahlevani, D. (2020). A solution approach to the orienteering problem with time windows and synchronisation constraints. Heliyon, 6(6), e04130. https://doi.org/10.1016/j.heliyon.2020.e04130

Ruiz-Meza, J., Brito, J., & Montoya-Torres, J. R. (2021). Multi-objective fuzzy tourist trip design problem with heterogeneous preferences and sustainable itineraries. Sustainability, 13(17), 9758. https://doi.org/10.3390/su13179758

Ruiz-Meza, J., & Montoya-Torres, J. R. (2022). A systematic literature review for the tourist trip design problem: Extensions, solution techniques, and future research lines. Operations Research Perspectives, 9, 100228. https://doi.org/10.1016/j.orp.2022.100228

Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2013). The multiconstraint team orienteering problem with multiple time windows. Transportation Science, 47(1), 53–63. https://doi.org/10.1287/trsc.1110.0377

Themes. (2024). Discovering the diversity and natural wonders of Malaysia. Helsinki Times. Retrieved June 14, 2024, from https://www.helsinkitimes.fi/themes/themes/travel/23144-discovering-the-diversity-and-natural-wonders-of-malaysia.html

Traveloka. (2023). Unforgettable adventures await: Explore the top 17 places in Penang. Retrieved September 11, 2024, from https://www.traveloka.com/en-my/explore/destination/penang-best-place/308660

Tripadvisor. (2024). Things to do in Penang. Retrieved August 14, 2024, from https://www.tripadvisor.com/Attractions-g298302-Activities-a_allAttractions.true-Penang.html

Uwaisy, M. A., Baizal, Z. K. A., & Reditya, M. Y. (2019). Recommendation of scheduling tourism routes using tabu search method (Case study Bandung). Procedia Computer Science, 157, 150–159. https://doi.org/10.1016/j.procs.2019.08.152

Vansteenwegen, P., & Van Oudheusden, D. (2007). The mobile tourist guide: An OR opportunity. OR Insight, 20(3), 21–27. https://doi.org/10.1057/ori.2007.16

Vu, D. M., Kergosien, Y., Mendoza, J. E., & Desport, P. (2022). Branch-and-check approaches for the tourist trip design problem with rich constraints. Computers & Operations Research, 138, 105566. https://doi.org/10.1016/j.cor.2021.105566

Wanderlog. (2024). Where to eat: The 50 best restaurants in Penang Island. Retrieved August 14, 2024, from https://wanderlog.com/list/geoCategory/197635/where-to-eat-best-restaurants-in-penang-island