A route pruning algorithm for an automated geographic location graph construction

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Christoph Schweimer, Bernhard C. Geiger, Meizhu Wang, Sergiy Gogolenko, Imran Mahmood, Alireza Jahani, Diana Suleimenova, Derek Groen
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/22f60a287a3c43a48cd3d7bbbfe296bb
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:22f60a287a3c43a48cd3d7bbbfe296bb
record_format	dspace
spelling	oai:doaj.org-article:22f60a287a3c43a48cd3d7bbbfe296bb2021-12-02T18:25:02ZA route pruning algorithm for an automated geographic location graph construction10.1038/s41598-021-90943-82045-2322https://doaj.org/article/22f60a287a3c43a48cd3d7bbbfe296bb2021-06-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-90943-8https://doaj.org/toc/2045-2322Abstract 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 $$\mathscr{O}(L^3)$$ O ( L 3 ) , 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.Christoph SchweimerBernhard C. GeigerMeizhu WangSergiy GogolenkoImran MahmoodAlireza JahaniDiana SuleimenovaDerek GroenNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-11 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Christoph Schweimer Bernhard C. Geiger Meizhu Wang Sergiy Gogolenko Imran Mahmood Alireza Jahani Diana Suleimenova Derek Groen A route pruning algorithm for an automated geographic location graph construction
description	Abstract 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 $$\mathscr{O}(L^3)$$ O ( L 3 ) , 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.
format	article
author	Christoph Schweimer Bernhard C. Geiger Meizhu Wang Sergiy Gogolenko Imran Mahmood Alireza Jahani Diana Suleimenova Derek Groen
author_facet	Christoph Schweimer Bernhard C. Geiger Meizhu Wang Sergiy Gogolenko Imran Mahmood Alireza Jahani Diana Suleimenova Derek Groen
author_sort	Christoph Schweimer
title	A route pruning algorithm for an automated geographic location graph construction
title_short	A route pruning algorithm for an automated geographic location graph construction
title_full	A route pruning algorithm for an automated geographic location graph construction
title_fullStr	A route pruning algorithm for an automated geographic location graph construction
title_full_unstemmed	A route pruning algorithm for an automated geographic location graph construction
title_sort	route pruning algorithm for an automated geographic location graph construction
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/22f60a287a3c43a48cd3d7bbbfe296bb
work_keys_str_mv	AT christophschweimer aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT bernhardcgeiger aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT meizhuwang aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT sergiygogolenko aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT imranmahmood aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT alirezajahani aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT dianasuleimenova aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT derekgroen aroutepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT christophschweimer routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT bernhardcgeiger routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT meizhuwang routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT sergiygogolenko routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT imranmahmood routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT alirezajahani routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT dianasuleimenova routepruningalgorithmforanautomatedgeographiclocationgraphconstruction AT derekgroen routepruningalgorithmforanautomatedgeographiclocationgraphconstruction
_version_	1718378028119097344

A route pruning algorithm for an automated geographic location graph construction

Ejemplares similares