Determining an optimal path for forest road construction using Dijkstra’s algorithm

https://doi.org/10.17221/9/2016-JFSCitation:Parsakhoo A., Jajouzadeh M. (2016): Determining an optimal path for forest road construction using Dijkstra’s algorithm. J. For. Sci., 62: 264-268.
download PDF
From an economic point of view a well-designed road path with the minimum construction cost is an optimal path that can be found using Dijkstra’s algorithm. In this study Dijkstra’s algorithm that consisted of nodes and links was used to optimize the road path in a broadleaved forest. The lower the cost, the greater the chance that the link will get routed. The road construction cost depends on the length of links, longitudinal gradient of links, side slope of the terrain and unit cost of the link construction. In general, the construction cost of each link increased with increasing length of the link, side slope gradient and longitudinal gradient. The total length and mean construction cost of optimal path were 530 m and 18.18 USD·m–1, respectively. Based on the analysis, we found that Dijkstra’s algorithm is feasible in selecting an optimal path according to the construction cost of forest road.
References:
Ahuja Ravindra K., Mehlhorn Kurt, Orlin James, Tarjan Robert E. (): Faster algorithms for the shortest path problem. Journal of the ACM, 37, 213-223  https://doi.org/10.1145/77600.77615
 
Akbarimehr M., Naghdi R. (2012): Determination of most appropriate distance between water diversions on skid trails in the mountainous forest, north of Iran. CATENA, 88, 68-72  https://doi.org/10.1016/j.catena.2011.08.005
 
Cheng Min-Yuan, Chang Guey-Lin (2001): Automating utility route design and planning through GIS. Automation in Construction, 10, 507-516  https://doi.org/10.1016/S0926-5805(00)00103-5
 
Contreras Marco, Chung Woodam (2007): A computer approach to finding an optimal log landing location and analyzing influencing factors for ground-based timber harvesting. Canadian Journal of Forest Research, 37, 276-292  https://doi.org/10.1139/x06-219
 
Devlin Ger J., McDonnell Kevin, Ward Shane (2008): Timber haulage routing in Ireland: an analysis using GIS and GPS. Journal of Transport Geography, 16, 63-72  https://doi.org/10.1016/j.jtrangeo.2007.01.008
 
Dijkstra E. W. (1959): A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269-271  https://doi.org/10.1007/BF01386390
 
Heralt L. (2002): Using the ROADENG system to design an optimum forest road variant aimed at the minimization of negative impacts on the natural environment. Journal of Forest Science, 48: 361–365.
 
Ilayaraja K. (2013): Road network analysis in Neyveli Township, Cuddalore District by using Quantum GIS. Indian Journal of Computer Science and Engineering, 4: 56–61.
 
Kaufman David E., Smith Robert L. (1993): FASTEST PATHS IN TIME-DEPENDENT NETWORKS FOR INTELLIGENT VEHICLE-HIGHWAY SYSTEMS APPLICATION∗. I V H S Journal, 1, 1-11  https://doi.org/10.1080/10248079308903779
 
Kooshki M., Hayati E., Rafatnia N., Taghi Ahmadi M. (2012): Using GIS to evaluate and design skid trails for forest products. Taiwan Journal of Forest Science, 27: 117–124.
 
Möhring R.H., Schilling H., Schütz B., Wagner D., Willhalm T. (2006): Partitioning graphs to speedup Dijkstra’s algorithm. ACM Journal of Experimental Algorithmics, 11: 2–8.
 
Rees W.G. (2004): Least-cost paths in mountainous terrain. Computers & Geosciences, 30: 203–209.
 
Rogers L.W. (2005): Automating contour-based route projection for preliminary forest road designs using GIS. [MSc Thesis.] Seattle, University of Washington: 78.
 
Tavankar F. (2013): Effect of forest management on density and species diversity of natural regeneration in Hyrcanian lowland forests, north of Iran. International Journal of Agriculture and Crop Sciences, 5: 1941–1945.
 
Wang Zheng, Crowcroft Jon (1992): Analysis of shortest-path routing algorithms in a dynamic network environment. ACM SIGCOMM Computer Communication Review, 22, 63-71  https://doi.org/10.1145/141800.141805
 
Wang Z., Zlatanova S., Moreno A., Oosterom P., Toro C. (2014): A data model for route planning in the case of forest fires. Computers & Geosciences, 68: 1–10.
 
Xie Feng, Levinson David (2007): Measuring the Structure of Road Networks. Geographical Analysis, 39, 336-356  https://doi.org/10.1111/j.1538-4632.2007.00707.x
 
Zhan F. Benjamin, Noon Charles E. (1998): Shortest Path Algorithms: An Evaluation Using Real Road Networks. Transportation Science, 32, 65-73  https://doi.org/10.1287/trsc.32.1.65
 
download PDF

© 2020 Czech Academy of Agricultural Sciences