Basics: Meaning of Static Routing

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:

Basics: Meaning of Static Routing

Post by Bernd Welter »

Hi there,

dealing with routing is a complex topic and if you want to understand our approaches we sometimes have to start from a very rough perspective: take a look at the attached slides…
xServer Workshop (BWE) 20131121_PTV_allgemein - Speed.pptx
Oldie but goldie!
(1.21 MiB) Downloaded 521 times
Update 5.9.2018: taken from the xServer2 documentation
TechnicalConcepts/Routing/DSC_RouteSelection.htm

And here: with my own words:
  • Depending on the category scope we also filter segments of network classes which are too far away from any waypoint. That's probably what you also apply when you drive from one big city to another big city: get out the city onto a major network. Reach for the destinations region. Deal with smaller roads in the destination area again.
  • Code: Select all

    <Algorithm aStarAggressiveness="1.3">
    <LevellingScopeByNetworkClass searchSpace="-1"/>
    <LevellingScopeByNetworkClass searchSpace="-1"/>
    <LevellingScopeByNetworkClass searchSpace="-1"/>
    <LevellingScopeByNetworkClass searchSpace="200"/>
    <LevellingScopeByNetworkClass searchSpace="20"/>
    <LevellingScopeByNetworkClass searchSpace="10"/>
    <LevellingScopeByNetworkClass searchSpace="10"/>
    <LevellingScopeByNetworkClass searchSpace="10"/>
    </Algorithm>
  • As each one of the 70 Million street segments (european city map) belongs to a unique NetworkClass and SpeedClass (info given by our providers) we can derive the current static speed based on the MIN versus MAX values on that NetworkClass (check SpeedRangeByNetworkClass). So while some German highways belong to Speedclass SC_0 (very fast) others are treated as slow highways (SC_7)
  • Code: Select all

    <Speed>
    	<SpeedRangeByNetworkClass minimumSpeed="70" maximumSpeed="135"/>
    	<SpeedRangeByNetworkClass minimumSpeed="35" maximumSpeed="125"/>
    	<SpeedRangeByNetworkClass minimumSpeed="25" maximumSpeed="85"/>
    	<SpeedRangeByNetworkClass minimumSpeed="25" maximumSpeed="60"/>
    	<SpeedRangeByNetworkClass minimumSpeed="20" maximumSpeed="50"/>
    	<SpeedRangeByNetworkClass minimumSpeed="18" maximumSpeed="40"/>
    	<SpeedRangeByNetworkClass minimumSpeed="9" maximumSpeed="16"/>
    	<SpeedRangeByNetworkClass minimumSpeed="4" maximumSpeed="6"/>
    </Speed>
    Enumerator NameValueDescription
    NC_0MOTORWAYMotorways
    NC_1HIGHWAYHighways
    NC_2TRUNK_ROADTruck roads
    NC_3COUNTRY_ROADCountry roads
    NC_4CITY_ROADCity roads
    NC_5RESIDENTIAL_ROADResidential roads
    NC_6SPECIAL_ROADDrivable but normally blocked roads (for cars).
    NC_7CYCLE_AND_WAYLKWAYCycle lanes and walkways
  • So we interpolate the speed of a relevant segment.
  • As we know the length of the relevant segments we can compute their individual required driving time.
  • Depending on your OPTIMIZATION preferences between distance (almost 0) and driving time (almost 100) we can compute somekind of an initial “price” of a segment.

    Code: Select all

    <Course distanceTimeWeighting="80" enforceShortestRoute="false">
  • Depending on further attributes of the segment (belongs to class HIGHWAY, has a specific Segment ID, …) we can add a penalty (aka MALUS) on the initial price. Here's an example of how we can apply the malus per NetworkClass:

    Code: Select all

    <Network rampMalus="10">
    	<MalusByNetworkClass malus="0"/>
    	<MalusByNetworkClass malus="0"/>
    	<MalusByNetworkClass malus="0"/>
    	<MalusByNetworkClass malus="0"/>
    	<MalusByNetworkClass malus="15"/>
    	<MalusByNetworkClass malus="50"/>
    	<MalusByNetworkClass malus="100"/>
    	<MalusByNetworkClass malus="100"/>
    </Network>
    This setting will apply a small malus of 15% on city roads, 50% on residential roads and so on. The upper network classes NC_0 to NC_3 aren't punished by this setting.
    S = Start   /   D = Destination<br />Depending on the malues values for the highlighted red parts of the route the blue detours are chosen or not.
    S = Start / D = Destination
    Depending on the malues values for the highlighted red parts of the route the blue detours are chosen or not.
  • Finally we determine the sequence of segments which link start to destination and produce the lowest sum of the penaltied prices. We might use traditional algorithms, e.g. Dijkstra or some other modern approaches such as High Performance Routing (based on Contraction Hierarchies which is in fact not using the category scope).
  • That’s routing!!
Best regards,
Bernd
Last edited by Bernd Welter on Fri Aug 26, 2022 12:57 pm, edited 3 times in total.
Reason: Added NC description
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