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

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:

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

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:

byte1 byte2 byte3 byte4 byte5 byte6 byte7 byte8 ... byten-3 byten-2 byten-1 byten
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:

byte1 byte2 ... byten
bit1 bit2 bit3 bit4 bit5 bit6 bit7 bit8 bit1 bit2 bit3 bit4 ... ... ... bit5 bit6 bit7 bit8
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

Note

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

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:

Anyway, in these cases you will be informed by a result limitation that overriding these parameters 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:

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.