Spatial Transformation of Equality - Generalized Travelling Salesman Problem to Travelling Salesman Problem

Zıa M., Cakir Z., Şeker D. Z.

ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION, vol.7, 2018 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 7
  • Publication Date: 2018
  • Doi Number: 10.3390/ijgi7030115
  • Journal Name: ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Keywords: generalized travelling salesman problem, shortest route, combinatorial optimization, OpenStreetMap, EFFICIENT TRANSFORMATION, N-SETS, ALGORITHM, NODES
  • Istanbul Technical University Affiliated: Yes

Abstract

The Equality-Generalized Travelling Salesman Problem (E-GTSP), which is an extension of the Travelling Salesman Problem (TSP), is stated as follows: given groups of points within a city, like banks, supermarkets, etc., find a minimum cost Hamiltonian cycle that visits each group exactly once. It can model many real-life combinatorial optimization scenarios more efficiently than TSP. This study presents five spatially driven search-algorithms for possible transformation of E-GTSP to TSP by considering the spatial spread of points in a given urban city. Presented algorithms are tested over 15 different cities, classified by their street-network's fractal-dimension. Obtained results denote that the R-Search algorithm, which selects the points from each group based on their radial separation with respect to the start-end point, is the best search criterion for any E-GTSP to TSP conversion modelled for a city street network. An 8.8% length error has been reported for this algorithm.