Running Loop Route Recommendation Algorithm with Diversity Beam Search

With the spread of smartphones and growing interest in health, many running apps, such as Nike Run Club [1], Strava [2], and Samsung Health [3], are widely used. However, while these services excel at workout logging, training plans, and community sharing, they still offer limited support for route selection. Novice runners, in particular, struggle to identify steep sections, assess nighttime safety factors (streetlights, crosswalks, traffic signals, etc.), and design loop routes that match a target distance. To address this, this paper proposes a system that automatically recommends safe, pleasant loop routes for novice runners by jointly considering infrastructure data such as slope, obstacles, and amenities. Its key components are (1) a Score function that sums seven weighted active terms, (2) a two-phase (Phase 1 + Phase 2) bidirectional search algorithm based on diversity beam search, (3) a spatially indexed Jeju database built from OSM, MOLIT (Ministry of Land, Infrastructure and Transport), and Google APIs, and (4) a fully deployed system using Spring Boot, React Native, Mapbox, and AWS.

Existing services excel at workout logging, training, and community features but offer little infrastructure-aware route recommendation. Nike Run Club [1] specializes in guided runs and training plans and does not recommend routes that reflect external infrastructure, while Strava [2] centers on heatmaps and route sharing, so generating loop routes that consider beginner safety is not a core feature. Samsung Health [3] focuses on post-run analysis, and Trail Router [4] generates round-trip routes of a specified distance but, because it prioritizes slope avoidance and green spaces, does not jointly consider obstacles and amenities.

Shortest-path algorithms such as Dijkstra's are designed to minimize distance and struggle to handle multiple objectives, such as slope and safety, simultaneously. Although studies exist on MCDM techniques [5][6] and target-distance-based loop route generation [7], research that simultaneously combines an infrastructure score, route diversity, and a real-time spatial index remains limited. Greedy search, a simple approach that selects only the single highest-scoring candidate at each step, easily converges to local optima and cannot guarantee route diversity. In contrast, beam search maintains the top-k candidates simultaneously and lets them compete, which is effective for escaping local optima[8]. This study applies beam search to spatial route exploration and extends it into diversity beam search by incorporating an overlap-ratio-based diversity filter.

The proposed system consists of four modules: (1) an offline data collection pipeline, (2) a route recommendation engine, (3) a backend API server, and (4) a frontend UI (Fig. 1). The collected and normalized data are stored in a MySQL spatially indexed database, and the road graph is loaded into an in-memory cache at server startup. Upon a user request, the system generates routes solely through database queries and in-memory computation, without calling external APIs, reducing response time.

Walkable roads in Jeju were collected via the OSM Overpass API[9] (excluding expressways and arterial roads; approx. 287K nodes), and missing segments were supplemented with MOLIT data and in-house CSV files (approx. 2.5M nodes), yielding a road network graph of approx. 2.79M points and 5.6M edges (Fig. 3). Each road point is defined as a node and each connection as an edge, ensuring that search paths never leave actual roads; disconnected segments between the two sources were merged using grid-index-based bridge edges (Haversine ≤ 10 m). We collected elevation from the Google Elevation API [10], obstacles from the OSM traffic_signal and crossing tags, and amenities from Google Places and public data, all stored in a spatially indexed MySQL database. The database consists of three groups, namely (a) the search graph, (b) infrastructure, and (c) users, courses, and records (Fig. 2), and a SPATIAL INDEX is applied to every coordinate column.

The score function in Eq. (1) evaluates the suitability of each candidate point. The Score consists of seven active terms: slope, obstacle, and reuse penalties; amenity and anchor-direction bonuses; and zigzag penalties. We deactivate the target-distance fitness (w1) and return cost (w5) because the phase structure replaces them (Table 1). The slope penalty normalizes segment slope, exempting slopes within ±5% and saturating at 20%, and the obstacle penalty normalizes traffic signals (×50) and crosswalks (×20) within a 10 m radius against a reference of 200. The reuse penalty is proportional to the number of visited nodes within a 50 m radius (minimum scale 0.4), and the amenity bonus is the inverse of the distance to the nearest amenity, 1/(1+d_min). The anchor-direction bonus is cosine-based, remaining neutral early and converging later as progress increases, and the zigzag penalty uses the angular difference between the current heading and the mean heading of the last four points, with different weights for the early and late stages (Table 1). Table 2 summarizes the symbols used in Eqs. (1)–(3) (see Table 1 for the weights wi).

Simple greedy search generates a single route by selecting only the candidate with the highest Score at each step. Although easy to implement, it (i) tends to converge to local optima, resulting in low stability of loop completion, and (ii) produces only one route, offering no alternative choices. To overcome these limitations, this section proposes diversity beam search.

The proposed diversity beam search combines conventional beam search with a diversity mechanism tailored to spatial routes. Nine beams (separated into nine directions relative to the anchor) compete and survive based on a global Score, substantially expanding the search space. Because node expansion follows the adjacency relations of the road edge graph (getNeighbors) one step at a time, generated routes always follow actual roads. At each step, invalid paths are pruned in advance by the six pre-candidate filters in Table 3 The search follows a bidirectional two-phase structure. First, anchors are fixed at 38% of the target distance from the start point in 16 directions within a radius of 600–2,000 m, securing directional diversity among routes in advance. Phase 1 searches from the start point toward the anchor and terminates when the cumulative distance reaches 48% with sufficient straight-line separation; Phase 2 returns from the anchor to the start point and completes the loop once the cumulative distance is at least 42% (up to 800 iterations per phase). The anchor-direction bonus bdir in Eq. (2) is defined as the product of two factors. bdir = (1 - cos(φ(r)π))/(2) · (dcur - dcand)/(dcur) (2) φ(r) = min(1, 2r) (Phase 1), φ(r) = min(1, 2(r-0.5)) (Phase 2) The first factor, (1−cos(φ(r)π))/2, is a weight that increases from 0 to 1 with progress. Since φ(r) rescales each phase's progress to 0–1, it gives almost no directional bonus early on, allowing the beams to spread freely, while they converge strongly toward the anchor later. The second factor, (d_cur−d_cand)/d_cur, is the rate of distance reduction toward the anchor and rewards candidates that move closer. Their product induces 'free exploration early and anchor convergence later', achieving both diverse routes and stable loop completion.

After the search, we apply an overlap-ratio-based diversity filter to the combined Phase 1 and Phase 2 routes. As shown in Eq. (3), the overlap ratio is defined as the number of points shared by two routes divided by the number of points in the shorter route. overlap(P1,P2) = (|S1 ∩ S2|)/(min(|S1|,|S2|)) (3) Coordinates are rounded to four decimal places (a grid of approx. 11 m), and for any route pair whose overlap ratio exceeds 30%, one route is removed to ensure diversity among the final three. Finally, the system returns the top three loop routes whose cumulative travel distance plus the return distance to the start point falls within ±10% of the target distance.

The backend is implemented as a Spring Boot REST API that provides endpoints for route recommendation and running-record management. The frontend is implemented with React Native (Expo) and Mapbox GL JS [11], visualizing recommended routes as color-coded polylines, and the system is deployed on AWS EC2 and RDS (MySQL).

To validate the proposed algorithm, the Jeju road network on AWS RDS was mirrored to a local MySQL instance (approx. 2.79M road points and 5.6M edges). Generated routes were measured in four scenarios with different start points and target distances (Tapdong 3 km, Downtown 5 km, Yeon-dong 3 km, and Ido 4 km), and an ablation study comparing the greedy, proposed, and Score-removed configurations under the same scenarios with fixed anchors was also conducted (Section 4.D).

The evaluation metrics are (1) the number of generated routes, (2) the average slope (%), (3) the number of obstacles near the route (within 15 m), (4) the distance to the nearest amenity (m), and (5) the average pairwise overlap ratio (Eq. 3). The first three metrics indicate how well the infrastructure Score is reflected, and the overlap ratio indicates route diversity. Since the system prioritizes generating natural loop routes, the distance error is reported as a secondary metric.

Fig. 4 visualizes the routes the proposed algorithm generates in the four scenarios on the actual road network (gray). All generated routes are loops that follow road edges, branch in different directions from the start point, and naturally circulate through the urban grid. The measurements for each scenario are summarized in Table 4.

To isolate the contributions of diversity beam search and the infrastructure Score, three configurations were compared under the same four scenarios with fixed anchors (at 38% of the target distance): (a) Greedy, a single-beam configuration; (b) Proposed, the multi-beam diversity beam search (current); and (c) Score-removed, with the weights of the infrastructure terms set to 0. Since fixing the anchors removes randomness, differences between configurations stem from the algorithmic components. Table 5 summarizes the results. Fig. 5 compares the routes generated by the greedy and proposed methods on the same road network, with the same start point and anchor. Visually, the greedy method yields only a single route, whereas the proposed method generates multiple loop routes branching in different directions from the start point. First, the effect of diversity beam search (Greedy → Proposed): the greedy method generated only one route (1.0 routes), offering no alternatives, and its large distance error of 0.70 made loop completion unstable. In contrast, the proposed method generated 2.2 distinct routes on average and halved the distance error to 0.36, quantitatively confirming its advantages in diversity and loop completion. Second, the effect of the infrastructure Score (Score-removed → Proposed): enabling the Score improved all three metrics—average slope from 2.94% to 2.82%, obstacles from 5.5 to 4.5, and amenity distance from 116 m to 112 m—confirming that the Score guides routes to be safer and more pleasant. The modest improvement is because the infrastructure weights are smaller than geometric terms such as the reuse penalty (w4 = 20) and thus act as corrective terms.

A strength of the proposed algorithm is that, because it follows the road edge graph one step at a time, the generated routes always follow actual roads (Fig. 4). The infrastructure Score was also reflected, with an average slope of approx. 2.8% and an average amenity distance of approx. 124 m. However, generation stability remains a limitation, as (i) the number of generated routes is inconsistent (only one in Ido) and (ii) the distance error is large in some cases; this is attributed to random anchors and graph connectivity, and can be improved through anchor determinization and distance control in future work.

This paper proposed an intelligent running loop route recommendation system for novice runners. We analyzed the limitations of greedy search and combined diversity beam search with a beam width of k = 9 and Phase 1 + Phase 2 bidirectional search. By integrating a Jeju spatially indexed database (approx. 2.79M points and 5.6M edges), a Score function with seven active terms, and an overlap-based diversity filter, we confirmed that the system generates diverse loop routes that follow actual roads, with gentle slopes and nearby amenities. Furthermore, the ablation study quantitatively confirmed that diversity beam search improves route diversity and loop completion, while the infrastructure Score improves the slope, obstacle, and amenity metrics. Future work includes (1) improving generation stability through anchor determinization and distance control, (2) verifying statistical significance through repeated experiments and expanding the scenarios, (3) directly reflecting elevation data in route quality, and (4) personalized recommendation based on running records and porting the pipeline to other regions.

This research was supported by the ANCHOR COSS program through the Jeju ANCHOR Center, funded by the Ministry of Education (MOE) and the Jeju ANCHOR Center, Republic of Korea (2026-RISE-17-001). This research was also supported by the ANCHOR program through the Jeju ANCHOR Center, funded by the Ministry of Education (MOE) and the Jeju Special Self-Governing Province, Republic of Korea (2026-ANCHOR-17-001).