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

Mohammed Zia*, Ziyadin Cakir, Dursun Zafer Seker

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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.

Original languageEnglish
Article number115
JournalISPRS International Journal of Geo-Information
Volume7
Issue number3
DOIs
Publication statusPublished - Mar 2018

Bibliographical note

Publisher Copyright:
© 2018 by the authors.

Funding

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.

FundersFunder number
National Innovation and Research and Innovation Center for Geographical Information Technologies
Scientific and Technological Research Council of Turkey2215
TUBITAK

    Keywords

    • Combinatorial optimization
    • Generalized travelling salesman problem
    • OpenStreetMap
    • Shortest route

    Fingerprint

    Dive into the research topics of 'Spatial transformation of equality - Generalized travelling salesman problem to travelling salesman problem'. Together they form a unique fingerprint.

    Cite this