Matrix routing effect due to category scope (LEVELLING)

This forum deals with any kind of routing computation whether it is simple A:B-routing, calculation of isochrones, simple matrix computation or nearest search.
Post Reply
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Matrix routing effect due to category scope (LEVELLING)

Post by Bernd Welter »

HI there,

today I was asked for the reason why a relation (A=>B1)'s routing result differs within a matrix routing if another waypoint B2 is added to the calculateMatrixInfo request.
In other words:
The client computed the two transactions based on
A : (B1)
A : (B1,B2)
and compared the partial results of the (A:B1) which differed.

I created some images that explain what causes this behaviour which occurs whenever a routing is based on levelling (uses the category scope):
Imagine the calculation with just the two waypoints A and B1. In the proximity of both waypoints the temporary data structures used to calculate the track contain a detailed streetnetwork but outside the circles the temporary network is based on NC0, NC1, NC2 only. SO outside the cirles the vehicle moves on higher street categories. The  yellow polygon shows the geometry of the result track
Imagine the calculation with just the two waypoints A and B1. In the proximity of both waypoints the temporary data structures used to calculate the track contain a detailed streetnetwork but outside the circles the temporary network is based on NC0, NC1, NC2 only. SO outside the cirles the vehicle moves on higher street categories. The yellow polygon shows the geometry of the result track
By adding the B2 and it's proximity area the temporary structures are different from those used in the previous scenario and therefor the algorithm finds additional opportunities to get from A to B1. The solution is the greeen line.
By adding the B2 and it's proximity area the temporary structures are different from those used in the previous scenario and therefor the algorithm finds additional opportunities to get from A to B1. The solution is the greeen line.
This image just shows both solutions at one glance. As you can see the green track is a bit shorter.
This image just shows both solutions at one glance. As you can see the green track is a bit shorter.
To avoid such a behaviour you could ether set the category scope of all NC's to -1, but keep in mind:
  • bad impact on performance because many more segments have to be evaluated
  • maybe tracks returned you don't want to (would you really want to leave the highway in the middle of a 600km route just to save 1-2 km of total distance?)
This effect does not occur when you apply search graph routing because this mechanism is so incredibly fast that it does no longer require leveling.

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