Planning routes based on actual data is not an easy task, especially when faced with challenging conditions. Finding cycles of fixed-length in directed, weighted graphs is an NP-hard problem. In the field, not enough research has been done on many alterations of this problem, especially in regard to real-world applications. In this paper, we propose a greedy algorithm for generating cyclic routes of the desired length and characteristics to match specifictypes of bicycles, using real-world data. The proposal is based on a greedy search of sub-routes to findthe best-fitbicycle route. The results indicate, that the algorithm performs very well and can be easily adjusted for other similar tasks. The mean absolute percentage error for the total distance of the routes was below the acceptable 5% error, reaching 3.24 MAPE for shorter and 2.74 MAPE for longer routes.
In the context of road planning, the basic algorithms are graph algorithms, which are quite often greedy. Which results in high computational complexity. An alternative to this group of algorithms is heuristics, which are algorithms that return an approximate solution but with low computational and time expenditure. An example of one of the latest heuristic algorithms is a technique inspired by the behavior of penguins [10]. It should also be noted that older algorithms are subject to hybridization, an example of which is the k-nearest neighbors algorithm for the clustering problem [11]. Such algorithms allow for the possibility of improving machine learning techniques, as shown in [12, 13], where algorithms inspired by nature were used as an optimizer, or to detect features in images. Again in [14], the authors focused on improving the stitching algorithm by applying the selected heuristic. The enormous use of heuristics is reflected in the possibility of using them as optimization methods in drones [15]. Generally, the optimization problem is quite known and can quite often be solved by finding an approximate solution. An example are navigations and different vessel applications [16, 17, 18]. In [19] the authors proposed a heuristic approach for generating cycles of fixed length in undirected graphs. The presented approach was tested on a graph obtained from real-world data.
Based on the literature analysis, the need for new methods and techniques in road planning can be noticed. In this paper, we present a solution for generating cycles of desired length and of certain edge attribute properties in a real-world environment, by introducing a dedicated algorithm. A practical use of finding a cyclic route suited for certain bicycle types is also presented and analyzed. The main contributions of the paper can be listed as: • New dedicated algorithm for finding cyclic routes with desired total length and edge attribute properties.
• Practical application of the proposed approach in the task of findingthe best bicycle route.
In this section, the proposed approach along with all the techniques used are described. The distance function used in the algorithm is the Earth’s Orthodrome (the shortest path between two points on the surface of a sphere running along its surface), commonly called great-circle distance. It is calculated from the coordinates of the starting vertex ’a’ and the destination vertex ’b’, in the UTM system. It is most often calculated using the haversine formula (Eq. 1), where is the Earth’s radius, lat and lat are the latitudes of the two points (in radians), Δlat and Δlon are the differences in coordinate values between the two points (in radians). Algorithm 1: Proposed greedy route-finding algorithm
Input: Graph representation , start node id , estimated number of sub-routes , desired total distance , number of acceptable attempts , acceptable distance error 1 path = [a]; total_distance = 0; part = ; part_previous = part;
2 b = a; p = b; acceptable_attempts = 0; i = 0; 3 Set the ’visited’ attribute for all edges in the to ; 4 while _ < do 5 part_path = find_partial_route (a, p, part, part_previous); 6 part_distance = path_weight (G, part_path, ’length’); 7 back_path = dijkstra (G, b, heuristic = dist_func, weight = weight_func()); 8 back_distance = path_weight (G, back_path, ’length’); if _ + _ + _ > ⋅ (1.0 + ) then back_path_previous = dijkstra (G, a, heuristic = dist_func, weight = weight_func()); back_distance_previous = path_weight (G, back_path_previous, ’length’); 30 path += part_path[1:] + back_path[1:]; total_distance = ℎ_ℎ(G, path, ’length’); 31 return path, total_distance;
The weighting function used in the Dijkstra algorithm takes into account its edges’ actual length, surface type, and (if the algorithm is looking for a return route) whether the edge has already been visited. Each considered surface type can be assigned a certain positive, non-zero value, acting as a modifier of the edge’s actual length. This makes the algorithm prefer favorable surface types. If the ’visited’ edge attribute is set as ’True’, the function returns infinity, as its goal is to avoid already visited edges. However, if the path can not be completed without going through such an edge, it can still be included in the path for the second time.
Algorithm 2: Finding partial route algorithm
Input: start node id , previous node id , desired distance from start node , desired distance from previous node _ 1 dijkstra_distances, dijkstra_paths = single_source_dijkstra (G, b, weight = weight_func(), cutoff = distance); 2 possible_nodes = dijkstra_distances.keys(); 3 best_score = ∞; 4 best_b = a; 5 for i, k in enumerate (possible_nodes) do 6 d = dist_func (a, k); 7 d_prev = dist_func (previous, k); score = ( − )2 + (_ − _)2; if score < best_score then best_score = score; best_b = k; 12 return dijkstra_paths[best_b];
Dijkstra’s algorithm has proven to be one of the most significant algorithms in graph theory. The algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph, therefore, finding the definitive shortest path between two nodes ’a’ and ’b’. There are many variations of the standard Dijkstra’s algorithm, including distance cut-off modification, which was incorporated in the part of the proposed algorithm, responsible for finding sub-route of the desired length (presented in Alg. 2). By introducing a maximum allowable distance from the source vertex, the algorithm seeks all paths that meet the allowable distance requirement. The allowable distance can be affected by a custom weighting function, as described in Sec. 2.2. It is worth pointing out, that if it is desired (for example, by not only taking the length aspect of the edges but other attributes, such as the mentioned surface type), this can result in the found paths being longer than the allowable distance.
In this section, the proposed algorithm is described in detail. The algorithm was created for the real-life scenarios. Its objective is to find a directed cycle whose total length is within the permissible range and which has optimal edge attributes. The proposed algorithm is greedy, as it divides the task of finding the whole route into smaller sub-routes, where it tries to maximize certain objective.
The operating principle of the algorithm can be briefly described as follows: The algorithm will search for a route by determining smaller sub-routes. The estimated length of each sub-route is equal to the quotient of the distance and the number of sub-routes. Starting from the starting vertex, the algorithm searches locally for the best vertex to go to. After one, the algorithm looks for a route to it and adds the distance to the total. After determining the sub-route, the algorithm considers whether it should choose a route back to the start vertex (completing the journey) or continue searching for sub-routes.
Finding a sub-route is presented in detail in Alg. 2. Starting from the starting vertex ’a’, the
algorithm performs a search of routes to all vertices to which the shortest path (taking into
account the weight function) is less than or equal to the estimated length of the sub-route (by
the Dijsktra’s algorithm with cut-off distance). After finding vertices that meet the condition,
the best node is chosen using the following metric:
(, , ) = ((, ) − )2 + ((, ) − )2
(
The Dijsktra’s algorithm used to find the shortest path between nodes in a graph by iteratively exploring the consecutive neighboring nodes and updating the shortest known distance from the start node to every other node met, until the shortest path is found. The Dijkstra’s algorithm is a greedy algorithm.
In order to introduce randomness to the algorithm, the finding sub-routes part can be altered to keep the score for every node found by the Dijkstra algorithm. Having calculated all the scores and sorted them accordingly, a random node from among the top nodes can be chosen, therefore making the choice of sub-path random, while still selecting a close-to-optimal path. However, this change significantly increases the computational complexity of the algorithm due to the sorting required.
In the main loop of the algorithm, after finding the local sub-route, the algorithm looks for the shortest return route (using Dijkstra’s algorithm) to the starting node. If the route found so far has a length whose total distance has an error within ± of the desired distance , the algorithm returns this route. If the route is too short, it continues the search. If it is too long, (while the route that would contain the return path from the current vertex ’a’ is too short), the algorithm tries again to find vertex ’b’, this time with half of the range from the previous iteration of the sub-route search. In case the algorithm fails to find a route so that its total length is within the intended error, during a such number of iterations (during which is halved each time), the algorithm returns a route with a return path from vertex ’a’, thus the length of such a route is less than ⋅ (1 − ) of the intended length. This acts as a safe mechanism, preventing the algorithm from looping infinitely. Even though this is unlikely to happen, the algorithm was created in mind of real-world application, in which such a situation can occur (for example, if there are multiple dead-ends or there are not enough roads and the graph is simply too sparse).
In the experiments, we considered the task of finding a loop for a biking trip, considering the desired length of the trip and the bike type.
In the experiments, we used publicly available OpenStreetMap (OSM) data. OSM is a collaborative project aimed at creating a free, editable map of the world. It is built by a community of contributors who add and update geographical information. OSM is widely used in many applications, such as navigation, urban planning disaster response and even environmental analysis. It provides a great source of information for traffic management, including bicycles. By using its API, we are able to convert the real-world part of a map into a representative graph, as the OSM is built as such graph, containing vertices and edges with certain attributes. There are, however certain limitations. Some edges may be mislabelled or may miss certain attributes.
The main task revolves around finding a good path, that will be favorable to the type of bicycle chosen. For example, if we consider racing bicycles, a desired path should be level and related to fast traffic. On the other hand, mountain bikes, and dirt roads should be chosen over the city’s streets. To achieve that, the weighting function described in Sec. 2.2 was introduced. As the OSM agenda allows for multiple surface types as edge attributes (in fact, it can be anything), to facilitate the task of assigning multipliers for surface types, we considered three separate categories, to which different types of surface may apply: ’Road’ - a surface characterized by a level surface, for high-speed driving, like asphalt, ’Off-road’ - a surface characterized by uneven ground, for off-road riding, like dirt and ’Neutral’ - suitable but sub-optimal for the extreme bicycle types. This category includes types found mostly on short distances in cities - such as paving stones. This way, for each bike type, we only need to assign multipliers for those three categories. These settings can be stored and easily modifiedin the ’.yaml’ file. In the experiments, we used the following settings for bike types and surface categories: The occurring problem we faced was the ambiguity connected with the surface types. Some surface types, such as ’paved’ could represent both paths paved with paving stones or just hardened soil.
As previously mentioned in Sec. 2.4.3, the main goal of introducing the proposed algorithm was the ability for the user to create a route of desired length and attribute quality, that start and end positions were the same. In the conducted experiments, we have found that the number of sub-routes equal to 5 yields the most satisfactory results for the user. The routes created with lower parameter tended to yield straight routes, going just out and back to the start, while the greater made the route cross over itself and twist. This can be observed in Fig. 1. There was no other simple way to select this parameter, other than manually, as there is no simple way of measuring ’roundness’ but by visual observation.
(a) n = 3 (b) n = 5 (c) n = 7
The error of ±5% was chosen for the desired distance. Such error gives the algorithm some flexibility in finding good sub-routes while maintaining the total length of the route objective.
In this section obtained results are presented. We tested the algorithm with different desired lengths and bike types. In Fig. 2, route comparison of example 9km routes between two opposite biketypes are presented. The starting position was chosen near Walthamstow Wetlands, London, as the London roads are well documented in OSM and the nearby park allowed the algorithm to choose paths further from busy roads (while still prioritizing the 9 km-length objective). As can be observed in the sub-figures, provided examples of surfaces in the two distinct routs differ greatly, as they fittheir specificbike type. Route chosen in Fig. 2a leads through green areas, with rough surfaces, while on the contrary, Fig. 2b presents a part of an asphalt bike-lane in the city’s busier area.
(a) ’Mountain’ bicycle (b) ’Racing’ bicycle
The algorithm was tested for the mean absolute percentage error of the obtained routes. To do so, two tests were performed, one for short and the other for long routes. The former measured the MAPE of 11 routes, ranging from 2km to 6km, with an interval of 0.4 km. The resulting error was 3.24%. The ladder measured routes ranging from 20km to 60km (with 4km intervals). The obtained MAPE was equal to 2.74%. Both of the obtained errors were within the acceptable range (which was set to 5%, as mentioned in Sec. 3.3).
During tests we were challenged with algorithms limitations, mainly involving insufficient or incorrect edge labelling. Furthermore, the amount of possible surface types is very extensive, which proved to be difficult to deal with and due to which we had to limit the considered surface-types. Another draw-back we had faced was findingroutes in the secluded areas, where graphs were often disconnected, making it impossible to findthe route meeting the criteria or making the algorithm loop infinitely(which we have since secured, as described in Sec. 2.4.3. As our approach is rather unique, as it considers indirect features of the edges in general cycle-findingproblem, it was hard to properly asses the method. However, this makes the research more impactful and the obtained results indicate the correctness of the approach.
The proposed algorithm can be used to find a directed cyclic path that needs to meet certain edge conditions in real life. In this paper, the task of finding a cycling route for a specific bike type and the assigned total length was presented. Based on the obtained results, the algorithm performs well for the considered tasks, generating routes within the acceptable distance error and adapting to the desired bike type. The limits of the algorithm are mainly due to miss-labeling of the edges and specific surface topology that may differ from location to location. Although these issues can be addressed by fine-tuning the surface categories and hyperparameters of the algorithm, it prevents the method from being fully universal. Nevertheless, the presented approach is flexible and can be applied to similar tasks. Overall, the algorithm performs well and we plan to develop it further in future work.
This work was supported by the Rector’s mentoring project ”Spread your wings” at the Silesian University of Technology. [5] W. Wei, F. Gao, R. Scherer, R. Damasevicius, D. Połap, Design and implementation of autonomous path planning for intelligent vehicle, Journal of Internet Technology 22 (2021) 957– 965. [6] M. Yao, H. Deng, X. Feng, P. Li, Y. Li, H. Liu, Improved dynamic windows approach based on energy consumption management and fuzzy logic control for local path planning of mobile robots, Computers & Industrial Engineering 187 (2024) 109767. [7] M. Reda, A. Onsy, A. Ghanbari, A. Y. Haikal, Path planning algorithms in the autonomous driving system: A comprehensive review, Robotics and Autonomous Systems (2024) 104630. [8] J. Yu, C. Chen, A. Arab, J. Yi, X. Pei, X. Guo, Rdt-rrt: Real-time double-tree rapidly-exploring random tree path planning for autonomous vehicles, Expert Systems with Applications 240 (2024) 122510. [9] X. Zhou, J. Yan, M. Yan, K. Mao, R. Yang, W. Liu, Path planning of rail-mounted logistics robots based on the improved dijkstra algorithm, Applied Sciences 13 (2023) 9955. [10] O. W. Khalid, N. A. M. Isa, H. A. M. Sakim, Emperor penguin optimizer: A comprehensive review based on state-of-the-art meta-heuristic algorithms, Alexandria Engineering Journal 63 (2023) 487–526. [11] K. Prokop, Grey wolf optimizer combined with k-nn algorithm for clustering problem,
IVUS 2022: 27th International Conference on Information Technology (2022). [12] D. Połap, Neuro-heuristic analysis of surveillance video in a centralized iot system, ISA transactions (2023). [13] S. Z. Kurdi, M. H. Ali, M. M. Jaber, T. Saba, A. Rehman, R. Damaševičius, Brain tumor classification using meta-heuristic optimized convolutional neural networks, Journal of Personalized Medicine 13 (2023) 181. [14] K. Prokop, D. Połap, Heuristic-based image stitching algorithm with automation of parameters for smart solutions, Expert Systems with Applications 241 (2024) 122792. [15] S. Darvishpoor, A. Darvishpour, M. Escarcega, M. Hassanalian, Nature-inspired algorithms from oceans to space: A comprehensive review of heuristic and meta-heuristic optimization algorithms and their potential applications in drones, Drones 7 (2023) 427. [16] W. Kazimierski, N. Wawrzyniak, M. Wlodarczyk-Sielicka, T. Hyla, I. Bodus-Olkowska, G. Zaniewicz, Mobile river navigation for smart cities, in: Information and Software Technologies: 25th International Conference, ICIST 2019, Vilnius, Lithuania, October 10–12, 2019, Proceedings 25, Springer, 2019, pp. 591–604. [17] M. Włodarczyk-Sielicka, N. Wawrzyniak, Problem of bathymetric big data interpolation for inland mobile navigation system, in: Information and Software Technologies: 23rd Interna- tional Conference, ICIST 2017, Druskininkai, Lithuania, October 12–14, 2017, Proceedings, Springer, 2017, pp. 611–621. [18] I. Garczyńska, A. Tomczak, G. Stępień, L. Kasyk, W. Ślączka, T. Kogut, Applicability of machine learning for vessel dimension survey with a minimum number of common points, Applied Sciences 12 (2022) 3453. [19] R. Lewis, P. Corcoran, Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks, Journal of Heuristics 28 (2022) 259–285. URL: https://doi.org/10.1007/s10732-022-09493-5. doi:10.1007/s10732-022-09493-5.