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

R. Lewis () and P. Corcoran ()
Additional contact information
R. Lewis: Cardiff University
P. Corcoran: Cardiff University

Journal of Heuristics, 2022, vol. 28, issue 3, No 2, 259-285

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

Keywords: Heuristics; Graphs; Cycles; Circuits; Location-based services (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09493-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:3:d:10.1007_s10732-022-09493-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-022-09493-5

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().