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 language | English |
---|---|
Article number | 115 |
Journal | ISPRS International Journal of Geo-Information |
Volume | 7 |
Issue number | 3 |
DOIs | |
Publication status | Published - 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.
Funders | Funder number |
---|---|
National Innovation and Research and Innovation Center for Geographical Information Technologies | |
Scientific and Technological Research Council of Turkey | 2215 |
TUBITAK |
Keywords
- Combinatorial optimization
- Generalized travelling salesman problem
- OpenStreetMap
- Shortest route