High-performance Routing

This Technical Concept is relevant to the following Services: xDima, xRoute, xData.

Characteristic

Short description

High-performance routing A route corresponds to a path of a vehicle through the underlying transport network. The main attributes of a route are the distance and the time that the vehicle travels along the path. is based on precomputed routing networks for specific sets of routing relevant parameters. Because of this, high-performance routing is less flexible than conventional routing, but provides the following advantages:

The routing performance is usually much better, in particular for the xDima Service. A 1000x1000 matrix can be computed in a few seconds.
The algorithm is exact and thus the results of high-performance routing are consistent over all xServer Services.

Use

The calculation of distance matrices with conventional routing is often slow. It can consume much more time than a subsequent optimization by xTour or xCluster. In particular for large distance matrices, high-performance routing is crucial to achieve an acceptable performance. For xRoute an important use case is the computation of the detailed route corresponding to a relation of a distance matrix. With high-performance routing this route has exactly the distance and travel time that is stored in the distance matrix. This is not always the case with conventional routing because of heuristics.

Detailed Consideration

Precomputed Routing Networks and Relevant Parameters

High-performance routing requires precomputed routing networks. Each edge of such a network represents a path in the map. Only the main attributes of these paths are stored: The distance, travel time, and the abstract cost used for route selection. Furthermore, the structure of the network depends on the cost of the edges. Because of this a high-performance routing network is valid only for one specific set of parameters. For example, it is not possible to use a different speed because the cost of some edges would be different and the whole routing network would be invalid.

The relevant parameters for high-performance routing are parameters of the profile A profile is a collection of parameters used to configure the request. Full profiles consist of a number of specialized sub-profiles like the VehicleProfile which describes the properties of a vehicle. and the request alike that have an influence on the precomputed networks. These parameters are stored as meta data of every high-performance routing network and can be retrieved through the xData operation listHighPerformanceRoutingNetworks when the corresponding result fields are activated. The relevant parameters can be found among:

the request profile: Parameters belonging to the category "highPerformanceRouting". Only the routingProfile, vehicleProfile, and featureLayerProfile have parameters of that category.
the geographic restrictions: Any restriction to use only parts of the map is relevant.
the time consideration mode: All time consideration scenarios are relevant. Note that the exact time consideration is not supported by high-performance routing.
the content snapshot id: A content snapshot influences the state of the map concerning dynamic data like traffic incidents, hence it also influences the high-performance routing network.

Management of High-performance Routing Networks

It is possible that the map provides already high-performance routing networks. They can be listed by the xData module.

Listing: The operation listHighPerformanceRoutingNetworks returns all available networks along with the relevant parameters. It is also possible to request only certain networks by their ids. Also the user data monitor of the xServer dashboard uses this operation to show the available networks.

Additionally, the user can create new high-performance routing networks. These user-created networks can also be deleted (map-provided networks cannot be deleted). The create and delete operations require an activated license key highPerformanceRoutingManagement and are located in the xData module.

Generation: In a CreateHighPerformanceRoutingNetworkRequest all the parameters such as the vehicle The term vehicle describes what is being routed or planned for. Vehicles are used in route calculation, distance matrix calculation and effectively also in tour planning. In route calculation, vehicle properties like overall size, weight and speed are in focus. In tour planning, it is vehicle properties like capacity and availability. Commonly a vehicle is motorized, like a truck - including its trailer or a car. However also a bike or even a pedestrian are included in this definition. profile, the routing profile, the time consideration scenario and the geographic restrictions have to be set. This request can be submitted with startCreateHighPerformanceRoutingNetwork which will trigger the creation. As the creation may take a considerable amount of time this operation is asynchronous only and provides a job object which can be used to query the progress and to fetch the response. The response contains the id of the generated network.
Removal: A user-created high-performance routing network can be deleted using the operation deleteHighPerformanceRoutingNetwork. The input to this operation is the id of the network to be deleted.

Usage of High-performance Routing

In order to use high-performance routing in xDima or xRoute an activated license key highPerformanceRouting is required and the routing type has to be set to one of the following two high-performance routing types. In both cases it is checked if the routing relevant parameters of the request match the corresponding parameters of one of the available high-performance networks. For user-created networks also the combination of tenant and scope used to create the network has to be set. If a suitable high-performance routing network is found it will be used for routing. The difference of the two high-performance routing types is the treatment of the case when no matching high-performance routing network is available:

HIGH_PERFORMANCE_ROUTING_WITH_FALLBACK_CONVENTIONAL: Conventional routing will be used as fall-back. The effectively used routing type is returned as part of the response (distance matrix summary and route report).
HIGH_PERFORMANCE_ROUTING: An exception is returned.

With API version 2.13 a direct selection mechanism has been introduced: As part of the route options the id of a high-performance routing network can be specified. This id must be set in combination with the routing type HIGH_PERFORMANCE_ROUTING (other routing types will return an exception). If the high-performance routing network is not available, an exception is returned. The profile and request parameters from the meta information of the high-performance routing network are used for linking and routing. Since API version 2.18, this mechanism is also available for the calculation of a distance matrix by specifying the id of a high-performance routing network in the distance matrix options.

Troubleshooting

In case a high-performance routing network is not used most likely one of the relevant routing parameters of the request is not the same as the ones in the high-performance routing networks.

Check the routing relevant parameters of the high-performance routing network, which can be retrieved through the xData module as described above.
Another possibility is to enable the trace logs of the corresponding service. Then, for each high-performance routing network the parameters that are different to the routing relevant parameters of the request are logged. To not spam your module log files with too many entries, it is sufficient to set a specific channel to trace, care for the following snippet for the logging-module.xml file:
```
<Logger name="com.ptvgroup.xserver.xroute.router.ContractionHierarchiesTools" level="trace" additivity="false">
    <AppenderRef ref="File"/>
</Logger>
```
If you are using xdima you have to replace "xroute" with "xdima" in the name of the logger. You can also add both loggers.
As of xServer release 2.8 a new routing profile parameter highPerformanceRoutingUTurnCost has been introduced for high-performance routing contexts. Existing high-performance routing networks are still compatible: Just set the new parameter to the value which was used to create the high-performance routing network. If the routing type is set to HIGH_PERFORMANCE_ROUTING_WITH_FALLBACK_CONVENTIONAL and the fallback is taken, then the value of uTurnCost is used.

Limitations

The major limitation of high-performance routing is the strong dependency of each routing network to one specific set of routing relevant parameters. A routing network can be used only if exactly the same routing relevant parameters are set in the request.
Another limitation is caused by the mere size of the precomputed data. A routing network for a whole continent can require several gigabytes of space, a world map requires 10 or more gigabytes.
Exact time-consideration is not supported by high-performance routing.

Good to know

xRoute Performance

The major performance improvement of high-performance routing is achieved for the xDima service. However, also the performance of the xRoute service can benefit, depending on the request settings. The xRoute service consists of several parts. First, a basic routing is done which calculates only the distance and travel time. Then, if requested, the path has to be constructed with the detailed polyline A polyline is a continuous line composed of one or more line segments given as a set of tuples with x,y and optional z coordinates., segment attributes are retrieved from the map, emissions and toll prices are calculated, etc. With high-performance routing only the performance of the first basic routing part is improved. Hence, there will be only a big speed-up compared to conventional routing when no additional result fields are requested. Otherwise the subsequent steps dominate the xRoute calculation time.

Usage of High-performance Routing Networks and Main Memory

The best performance is achieved if the whole high-performance routing network is already available in the main memory. The xServer services access the data using memory-mapped files. If the data is not yet available in main memory the part that is required is automatically loaded from the storage device, which is usually quite slow compared to a main memory access. In particular for the xRoute service this may cause a longer runtime with high-performance routing compared to conventional routing.

The high-performance routing networks in main memory are shared among all xServer and all their services. This is ensured by the memory-mapped files technique that is used for data access. Even if the size of the data is part of the size of each module's process there is in fact only one instance of it in main memory.

Generation of High-performance Routing Networks and Main Memory

The field highPerformanceRoutingUTurnCost has an impact on the memory requirement. For large networks a value of 500 is recommended.
With large maps the creation requires at least 32 GB (continent-sized maps) or 64 GB (world maps) of main memory along with a page file or swap partition of similar size.
Geographic restrictions can be used to create high-performance routing networks for certain parts of a map. This reduces the memory requirements accordingly.
Parallel creation of large high-performance routing networks can be problematic since each instance requires its own memory. There are possibilities for administrators to ensure that only one creation is running at the same time:
- Run only one instance of xData in the xServer. The drawback of this solution is that during the creation no other xData operation can be used. See the services configuration documentation.
- Run a separate xServer that is responsible only for creation of high-performance routing networks with one xData module.

Automatic removal of unused high-performance routing networks

By default PTV xServer stores all high-performance routing networks on the server side regardless of whether they are used or not. By setting the configuration option core.highPerformanceRoutingNetworkCleanupEnabled to true an automatic removal of unused high-performance routing networks can be enabled. The time to live for unused high-performance routing networks can be specified with the second option core.highPerformanceRoutingNetworkRetentionTime. The default value is seven days.

Integration Sample	How to Retrieve the Available Metainformation in the Map
Integration Sample	High-performance Routing
Technical Concept	Multitenancy
Technical Concept	Route Selection
Showcase	Compare xDima and xRoute Results