What is a distance matrix (used for)?

deals with computation of distance matrices
Post Reply
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

What is a distance matrix (used for)?

Post by Bernd Welter »

Hi there,

imagine you want to perform an optimization task such as
  • Planning a fleet of 20 trucks dealing with 2000 orders the next few days
  • Parcel delivery (B2B): Sequencing of a city depot's trucks one by one with hundreds of daily orders (business customers)
  • Strategic field service optimization (planning scope 3 months or even more) of service technicians who deal with thousands of geolocated service tasks...
  • Dozends of sales reps travelling through the area visiting thousands of customers in the next months
  • and many other usecases...
In each one of those usecases the driving times and distances between hundreds of locations are required.
Question: Would you recalculate those relation KPIs each and every time you do a planning with slightly different parameters? Hopefully not! You'd try to reuse them if possible.

And here's why and how:
Most xServer methods create a result within the server, the result is returned to the client and no longer stored on the client side. While this works fine for usecases such as geocoding, simple routing and mapping other usecases are more complex and require data to be stored on the server to achieve a better performance during succeeding requests.
One typical example is tour optimization:
  • During the process of the optimization of hundreds of locations L[0], L[1], ...L[n] the driving times (L,L[j]) and distances(L,L[j]) are required thousands or even millions of times and this is why precompute the square schema of n² relations and store it for the repeated access to those values.
  • Imagine a user who wants to perform several optimization calls with the same locations (or maybe a subset of them) by simply changing a few parameters such as
    • operating times of vehicles
    • fleetsize (e.g. as a reaction of unscheduled orders)
    • planning horizon (e.g. daily planning of the next day)
    • ...
  • In each one of those scenarios the required distances and periods are constant and theres a big potential in saving computation time by reusing the values once they have been calculated.
  • This is why we store such information in a so-called distance matrix (DIMA) which is represented by a simple file folder on the servers disk space. The files in that folder contain the routing profile (each distance matrices content is based on one single routing profile), the list of involved coordinates and the driving times and distances.
  • Besides the initial creation of such a dima space the dima components offer highly efficient mechanisms to extend and reuse distance matrices if needed while they ensure that no CPU (and time) is wasted for waiting on unrequired output.
  • For the curious ones: if the number of locations involved is higher than e.g. 200 the filespace is dominated by the distance matrix table file as you can compute the space (at least xServer 1) via n² * 6 bytes.
    file sizes of distance matrices between 1'000 and 10'000 locations (=up to 100'000'000 relations!)
    file sizes of distance matrices between 1'000 and 10'000 locations (=up to 100'000'000 relations!)
  • Further info is available at the regular usecase documentation of xDima
Best regards,
Bernd
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
Post Reply