TrueDrive: a sophisticated spatial analysis technology
Everybody knows that finding ‘the perfect’ location to open a sales point or to start a building construction is a very nerve-wracking and time-consuming process.
Defining a proposed trade area based on just traditional marketing studies can cause crucial omission errors, lead to poor sales and wrong site selection decisions. First of all you should precisely evaluate the market environment, the planned site location suitability, the competitive supply concerning local demographics and logistical factors, and many other things!
TrueDrive provides an API for performing the drive time/distance calculation. TrueDrive enables you to develop interactive desktop, server or web-based mapping or market analysis applications for solving various routing and logistical problems. A smart calculation algorithm requiring low computation resources and memory consumption apart from flexible TrueDrive integration capabilities can be valuable for performing different marketing analyses.
Based on TrueDrive, it is possible to create a web service using which the network analysis algorithms can be run. The following road network analysis algorithms are currently available:
- Calculation of shortest route between points
- Calculation of service areas from specified points for specific time or distance.
On the left: calculation of shortest route, on the right: calculation of service area
One of the main TrueDrive benefits is the extremely high speed of applied algorithms with deep optimization. This enables you to almost instantly complete tasks that previously required a delayed start or long wait.
It can help you solve various non-standard problems in the domain of road transportation, enabling you to automate and optimize many work processes: decrease costs, improve safety, etc. The range of solvable problems is wide and can be tailored further to the exact needs of your project or organization.
TrueDrive is not yet another software product for creating road network services, but the product with number of benefits:
- High speed of the algorithms work enables you to perform typical calculations on the fly.
- Possibility to use not only standard road parameters for optimization (time and distance), but also specific parameters calculated in advance at the stage of building the road graph index. For example, you can use the traffic safety criterion (if data is available) or apply the formula for calculating the optimization parameter on the fly, for which the SQL notation is used.
- Possibility to use barriers. Each request may contain a set of spatial restrictions on traffic on certain road segments or zones. If traffic on such sections is impossible or obstructed (transparent barriers), then this circumstance will be taken into account when calculating the route. Using barriers does not require rebuilding of the road graph index, each calculation request can contain its own set of barriers.
- When optimizing time, the turn penalties can be used in calculations depending on the turn angle. Thus, in case of the right-hand traffic, turning left will take longer than turning right. This feature enables you to bring the calculation results closer to real conditions.
- When calculating service areas, multiple centers can be used at a time. The number of such centers is not limited and can reach up to several hundred, thus, for example, per one launch you can get the distribution of service areas for many stores or logistics centers at once.
- Polygons obtained during the service areas calculation look very detailed, exactly repeating boundaries of passed road network sections. The detailed service areas boundary allows for greater accuracy in determining the reachability of certain points and calculating overlay parameters (for example, calculation of demographics covered by service area).
- When calculating service areas from multiple centers, a mode is possible in which the output service areas will compete, that is, they will not overlap each other. In this case, the disputed overlap areas will be divided between competing centers according to the criterion of proximity to such centers. The algorithm is somewhat similar to building of Thyssen polygons, but the calculation is carried out on the road network.
Web service key features are as follows:
- availability of ready-made network analysis tools, including:
- search for the shortest route between specific points,
- optimization of the order of avoidance of intermediate points of the route,
- calculation of isolated service areas,
- calculation of competitive service areas;
- ability to use ready-made data sets for calculation (indices), as well as building new data sets (to order) based on user data;
- support for OS Linux and Windows Server;
- TrueDrive software is developed in Russian federation and belongs to Russian company;
- possibility of deep integration with the CoGIS infrastructure platform enables you to solve complex thematic problems using network analysis within the existing information infrastructure.
The major distinguishing features of the TrueDrive technology are as follows.
All the network analysis algorithms available in TrueDrive are provided to optimize specific characteristic. That is, for example, a typical task of finding optimal route between two points on map is minimization of travel time.
It is also possible to use characteristic of the distance traveled, rather than the time spent. This enables you to get the shortest route, despite the fact that the time used to travel along the found route may be longer.
In everyday tasks, optimization of time and distance is usually sufficient, but in the workflows of an enterprise or a government agency, calculations may require specific characteristics depending on the problem. The TrueDrive road network analysis algorithms enable you to use both standard parameters such as time or distance, and any other custom characteristics.
Optimal routes calculated by time and distance
To take advantage of this opportunity, at the stage of preparing a special road graph index based on the source data, it is necessary to set a formula for calculating the user characteristic based on the source road segments properties.
The ability to work with user characteristics during optimization enables you to solve a wide range of non-standard problems. That is, for example, instead of optimizing time, you can minimize the amount of used fuel, focusing on the average consumption of the car, which depends on the current speed.
Even more impressive is the use of characteristics determining the accident rate of each road section, taking into account the segments length. This algorithm will help you find the safest route.
The user characteristics can define a variety of parameters for each road segment, and in each case a unique optimization system can be obtained. This approach enables you to solve non-standard problems of complex enterprise workflows.
The use of network analysis algorithms involves moving along the road network. But there are multiple moving types: you can move by car, truck, special vehicle, bicycle or just walk.
TrueDrive technology enables you to determine all types of vehicles at the stage of preparing the road graph index and to set different corrections for each type. This helps you determine which roads can drive all types of vehicles, and which can drive only cars, which roads can drive special vehicles only, and which can be used by public transport only.
For each moving type it is possible to set your own travel cost (for example, time) for each road segment. This cost, such as the travel time for the certain road segment, can be influenced by the length of the segment, the quality of the road surface, the slope, and other characteristics.
The moving type is set each time the network analysis algorithm is run. You can run several calculations at once using different settings, including specifying the type of vehicle.
After building the indexed road graph based on the source data, the set of road connectivity characteristics and their parameters are fixed. This enables you to create auxiliary data structures, the use of which significantly increases the calculation speed. The logical roads graph at the time of creation of the index structure becomes unchanged.
Often there are situations when certain road segments should be ignored, since traffic is prohibited (the road is blocked, repairs are underway, etc.). For such cases, the TrueDrive technology provides a specific ability of setting barriers.
Recalculation of found route by adding barrier
Barriers can be of point, polyline or polygon type. The point barriers snap to the nearest road segment and build the virtual barrier on that segment. The polyline barrier marks as impassable those segments that intersect with the given polyline. Same way, the polygon barriers mark those segments that fall completely or partially inside the polygon.
Barriers can be semi-transparent, i.e. not strictly prohibit traffic, but increase the travel time on the given segment. This mechanism enables you to define areas of unwanted presence. As a result, the network analysis algorithm would try to bypass the marked area until it becomes irrational. If such bypass is not possible or the bypass cost is too high considering the selected optimization, then the pass with minimal presence in the undesirable area is allowed.
The barrier transparency level is set by the penalty parameter with the following values:
- -1 – absolute barrier (traffic prohibited)
- 0 - instant teleportation (cost travel on segment is ignored)
- 0.5 - movement speed twice as fast
- 1 - no barrier
- 2 - movement speed twice as slow
Thus, setting barrier on the road can either completely prohibit traffic or reduce the passage priority on the given segment.
A special case is setting the penalty parameter in the range from 0 to 1. Values from this range allow, on the contrary, to increase the travel speed along the road segment. This possibility can be used in situations where road characteristics have been improved, for example, the asphalt pavement has been laid over the gravel embankment.
The use of barriers enables you to decrease dependance on the need to recalculate the road graph index, but with a significant increase in the number of specified barriers, it is worth changing the source road network data and recalculating the index file.
Peculiarities of passing crossroads
Each crossroad consists of several road segments converging at one point. While driving, the vehicle uses only two segments. The vehicle can go straight, turn right or left or make a U-turn.
The traffic rules may prohibit a certain type of maneuver at a given intersection. Most often, the left turns are prohibited. When building the road graph index, the TrueDrive technology enables you to set a list of road segments pairs, the passage between which is prohibited. The network analysis algorithm will consider this rule and will not allow you to build the route that includes such turn.
In addition, according to statistics, driving at different angles takes different time to pass the intersection. For example, driving straight ahead on average takes less time than turning left, since when turning you need to significantly reduce your speed, and only after passing the intersection you can speed up again.
TrueDrive enables you to take into account such turn circumstances. To do this, when building the road graph index, you should specify the desired deceleration parameters depending on angles of passing the intersection.
Optimal route search algorithm
The optimal route search algorithm is provided to calculate the route connecting several stopping points. As a result, the route will be calculated that enables you to travel from the start point to the end point in the minimum time/distance, passing through all intermediate points.
Calculation of optimal route with intermediate points
Intermediate points order
There are two optimization modes when specifying multiple stopping points to calculate the optimal route:
- Preserving the initial intermediate stops order
- Optimization of the initial intermediate stops order.
When choosing the mode of preserving the intermediate points order, the algorithm performs a sequential search for optimal routes between each of the neighboring stopping points. The output result is obtained by collecting all the parts into one route. Optimization of passing the intermediate points order is not done in this case.
If the mode of optimizing the intermediate points order is selected, then the optimal route search algorithm is used, considering all possible order combinations of the given stopping points. It should be taken into account that the calculation with the enabled mode of optimizing the order of intermediate points may be slower than the calculation with preserving the order of intermediate points.
In the algorithm for searching the optimal route from one city to another, in most cases, the main highways between cities are used. This is due to the fact that on highways the quality of roads and the average speed are higher, and the distance is shorter.
Normally, the optimal route search algorithm should process most of the indexed graph of roads connecting the specified stopping points. The analysis of many road branches does not lead to the best result, and in most cases such maneuvers can be neglected.
Calculation of optimal route without considering roads hierarchy (5-7 seconds)
TrueDrive offers the mode of calculating the optimal route based on the roads hierarchy. In this case, between cities (long sections), the subgraph consisting of only high-speed roads is used, and in the small radius of stopping points, the complete graph of roads is used.
Calculation of optimal route considering roads hierarchy (1-1,5 seconds)
The road hierarchy mode can significantly reduce the calculation time for long routes and provide more expected result for travel or long-distance transportation, in which traffic between cities mostly takes place on large highways, even though there may be a better route. Depending on the task and at the user’s discretion, you can turn on or off the mode of considering the roads hierarchy to find the most optimal route.
Building service areas algorithm
Algorithm of building service areas can be used when you need to define availability of service areas from specified centers (points) based on set time or distance.
The algorithm results can be used in a variety of tasks, for example, to determine the areas of likely presence of an ideal client (who is solvent and interested in the presented goods) or to determine city areas where emergency vehicles cannot reach within the prescribed standard time.
Building service areas (10, 15, 20 minutes)
Before starting the calculation of service areas, it is necessary to determine the number and threshold values of all the subareas (rings). As a result of the algorithm work, several nested polygons (service areas) are obtained, each of which corresponds to certain threshold value.
Thus, in one run of the algorithm, several service areas with different threshold values can be obtained at once, which can be analyzed separately or jointly.
Types of comparison of service areas of different points
To calculate service areas, you can specify several centers (points). In this case, the algorithm will build separate service area for each center, which will then be compared in a way determined before the algorithm launch. The following types of comparison of service areas of different points are available:
- Service areas of different points are independent of each other
- Combination of service areas of different points
- Competitive service areas
Independent service areas, combination of service areas, competitive service areas
When it is required not to mix the calculated service areas of different centers, the first type is used - without comparison. In this case, the user receives service areas for each center separately, moreover, the service areas of different centers can intersect and have common areas. This type of comparison can be used, for example, to determine the areas of responsibility of various municipal services.
In case when it is necessary to build a common service area for all centers at once, a combination of different services is used. This kind of comparison is helpful in tasks where the goal is to determine, for example, what part of a city is available for a service in a specified time.
The type of comparison "competitive zones" is used when in addition to determining the common service area it is necessary to distribute responsibility between different centers according to the selected criterion (time, distance). The result in this case will be similar to the "no comparison" option, except that the intersecting areas are divided between adjacent service areas in such a way that each resulting part has the nearest center corresponding to each service area.
TrueDrive is the software product using which the web service can be run. Interaction with the TrueDrive services can be implemented via direct network connection over HTTP/HTTPS protocols, via RESTful.
TrueDrive can be easily integrated to ecosystem of CoGIS infrastructure platform and is supported by all its clients. This enables you to extend functionality of geoinformation system based on CoGIS via network analysis algorithms.
TrueDrive web service can be integrated to CoGIS platform as following:
- By using TrueDrive services directly from CoGIS clients.
- By using TrueDrive functions as part of geoprocessing models within geoprocessing tools on a server side of the information system.
The external TrueDrive API works over the protocol compatible with Network Analyst Server, which allows to integrate TrueDrive to the ArcGIS Server based information systems.
The TrueDrive development technologies enable high performance and reliability of implemented solutions, do not impose restrictions on use and are cross-platform. For example, the TrueDrive core is written in C++, and the upper level TrueDrive logic in .NET Core (C#), ASP.NET Core.