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, cilt.7, 2018 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 7
  • Basım Tarihi: 2018
  • Doi Numarası: 10.3390/ijgi7030115
  • Dergi Adı: ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION

Özet

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.