Distance Matrices

Characteristic

Detailed Consideration

Internal Structure of Distance Matrices

Distance matrices are organized in columns and rows, squared and rectangular matrices are possible.

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:

The violated and estimated by direct distance flags are returned as contiguous arrays of bytes. Each byte codes up to 8 flags:

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	minTravelTime1	n1	x1,1	y1,1	...	x1,n1	y1,n1	...	minTravelTimek	nk	xk,1	yk,1	...	xk,nk	yk,nk
  	travelTimeProfile1							...	travelTimeProfilek

  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

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:

• 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

Related Topics