Tourist Route Optimisation in Melaka and Penang Using Nearest Neighbour and GRASP Algorithms

Abstract

Efficient tourist route planning is crucial for enhancing travel experience and mobility in heritage cities. However, tourists often face difficulties in determining an optimal visiting sequence for multiple attractions which results in inefficient travel routes and increased travel distance. This research proposes a graph-based route optimisation framework for tourist attractions in Melaka and Penang, Malaysia by using the Nearest Neighbour and GRASP algorithms. Major attractions are modelled as nodes while travel distances obtained from the Google Maps Distance Matrix API are represented as weighted edges. Two heuristic approaches, which are the Nearest Neighbour (NN) algorithm and the Greedy Randomised Adaptive Search Procedure (GRASP), are implemented and compared in terms of total travel distance and computation time. Empirical results show that NN produces solutions with negligible computation time but longer routes. In contrast, GRASP consistently yields shorter routes with an average improvement of approximately 6.00–7.00% at an acceptable higher computational effort. The findings demonstrate that GRASP is more suitable for practical tourism route optimisation, where solution quality is prioritised. Future work may incorporate real-time traffic conditions, individual tourist preferences, and dynamic environmental factors further to enhance the practicality and adaptability of the proposed approach.