Knowledge Base

KB10681 - Support for optimal routing, networking.

The routing/networking support in the TatukGIS Developer Kernel and desktop GIS Editor products can be used for vehicle routing on complex road and street networks and for other network situations such as involving water drainage systems, liquids pipelines, rail track networks, electrical power grids, etc. Top route calculation performance, even with huge datasets, is enabled by support for a persistent network - so that the network need not be regenerated upon each new route calculation request. Route calculations require the network be represented by topologically correct vector line layers.

Routing is cost based, between a starting point and a termination point. When routing on a geocoded street map layer, the route starting and termination points can be defined by street addresses. By default, routes are calculated based on distances. With a vector line layer in a projected coordinate system (one with measurement units), the length of each line segment between nodes (each link) corresponds to the actual distance on the ground. (Nodes are normally at the line intersections, but can also be applied at places on a line where there is no intersection.) Distances can be modified using cost modifiers, which are recorded as attribute values. Cost modifiers can be applied individually to each link or as a cost hierarchy across an entire network. The cost factor for each link can be unrelated to distance, such as to represent throughput capacity (such as in pipes), available capacity, time to traverse, degree of incline, pressure, resistance, etc.

Cost modifiers can be applied in the following ways:

  • Link cost (for each direction separately), using the DK OnLinkCost event. Cost factors can be coded to the attribute fields of each link individually, or programmatically based on vector classes which are coded to the vector attributes. For instance, the cost factor for an interstate highway (autobahn) might be 1, whereas the cost factor for a common highway might be 1.2, for a secondary road 1.5, and for an unpaved road a cost factor of 2.5. In this example, the interstate highway route would have to be at least 2.5 times longer than the unpaved road route for the unpaved route to be selected as the optimal route. Alternatively, the cost factors can reflect speed limits of each road segment, assuming that this information is available and coded as layer attributes. Special cost factors might be assigned to unusual links in the network, such as toll bridges, tunnels, or a particularly poorly maintained or dangerous road segments.
  • Prohibited cost links. Whereas high cost greatly discourages the use of that link (line segment) in the network, prohibited cost absolutely forbids the use of the link. An example would be an emergency response or police vehicle traveling in the wrong direction on a one-way street. The cost should be set to a high level to highly discourage this behavior but not absolutely forbidden (because other costs, i.e., the delay in reaching the point of the emergency, could be even higher).
  • Link cost modifier to reflect preferences using the DK OnLinkType event. This concept in based on use of a cost modifier array to enable the user to easily and quickly modify the assignment of cost factors dynamically across the entire network. Typical examples are "time to traverse" and length/distance based modification. Using the road network example, this would allow a user to modify the relative preference for or against certain types of roads (interstate highways, secondary roads, scenic routes, etc.) in the calculation of the optimum route. For a pipeline network or electricity grid, the cost factor might reflect free (available) capacity of each pipeline or transmission line segment, which may fluctuate with time. Another example might be a situations in which trucks are forbidden from certain streets during specified hours of the day, or emergency vehicle routing that considers the time-of-day or day-of-week traffic congestion cycles in the optimal route calculation.
  • On demand link cost calculation. This re-calculates the costs on each call with the cost parameters updating dynamically. An example might be a road network or electrical power grid in which capacity utilization information is automatically updated from sensors at key positions along the network.
  • Heuristic cost modification. Heuristic cost calculations use a built-in heuristic cost algorithm to prioritize route possibilities based on a preference for the "as the crow flies" direction toward the route destination. Lower heuristic value settings mean slower but deeper path searching and a potentially more accurate result. Higher value settings mean faster but less deep path searching and acceptance of a greater risk of a worse than optimum result. A setting of 0 turns off the heuristic cost modifier.

The Geocoding source code sample found in DK Sample Set #2 demonstrates road routing functionality on a TIGER vector street/road map, with link cost routing based on two road classes - main and secondary. The relative preference for main versus secondary roads can be manipulated to see the effect of the cost setting on the route calculation.

For more on turn restrictions, bridges, overpasses, tunnels and similar situations, refer to knowledge base items KB10443, KB10442, and KB10276. Knowledge base item KB10879 offers some specific tips for effective optimal routing implementation. Knowledge base item KB10791 provides guidance on support for road/street map data of leading vendors.

The functionality described in the knowledge base item can be implemented in the TatukGIS Editor product using its built-in pascal/basic scripting environment which exposes the required networking related properties and functions from the DK object API.

Created: February 24, 2006, Modified: September 12, 2017
follow us on Facebook  follow us on Twitter  follow us on Google +  follow us on LinkedIn  Embarcadero