Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/24302
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Schweimer, C | - |
dc.contributor.author | Geiger, BC | - |
dc.contributor.author | Wang, M | - |
dc.contributor.author | Gogolenko, S | - |
dc.contributor.author | Mahmood, I | - |
dc.contributor.author | Jahani, A | - |
dc.contributor.author | Suleimenova, D | - |
dc.contributor.author | Groen, D | - |
dc.date.accessioned | 2022-03-21T11:45:28Z | - |
dc.date.available | 2022-03-21T11:45:28Z | - |
dc.date.issued | 2021-06-02 | - |
dc.identifier | 11547 | - |
dc.identifier.citation | Schweimer, C., Geiger, B.C., Wang, M., Gogolenko, S., Mahmood, I., Jahani, A., Suleimenova, D. and Groen, D. (2021) 'A route pruning algorithm for an automated geographic location graph construction', Scientific Reports, 2021, 11 (1), 11547, pp. 1-11. doi: 10.1038/s41598-021-90943-8. | en_US |
dc.identifier.uri | https://bura.brunel.ac.uk/handle/2438/24302 | - |
dc.description | Supplementary Information: The online version contains supplementary material available at https://doi.org/10.1038/s41598-021-90943-8. Map data copyrighted OpenStreetMap contributors and available from https://www.openstreetmap.org. | en_US |
dc.description.abstract | Copyright © The Author(s) 2021. Automated construction of location graphs is instrumental but challenging, particularly in logistics optimisation problems and agent-based movement simulations. Hence, we propose an algorithm for automated construction of location graphs, in which vertices correspond to geographic locations of interest and edges to direct travelling routes between them. Our approach involves two steps. In the first step, we use a routing service to compute distances between all pairs of L locations, resulting in a complete graph. In the second step, we prune this graph by removing edges corresponding to indirect routes, identified using the triangle inequality. The computational complexity of this second step is O(L3) , which enables the computation of location graphs for all towns and cities on the road network of an entire continent. To illustrate the utility of our algorithm in an application, we constructed location graphs for four regions of different size and road infrastructures and compared them to manually created ground truths. Our algorithm simultaneously achieved precision and recall values around 0.9 for a wide range of the single hyperparameter, suggesting that it is a valid approach to create large location graphs for which a manual creation is infeasible. | en_US |
dc.description.sponsorship | The presented work was developed in the project HPC and Big Data Technologies for Global Systems (HiDALGO), under grant agreement No.824115. The Know-Center is funded within the Austrian COMET Program—Competence Centers for Excellent Technologies—under the auspices of the Austrian Federal Ministry for Climate Action, Environment, Energy, Mobility, Innovation and Technology, the Austrian Federal Ministry for Digital and Economic Affairs and by the State of Styria. | en_US |
dc.description.uri | https://doi.org/10.1038/s41598-021-90943-8 | - |
dc.format.extent | 1 - 11 | - |
dc.format.medium | Electronic | - |
dc.language.iso | en_US | en_US |
dc.publisher | Springer Nature | en_US |
dc.rights | Rights and permissions: Open Access. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit https://creativecommons.org/licenses/by/4.0/. | - |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | - |
dc.subject | computer science | en_US |
dc.subject | information technology | en_US |
dc.title | A route pruning algorithm for an automated geographic location graph construction | en_US |
dc.type | Article | en_US |
dc.identifier.doi | https://doi.org/10.1038/s41598-021-90943-8 | - |
dc.relation.isPartOf | Scientific Reports | - |
pubs.issue | 1 | - |
pubs.publication-status | Published | - |
pubs.volume | 11 | - |
dc.identifier.eissn | 2045-2322 | - |
Appears in Collections: | Dept of Computer Science Research Papers |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
FullText.pdf | 2.03 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License