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.

Basics: Meaning of Static Routing

Postby Bernd Welter » Tue Aug 21, 2018 3:14 pm

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 47 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.
  • xml code
    <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)
  • xml code
    <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.
    xml code
    <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.
  • 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 Wed Feb 06, 2019 8:17 am, edited 1 time in total.
Reason: Added NC description
Bernd Welter
Manager Technical Consulting & Requirement Engineering
Senior Technical Consultant Developer Components
PTV GROUP - Germany

Bernd at Youtube
User avatar
Bernd Welter
Site Admin
 
Posts: 1275
Joined: Mon Apr 14, 2014 10:28 am

Return to PTV xRouteServer

cron