Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks

Lewis, Rhydian ORCID: https://orcid.org/0000-0003-1046-811X and Corcoran, Padraig ORCID: https://orcid.org/0000-0001-9731-3385 2022. Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks. Journal of Heuristics 28 , pp. 259-285. 10.1007/s10732-022-09493-5

Preview

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

Abstract

This paper proposes two heuristic algorithms for finding fixed-length circuits and cycles in undirected edge-weighted graphs. It focusses particularly on a largely unresearched practical application where we are seeking attractive round trips for pedestrians and joggers in urban street networks. Our first method is based on identifying suitable pairs of paths that are combined to form a solution; our second is based on local search techniques. Both algorithms display high levels of accuracy, producing solutions within just a few meters of the target. Run times for the local search algorithm are also short, with solutions in large cities often being found in less than one second.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics Mathematics
Additional Information:	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.
Publisher:	Springer Verlag (Germany)
ISSN:	1381-1231
Date of First Compliant Deposit:	2 March 2022
Date of Acceptance:	1 March 2022
Last Modified:	08 Jan 2025 11:48
URI:	https://orca.cardiff.ac.uk/id/eprint/147966

Actions (repository staff only)

Edit Item