KB10681 - Support for optimal routing, networking.

The routing/networking support in the TatukGIS DK and Internet Server products can be applied to vehicles on a road/street network represented by a topologically correct vector line layer as well as other situations, such as a water drainage system, liquid pipeline network, rail network, electrical power grid, etc. The support includes cost based routing between a starting point and termination point. When routing on a geocoded street map layer, the starting and termination points of the route can be defined by street addresses. For top performance even on huge datasets, the DK supports a persistent network so that the network need not be regenerated upon each route calculation request.

Assuming that a vector line layer reflects a projected geographic coordinate system (with measurement units), the length of each line segment between nodes (each link) corresponds to an 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.) By default, routes are calculated from distances only. The distances can modified with cost modifiers assigned to each link in the network, to apply a cost hierarchy across the entire network. Alternatively, it is possible for the cost factor for each link to be unrelated to distance, such as to represent throughput capacity, available capacity, time to traverse, degree of incline, pressure, resistance, etc. Cost factors reflect an attribute value or values associated with each link.

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 interstate highways (autobahn) might be 1, whereas the cost factor for common highways might be 1.2, for secondary roads 1.5, and for unpaved roads a cost factor of 2.5. In such an 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 to the attributes of the vector map layer(s ). 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. The difference between prohibited cost and high cost is high cost greatly discourages the use of that link (line segment) in the network whereas 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 high to discourage this behavior but not absolutely forbid it, 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 the use of a cost modifier array to allow 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 could fluctuate during the course of time. Another example might be a situations in which trucks are forbidden from using certain streets only 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 calculation of the optimum route for a given time.
• On demand link cost calculation. This would calculate the cost individually on each call for situations when parameters are changing dynamically. An example might be a road network or electrical power grid in which capacity utilization information is manually updated by the user or automatically updated from information provided by sensors at key positions along the network.

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 classes of roads. The user can adjust the relative preference for main or secondary roads on which the route is calculated.

For more on restricted turns, bridge and tunnel situations, etc., refer to knowledge base items KB10443, KB10442, and KB10276.

The functionality described in this KB item can also be implemented in the TatukGIS Editor product by using its built-in scripting features which expose the necessary functions in the DK API.