How to Extend a Distance Matrix

If you have an already calculated distance matrix with a lot of locations required in future and at the same time some new locations that have to be considered additionally, it could be advantageous to extend the distance matrix. Extending the distance matrix case-by-case is better than calculating the complete distance matrix with all locations (old and new ones) again. Only the transferred locations and not all possible location pairs are considered for the routing calculation.

Here is an example. The distance table in a distance matrix is newly generated with the locations A, B and C.

In the second step, the distance table is extended with the locations B, D and E, so that the relevant values are newly calculated and the irrelevant values are identified. Please note that the locations A and C are not transferred in the request for calculating the distance table.

Example for a distance matrix extended to two more locations

LRU - Last Recently Used Mechanism

The size of a distance matrix is limited. If you try to extend a distance matrix, it is possible that you will exceed the maximum number of locations. The LRU mechanism (“last recently used”) ensures that the distance table in a distance matrix can only grow to the specified size in spite of constant extensions. The idea is that the locations which have not been used for the longest amount of time must be removed from the distance table.

Here is an example. The distance table in a distance matrix was generated with the locations A, B and C and may contain a maximum of five locations. In an extension, the distances and driving periods between the locations A, B and D are added. The location C was not used in the extension. Please note that the last row and column in the distance table does not exist at this point in time, but may exist potentially.

Example for a distance matrix extended to one more location

In the next extension of the distance table, the locations B, D, E and F have to be taken into account. As the six locations now exceed the permitted size of the distance table, the last recently used location is removed. In this example, the locations A and C are candidates for removal. Since location A was used in the last extension, location C is removed. The location E occupies the free space in the distance table and location F occupies the position of location C.

Example for the LRU mechanism

Copyright © 2024 PTV Logistics GmbH All rights reserved. | Imprint