Knowledge Base



KB10879 - Hints for effective optimal routing.

TGIS_ShortestPath is an effective way for finding the shortest path between any two points in a network. Achieving best performance, however, can require additional steps.
Shape length calculations
Diagnosis
  • By default all length calculations are performed using TGIS_ShortestPath.RoadLength=GIS_LENGTH. Because the GIS_LENGTH virtual attribute is calculated dynamically using the TGIS_Shape.LengthCS method, it is not the fastest method (particularly if using the Transverse Mercator projection).
Recommendation
  • Store pre-computed length as an attribute field and provide it to .RoadLength.
  • A computed route between two points contains the shape .Uid as well as computed values for .RoadLength and .RoadName. Speed can be increased by setting .RoadLength='' and .RoadName='' just before calling .Find() (so it will not affect persistent network generation). This is particularly useful on batch calculations and you can always compute those values on your own. (Implemented in build .10363).
Heuristic optimization
Diagnosis
 
  • Heuristic optimization (TGIS_ShortestPath.HeuristicCostModifier) is by default zero, which means it is disabled. The general formula for cost modifier will be an average cost for traversing in a straight (as the crow flies) line between the currently evaluated node and the end node. HeuristicCostModifier will be treated as a multiplier for straight distance expressed in meters (for layers with a proper Coordinate System only!).

Recommendation
 
  • Under normal circumstances, HeuristicCostModifier=1 will deliver a significant speed gain. However, it uses the projection code inside.
  • If a layer is stored in a meaningful projection (with layer units in meters and not degrees), HeuristicCostModifier can be set to a negative value to turn on projection code to use a simple point-to-point distance calculation. But in this case, be sure that the units used for length (see point "Shape length calculations") matches the units used for heuristic cost calculations. In other words, if your map is in feet, then stay with feet.
Dynamic routing
Diagnosis
 
  • Routing stores a persistent network on the disk. Upon the network generation process, events .OnLinkType and .OnLinkCost are raised to allow user defined cost calculations. These events are not called upon actual routing!

Recommendation
 
  • Use .OnLinkDynamic event to temporarily modify network behavior.
  • Use .CostModifiers to change the performance of a particular road type as set by .OnLinkType. Suppose a category is defined for local streets. You can change .CostModifiers to provide different performance during traffic rush hours.

Other hints
Use TGIS_ShortestPath.Find() instead of the obsolete .StartPos() and .EndPos() routines.

 

Created: April 26, 2012, Modified: May 01, 2012
follow us on Facebook  follow us on Twitter  follow us on Google +  follow us on LinkedIn  Embarcadero