Basics: Meaning of Static Routing

Bernd Welter · Post by **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 669 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 Name	Value	Description
NC_0	MOTORWAY	Motorways
NC_1	HIGHWAY	Highways
NC_2	TRUNK_ROAD	Truck roads
NC_3	COUNTRY_ROAD	Country roads
NC_4	CITY_ROAD	City roads
NC_5	RESIDENTIAL_ROAD	Residential roads
NC_6	SPECIAL_ROAD	Drivable but normally blocked roads (for cars).
NC_7	CYCLE_AND_WAYLKWAY	Cycle 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
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