High-performance Routing

Characteristic

Short description

High-performance routingClosed 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 profileClosed 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:

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.

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.

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:

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.

Limitations

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 polylineClosed 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.