Ant Colony Optimization for Jakarta Historical Tours: A Comparative Analysis of GPS and Map Image Approaches

Abstract

The Traveling Salesman Problem (TSP) is a problem that represents a difficult combinatorial optimization problem starting from practical problems. The ant colony optimization (ACO) algorithm is implemented in several topics, particularly in solving combinatorial optimization problems. ACO is inspired by the behavior of ants in searching for the shortest path between a food source and their nest. In this research, ACO is used to find the best path or traveling salesman problem for museums and historical sites in Jakarta capital city of Indonesia. This research employs an approach based on the location's coordinates or latitude and longitude, while another method depends on coordinate data obtained from a supplied map image. After implementing both models, it can be concluded that the ACO model is not very good at solving TSP using actual coordinates. Meanwhile, the algorithm can quickly find near-optimal paths when using coordinates from a map image. The algorithm generates the optimal path in 11 seconds, reducing the initial distance from 17.938 to 4.430, using 4.731 ants and 75 trips with a distance power of 1. Statistical random variation was also performed, which proved that the algorithm is flexible and reliable when tested under various conditions.

Keywords

• ant colony optimization
• historical sites
• intelligent system
• tour planning
• traveling salesman problem