A new algorithm to find raster-based least-cost paths using cut and fill operations

ABSTRACT

We developed a least-cost path analysis algorithm that satisfies a slope threshold condition in hilly terrain. The new algorithm uses an expanding moving-window to explore a combination of cells that satisfy an elevation threshold condition and then supplements this by executing cut and fill operations when there are obstacle cells between source and destination cells. Cut and fill factors regarding the difference in the actual elevation and revised elevation are considered and a least-cost path is analyzed after calculating the accumulated travel cost to the destination point. After applying the developed algorithm to synthetic and real-world data, the least accumulated travel cost from the source point can then be calculated for all cells on the raster surface by considering various slope thresholds, moving-window sizes and raster data resolutions. This algorithm can be implemented as a useful tool in GIS software as well as engineering design software utilized in the construction and mining industries.

KEYWORDS:

• Geographic Information Systems
• least-cost path analysis
• cut and fill operations
• earthwork costs
• digital elevation model

Acknowledgments

The authors thank Dr Shawn Laffan and anonymous peer reviewers, who provided useful comments that significantly improved our analysis and the final paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the Ministry of Trade, Industry and Energy [Korea Energy and Mineral Resources Engineering Program] and National Research Foundation of Korea [Basic Science Research Program/2015R1D1A1A010612].