Distance Matrices
Characteristic
Short description
With distance matrices it is possible to access, store and calculate
- driving distance,
- driving time,
- additional flags and optional further contents
for every relation between two locations.
Use
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.
Detailed Consideration
Internal Structure of Distance Matrices
Distance matrices are organized in columns and rows, squared and rectangular matrices are possible.
Destination 1 | Destination 2 | Destination 3 | |
---|---|---|---|
Origin 1 | distance/time/etc. | distance/time/etc. | distance/time/etc. |
Origin 2 | distance/time/etc. | distance/time/etc. | distance/time/etc. |
General Behavior of Distance Matrices
In general routed 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. 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:
- Detour factor: A factor that describes the average detour an actual route on the road requires, compared to the geographical distance.
- Average speed: The average speed of 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.. It is used to estimate the travel time.
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.
Algorithms of Distance Matrices
The PTV xDima service provides two different algorithms to calculate distance matrices:
- A high-performance routing based on a contraction hierarchies algorithm and
- A conventional routing calculation based on Dijkstra's algorithm.
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 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. 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 xDima service
The PTV xDima service provides the following services to calculate and manage distance matrices:
- Create distance matrices by entering locations.
- Access either single elements of a distance matrix or slices of the distance matrix. A textual or a binary encoded version of the response is available.
- List distance matrices.
- Delete distance matrice.
- Import distance matrices: Check the documentation of the ImportDistanceMatrixRequest for further details. Toll costs can not be imported. It is possible to provide the contents in the encoded format. There is an integration sample on how to decode the encoded contents which should give you an idea how to encode your data.
- Update distance matrices. Either using ExtendDistanceMatrixRequest which calculates the new relations or using ExtendDistanceMatrixWithContentsRequest where the contents are specified. To import very big matrices, it could be useful to combine ImportDistanceMatrixRequest and ExtendDistanceMatrixWithContentsRequest.
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.
Accessing the distance matrix contents using the binary encoded version
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:
byte_{1} | byte_{2} | byte_{3} | byte_{4} | byte_{5} | byte_{6} | byte_{7} | byte_{8} | ... | byte_{n-3} | byte_{n-2} | byte_{n-1} | byte_{n} | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
unsigned integer_{1} | unsigned integer_{2} | ... | unsigned integer_{k} | ||||||||||
Distances | 1^{st} distance | 2^{nd} distance | ... | k^{th} distance | |||||||||
Travel Times | 1^{st} time | 2^{nd} time | ... | k^{th} time | |||||||||
Toll Costs | 1^{st} toll cost | 2^{nd} toll cost | ... | k^{th} toll cost |
The violated and estimated by direct distance flags are returned as contiguous arrays of bytes. Each byte codes up to 8 flags:
byte_{1} | byte_{2} | ... | byte_{n} | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
bit_{1} | bit_{2} | bit_{3} | bit_{4} | bit_{5} | bit_{6} | bit_{7} | bit_{8} | bit_{1} | bit_{2} | bit_{3} | bit_{4} | ... | ... | ... | bit_{5} | bit_{6} | bit_{7} | bit_{8} | |
Violated | 1^{st} flag | 2^{nd} flag | 3^{rd} flag | 4^{th} flag | 5^{th} flag | 6^{th} flag | 7^{th} flag | 8^{th} flag | 9^{th} flag | 10^{th} flag | 11^{th} flag | 12^{th} flag | ... | ... | ... | k-3^{th} flag | k-2^{th} flag | k-1^{th} flag | k^{th} flag |
Estimated By Direct Distance | 1^{st} flag | 2^{nd} flag | 3^{rd} flag | 4^{th} flag | 5^{th} flag | 6^{th} flag | 7^{th} flag | 8^{th} flag | 9^{th} flag | 10^{th} flag | 11^{th} flag | 12^{th} flag | ... | ... | ... | k-3^{th} flag | k-2^{th} flag | k-1^{th} flag | k^{th} flag |
Note
- k stands for the number of distance matrix relations which have been requested
- n stands for the number of bytes necessary to hold the response
Multiple Travel Times Distance Matrix
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.
To create a Multiple Travel Times Distance Matrix, it is necessary to define the multiple travel times consideration scenario with a horizon.
Then, it is possible to interact with such matrix by two means (that are mutually exclusive):
- Querying a specific start time within the horizon. In this case the returned travel time is interpolated using the nearest values.
- Querying the complete travel time profile. A piecewise function is then returned having the time on the abscissa and the corresponding travel time on the ordinate.
Please note that due to size considerations only a binary encoded version is offered for this access.The travel time profiles are returned in a compact form as a contiguous array of bytes with the following memory layout (each unsigned integer uses either a 2 or 4-bytes little endian scheme):
4 bytes 1 byte 2 bytes 2 bytes ... 2 bytes 2 bytes ... 4 bytes 1 byte 2 bytes 2 bytes ... 2 bytes 2 bytes Travel Time Profiles minTravelTime_{1} n_{1} x_{1,1} y_{1,1} ... x_{1,n1} y_{1,n1} ... minTravelTime_{k} n_{k} x_{k,1} y_{k,1} ... x_{k,nk} y_{k,nk} travelTimeProfile_{1} ... travelTimeProfile_{k} Note
- k stands for the number of distance matrix relations which have been requested
- n_{i} stands for the number of pairs (x,y) returned for the i^{th} function
- minTravelTime_{i} is the minimum travel time expressed in milliseconds of the i^{th} function
- The x value is expressed as an offset in minutes from the start time of the horizon.
- The y value is expressed as an offset in seconds from the minimum travel time of the function.
high-performance routing
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 parameters used to calculate the high-performance routing network will be applied.
However, to offer more flexibility, it is possible to override the parameters in MultipleTravelTimesConsideration:
- the horizon ; 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
- the feature layer themes ; for example, you might want to apply PTV_SpeedPatterns on a high-performance routing network which was not calculated with
Usage of Distance Matrices in PTV optimization services
All PTV xServer optimization services offer the possibility to choose between the following options:
- Use existing distance matrix: A distance matrix created and maintained by the xDima service is used. It is addressed by a unique identifier.
- Direct distance calculation: Estimated distance using the parameters detour factor and average speed. This mode does not require a prior creation of a distance matrix using the xDima service.
Good to know
Time Dependency
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.
- Snapshot mode
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.
- Multiple travel times mode
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.
Automatic removal of unused distance matrices
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
core.distanceMatrixCleanupEnabled
to 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.
Network file systems for the storage of distance matrices
The parameter 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.
Related Topics
Showcase | Compare xdima and xroute results |
Showcase | Consider Multiple Travel Times Matrices |
Integration Sample | Managing Distance Matrices |
Integration Sample | Import and Update Distance Matrix |
Integration Sample | Accessing Distance Matrix Contents with Binary Encoded Arrays |
Integration Sample | Retrieving Travel Times from a Multiple Travel Times Distance Matrix |
Integration Sample | How to Plan Tours using a Distance Matrix |