Development of an optimal route alghorithm based on navigation services data

These days, navigation software is widely used. The quickest and shortest routes are the route search optimizations provided by current navigation systems. This study will provide an algorithm for route optimization that takes into account the resources required to overcome the route.

The problem statement states that the goal is to identify a path that uses the fewest resources to travel between two sites (perhaps including several intermediary points).

We will start by pointing out that since ascent requires more resources than descent, the least expensive route is the one that involves the fewest ascents.

A route with a starting point, a destination, and an arbitrary number of intermediate points is the initial data.

The Google Maps service provides the electronic map data used in this work. The Google Maps Directions API service is used to find potential routes between two nearby route points [1]. Additionally, the elevation data for route points – obtained through the Google Maps Elevation API service – will be used in the study [2]. The goal is to give each path between any two nearby points a weight. In order to accomplish this, the route is broken up into numerous sections, each of which has a specified length L, starting point height H_start, and ending point height H_end.

Let's explain what energy functional is:

(1)

where α is the route section's slope angle. Formula (2) can be used to determine the angle:

(2)

Let's introduce the idea of the cost functional:

(3)

where L is the section length and E is the cost functional that was previously introduced.

The total of the cost functional values for every segment will be used to determine the weight value for the overall route:

(4)

Each route's weights are determined. As a result, the overall weight of each route will vary according on the cost of travel. The route that includes the relevant sections with the lowest values of the determined weights is the desired one.

Test outcomes. Finding a path in the Tatra National Park (Poland) that includes intermediate waypoints serves as an illustration of how the algorithm works. Start point – ‘Dolina Białego’ Ticket office (49.2777890, 19.9571640). End point – ‘Giewont’ Mountain peak (49.2515054208116, 19.934035065097877) (Figure).

Pic. Routes between waypoints, Tatra National Park (Poland)

The routes and corresponding weights calculated by the algorithm are presented in Table 1. The routes have 600-900 sections to analyze with (1).

Table

Route's weights

Route 2 has the lowest weight values for respective sections of the route.

Conclusion, will make up the intended route based on the data in Table. It can be inferred from the test analysis that the algorithm's output is satisfactory. The system chooses routes with fewer climbs and, therefore, less energy consumption for hilly and mountainous terrain than those suggested by Google Maps. For flat terrain the outcome is in line with what Google Maps suggests.