Greedy Heuristic Algorithms for Multi-Objective Tourist Trip Design Problem on Penang Island

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.