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

作者：Baek Jieun; Choi Yosoon^*

来源：International Journal of Geographical Information Science, 2017, 31(11): 2234-2254.

DOI：10.1080/13658816.2017.1356463

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

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.

• 出版日期2017