An Analysis of Travelling Salesman Problem Utilizing Hill Climbing Algorithm for a Smart City Touristic Search on OpenStreetMap (OSM)


Ozcan S. C. , Kaya H.

2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), Kizilcahamam, Türkiye, 19 - 21 Ekim 2018, ss.729-733 identifier identifier

  • Doi Numarası: 10.1109/ismsit.2018.8567045
  • Basıldığı Şehir: Kizilcahamam
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.729-733

Özet

Travelling Salesman Problem (TSP) can be applied to find the most efficient route to travel between various nodes. The goal is to make smart cities to be created by heuristic algorithms on the real maps to perform some tasks through TSP. Therefore, Hill Climbing heuristic search algorithm which is generally used for mathematical optimization problems in Artificial Intelligence (AI) field has been preferred in this study. This application takes a city from the OpenStreetMap (OSM), which is a real map as an input given to the algorithm, and calculates a path to visit all the nodes on the related route. The output was intended to be found in the shortest possible way and in the least possible time. On the market, there are some travelling, public transport and discovery applications or games on the smart maps. Also there are some publications about TSP and meta-heuristic approaches in the literature but the sources are generally commercial products and for limited cities. There is no application that takes all the cities as a source and makes a travel plan for tourists. This study intended to create an open-source, location independent travel plan advisor and develop an indigenous product. Application was tested for Rome and Ankara as an instance but because a flexible working area OSM was used, application can be generated for all the routes and also various applications can be developed by researchers based on this study.