'Conversations with friends' how one comment resulted in Cardiff mathematician’s ground-breaking journey-mapping algorithm

Catch-ups with friends usually cover current events, the weather, work gossip, or a new favourite TV series. However, when Cardiff University Reader in Mathematics Dr Rhyd Lewis had one such chat with his sister-in-law, it led to an intriguing new journey-mapping algorithm and publication in the Journal of Heuristics.

After an off-hand comment that it would be useful for smartphones to plan journeys of a specific length, Dr Lewis’s thoughts turned to how beneficial a tweak to journey-mapping software would be, getting daily steps into a busy day or planning a run through an unfamiliar area.

Surprisingly, Dr Lewis found that there was little existing work on the subject and that popular existing applications that plan routes are often not automated, with users inputting journey waypoints themselves without automated calculations as to the journey’s specific length. This in turn required user effort, familiarity, or plain old-fashioned trial-and-error when an algorithm could take the effort and guesswork out of (or rather add into) the equation.

Algorithms such as these don’t only push for efficiency or time saving by plotting journeys that curb additional effort when a specific distance is preferred. On top of resource conservation, the user can utilise this journey-mapping algorithm to meet safety concerns by covering no more ground than is necessary. Personal safety is an ever-present concern when navigating urban landscapes, particularly for those unfamiliar users, such as those travelling for business or pleasure or who are new to an area. This potentially has growth opportunities such as creating more accessible journeys for disabled users who wish to conserve their personal energy, or for neurodivergent users who would like to minimise travel time through crowded spaces, or by letting people avoid undesirable routes or even make visually appealing routes for themselves to follow.

The resulting paper, ‘Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks’ co-written with Dr Padraig Corcoran with suggestions for fast-acting heuristics to meet the problem was published by the Journal of Heuristics in 2022 and emphasises Cardiff University School of Mathematics’ commitment to applying mathematic solutions as a means of improving our modern world

Dr Rhyd Lewis is a Reader in Mathematics and has also published on school bus routing, medical theatre/sports scheduling, as well as algorithmic graph theory and graph colouring. Dr Padraig Corcoran is a Senior Lecturer and the Director of Research in the School of Computer Science and Informatics and shares an interest in graph theory.