Routing Algorithms

At the core of Pathfinder is a routing engine which calculates optimal paths given the constraints of the scenario.

Before using a routing algorithm, Pathfinder needs to create a Resistance Map, where all the layer resistances are combined into a single image. The resolution of this image is given by the project resolution.

Image source: Geography, Remote Sensing and GIS lesson – LyfSkill, Universität zu Köln.

The Routing Problem

The goal of all routing algorithms is to find paths traversing the resistance map from the Start point to the End point (possibly with some intermediate points), so that the sum of all the resistances along the way is minimized.

The results of the routing algorithms are:

• A corridor map raster summarizing where optimal paths might be located.

• One or more polygonal lines describing the optimal paths.

Algorithm Choices

Depending on your company license, more than one routing algorithm may be available. In the scenario settings panel it is possible to choose the algorithm among the available ones.

Fast Single Path

This is the default option and the fastest to compute. It generates a single optimal path per scenario by finding the least resistance route in the corridor map, therefore, crossing the lightest areas in that map.

Advanced Single Path

This option is equivalent to the previous Fast Single Path and it probably will not be available for most customers. It’s only used for testing.

Advanced Multiple Paths

This version of the algorithm generates multiple possible paths which are local resistance optima. The resulting paths are significantly different between them and can be used to analyze alternative routing solutions.

In this case, multiple paths are shown in the Results/Path section of the right panel, each one with its own cost estimation, and can be colored and displayed separately.

Pylon Optimization (Beta)

The advanced single and multiple path routing algorithms have additional versions which optimize the pylon/tower location and angles for power transmission applications, so that pylons are actually placed in least-resistance locations and large angles are avoided.

With these algorithms we can configure options to achieve the desired effect:

• Balance the relative importance of the edge resistance compared to the resistance at pylon locations.

• Balance the relative importance of the angle minimization compared to the resistance minimization.

• Control how much the path can deviate from the straight line going from Start to End.

• Set a maximum angle between previous and following wires at any pylon.

• Allow jumps over forbidden areas.

Note

The default settings may disable the angle optimization. If you want to use this feature check with your administrator that appropriate options are set in the algorithm configuration.

As an example, compare these results (the parameters must be set in the pylon siting options):

Note

Because of the additional resources required to run this algorithm, it may fail in large projects. We recommend to reduce as much as possible the difference between the minimum and maximum pylon distances.

Pathfinder Explore algorithm (Beta)

Pathfinder 3.2 includes a new multipath algorithm which can be used like the standard routing algorithms, and also to solve specific problems like combined overhead-tunnel routing (see below).

Some advantages of this algorithm are:

• Small memory footprint and great performance with large areas.

• Generation of many alternative routes. By default this number is six, but in some cases (see the Tunneling geoprocess) can be configured.

• Extensible with complex geometric and multi-map constraints. Because the resistance evaluation (cost function) is clearly separated from the algorithm engine, the Explore algorithm can be extended to take into account specific geometric criteria (e.g. slope limits or advanced crossings constraints) and to use multiple resistance maps as input, describing alternate costs for different technologies used, so the most appropriate can be chosen for each route segment.

Compare the results of the Fast, Pylon Spotting and Explore algorithms.

You are welcome to try this new routing method and give us your feedback.

Forbidden Areas

The use of Forbidden areas is an important feature of Pathfinder’s optimization algorithms. However, they must be used carefully, because the strong constraints they impose on the path search.

As we can see in the next images, algorithms will avoid forbidden areas (see North detour), unless there is no other choice than crossing them to find a path (see South area).

Usually, the path may cross a forbidden area, as long as the pylons are located outside:

If we need to prevent strictly the path from crossing forbidden areas, we must use the algorithms including pylon spotting, disabling the “between points allowed” choice in the advanced options.

Note

Advanced algorithms with pylong spotting (in beta) may fail when trying to find an optimal path with forbidden areas. Sudden turns are not handled well.

Note

It is recommended to avoid forbidden areas for large linear features like highways, rivers, etc. Use a large resistance value instead.

Pros and Cons

The following table summarizes some of the pros and cons of using each algorithm:

Algorithm comparison

Algorithm	Performance	Optimizations	Suggested for
Gilytics fast	Fast, quite lean.	Total resistance. Avoids FB areas but “cuts corners”.	Quick results, strict bundling, single solution per scenario.
Pylon spotting	Slow, memory limitations with large projects.	Total resistance. Pylon location. Angle constraints. FB constraints.	Precise pylon constraints in smaller projects.
Explore	Fast and lean.	Total resistance. Relaxed pylon, angle and FB constraints. “Corridor width” option.	Large projects. Multiple path options. Used by combined routing geoprocesses.

Regarding the reversibility of the results when swapping the Start and End points, see this note.

---

Disclaimer: the scenarios depicted in this manual do not represent actual customer projects or infrastructure proposals, and are presented for demonstration purposes only.

For more help, please use the help chat in the application, or contact Gilytics.