With distance matrices it is possible to access, store and calculate
for every relation between two locations.
Distance matrices are the basis for tour and cluster optimization. Tour and cluster optimization algorithms have to access these relations very frequently. Therefore PTV xServer provides optimized algorithms for the calculation and access of distance matrices.
Distance matrices are organized in columns and rows, squared and rectangular matrices are possible.
|Destination 1||Destination 2||Destination 3|
In general routedA 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. road distances are used to fill the distance matrix. If it is not possible to calculate a road distance an estimation based on the direct distance is used. The direct distance and estimated travel time is calculated from the geographical distance using the fields:
These fields are user provided in the request for the creation of the distance matrix. If a location not contained in the distance matrix is used to acquire distance and travel time an exception is thrown.
The PTV xDima service provides two different algorithms to calculate distance matrices:
Since distance matrices usually store a large number of relations, the PTV xDima service tries to load a high performance routing network matching the used profileA 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. by default. If no matching high performance network is available, the distance matrix will be calculated with PTV's accelerated version of the Dijkstra algorithm.
The PTV xDima service provides the following services to calculate and manage distance matrices:
Normally, distance matrices are stored on the server. The xDima service is the only way to create and manage distance matrices in PTV xServer. There is a single exception form this rule: The createAndGet request. Using this request a distance matrix is created in memory and immediately returned without persisting it on the server.
The PTV xDima service provides the possibility to return distance matrix contents as compact binary arrays. The benefits are important for large contents as it considerably reduces the size of the response.
The distances, travel times, and toll costs are returned as contiguous arrays of unsigned integers respectively in meters, milliseconds, and cents (hundredth of the currency). Each unsigned integer uses a 4-bytes little endian scheme:
|unsigned integer1||unsigned integer2||...||unsigned integerk|
|Distances||1st distance||2nd distance||...||kth distance|
|Travel Times||1st time||2nd time||...||kth time|
|Toll Costs||1st toll cost||2nd toll cost||...||kth toll cost|
The violated and estimated by direct distance flags are returned as contiguous arrays of bytes. Each byte codes up to 8 flags:
|Violated||1st flag||2nd flag||3rd flag||4th flag||5th flag||6th flag||7th flag||8th flag||9th flag||10th flag||11th flag||12th flag||...||...||...||k-3th flag||k-2th flag||k-1th flag||kth flag|
|Estimated By Direct Distance||1st flag||2nd flag||3rd flag||4th flag||5th flag||6th flag||7th flag||8th flag||9th flag||10th flag||11th flag||12th flag||...||...||...||k-3th flag||k-2th flag||k-1th flag||kth flag|
A Multiple Travel Times Distance Matrix contains several travel times for a relation within the given horizon.
The travel times are calculated on a static route considering the long-term blockings. Every single blocking -which is not valid for the whole horizon- is ignored when calculating the travel times.
It is possible to query the travel time for any start time within the horizon. Please note that the returned travel time is interpolated using the nearest values available in the matrix.
Additionally, it is possible to use high-performance routing to speed up the computation of such distance matrices as for regular ones.
Please note that If you specify explicitly an high-performance routing network id in the request, by default the horizon considered will be the one used for the creation of the high-performance routing network. However, it is possible to override it in the createDistanceMatrix request to offer more flexibility.
For example, you might want to calculate a network for a specific Monday and shift afterwards the horizon of the distance matrix to a different Monday to match your tour plan horizon.
Anyway, in this case you will be informed by a result limitation that using a different horizon could lead to less optimal results.
All PTV xServer optimization services offer the possibility to choose between the following options:
Travel times may change during the day due to congested roads. It is certainly desirable to take account of these effects during the creation of trips in xTour. But this comes has a cost.
In contrast to time-independent distance matrix, an xTour based on a snapshot distance matrix considers congestion if the reference time is well chosen (like in the middle of a rush hour).
If so chosen, roads are always assumed to be congested, even during the night. The space consumption remains the same as in the time-independent case and thus also the run-time of xTour.
In contrast to Snapshot, congestion is taken into account more realistically. It is considered that travel times change over the day.
However, the creation of the distance matrix takes longer and it uses 4 times more space. The trip planning becomes significantly more complex so it also affects the run-time of xTour.
For large distance matrices, the computation tend to be quite long. Under these circumstances, it could be a valuable approach to use high-performance routing in combination with this mode. Thus, prior to calculating the distance matrix, a high-performance routing network has to be calculated with the same options than for the distance matrix.
By default PTV xServer stores all distance matrices on the server side regardless of whether they are used or not. By setting the configuration option
true an automatic removal of unused distance matrices can be enabled. The time to live for unused
distance matrices can be specified with the second option
core.distanceMatrixRetentionTime. The default value is seven days.
core.distanceMatrixPath allows the administrator to set the storage of the distance matrices. If a network file system is chosen
it should be taken into account that the access of distance matrices could be slowed down. Especially the list functionality could be massively
decelerated. As a consequence timeouts may occur. The performance of the access to the contents of a distance matrix is usually acceptable because in
this case file access optimizations work in particular caching.
|Showcase||Compare xdima and xroute results|
|Showcase||Consider Multiple Travel Times Matrices|
|Integration Sample||Managing Distance Matrices|
|Integration Sample||Accessing Distance Matrix Contents with Binary Encoded Arrays|
|Integration Sample||How to Plan Tours using a Distance Matrix|