Page 1 of 1

Basics: Meaning of Static Routing

Posted: Tue Aug 21, 2018 3:14 pm
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 522 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