Fast algorithms for computing fixed-length round trips in real-world street networks

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X and Corcoran, Padraig ORCID: https://orcid.org/0000-0001-9731-3385 2024. Fast algorithms for computing fixed-length round trips in real-world street networks. SN Computer Science 5 (7) , 868. 10.1007/s42979-024-03223-3

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (5MB) | Preview

Abstract

This paper proposes and evaluates algorithms for calculating round trips of a prescribed length on directed street networks. This problem has several real-world applications, such as designing jogging routes and cycling tours. In this work, we focus specifically on methods that avoid the need to download, process, and store large map databases. At the same time, we aim for our methods to be fast, accurate, and capable of handling a wide range of prescribed distances, from just a few meters to many kilometres. To achieve this, our overall strategy involves using a small number of calls to a suitable online mapping service to collect relevant structural information for the problem at hand. All remaining computations are then performed locally on the client. Empirically, we demonstrate that our suggested techniques outperform existing open-source algorithms in terms of both accuracy and runtime requirements. Our most successful approach is based on multi-objective local search, utilizing specialized neighbourhood operators that exploit the underlying graph-theoretical properties of this problem, resulting in runtimes of around 2–3 s on a typical desktop computer.

Item Type:	Article
Date Type:	Published Online
Status:	Published
Schools:	Computer Science & Informatics Mathematics
Publisher:	Springer
ISSN:	2661-8907
Date of First Compliant Deposit:	9 September 2024
Date of Acceptance:	11 August 2024
Last Modified:	10 Sep 2024 11:30
URI:	https://orca.cardiff.ac.uk/id/eprint/171946

Actions (repository staff only)

Edit Item