Distance Matrices

This Technical Concept is relevant to the following Services: xDima, xTour, xCluster.

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 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:

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 vehicleThe 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 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 xDima service

The PTV xDima service provides the following services to calculate and manage distance matrices:

Create and update 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 and delete distance matrices.
Import distance matrices (planned for a future version of the xDima service).

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₁	byte₅	...	byte_n-3
	unsigned integer₁	unsigned integer₂	...	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₁								byte₂					...	byte_n
	bit₁	bit₂	bit₃	bit₄	bit₅	bit₆	bit₇	bit₈	bit₁	bit₂	bit₃	bit₄	...	...	...	bit₅	bit₆	bit₇	bit₈
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.
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.

To define a Multiple Travel Times Distance Matrix: it is mandatory to set the multiple travel times consideration scenario with a horizon.
To query a Multiple Travel Times Distance Matrix: a start time (the date/time to estimate the travel time) has to be provided.

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.

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.

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