Spatial transformation of equality - Generalized travelling salesman problem to travelling salesman problem

Mohammed Zia*, Ziyadin Cakir, Dursun Zafer Seker

*Bu çalışma için yazışmadan sorumlu yazar

Araştırma sonucu: ???type-name???Makalebilirkişi

8 Atıf (Scopus)

Ö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.

Orijinal dilİngilizce
Makale numarası115
DergiISPRS International Journal of Geo-Information
Hacim7
Basın numarası3
DOI'lar
Yayın durumuYayınlandı - Mar 2018

Bibliyografik not

Publisher Copyright:
© 2018 by the authors.

Finansman

Acknowledgments: The research presented in this article is primarily funded by The Scientific and Technological Research Council of Turkey under 2215—Graduate Scholarship Programme for International Students (TUBITAK, URL: https://www.tubitak.gov.tr/en). The authors would also like to thank the National Innovation and Research and Innovation Center for Geographical Information Technologies for additional support.

FinansörlerFinansör numarası
National Innovation and Research and Innovation Center for Geographical Information Technologies
Scientific and Technological Research Council of Turkey2215
TUBITAK

    Parmak izi

    Spatial transformation of equality - Generalized travelling salesman problem to travelling salesman problem' araştırma başlıklarına git. Birlikte benzersiz bir parmak izi oluştururlar.

    Alıntı Yap