Determining an optimal path for forest road construction using Dijkstra’s algorithm
A. Parsakhoo, M. Jajouzadehhttps://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.
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.Keywords:
selecting path; nodes; links; Nahar Khvoran forestReferences:
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.77615Akbarimehr 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.005Cheng 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-5Contreras 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-219Devlin 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.008Dijkstra E. W. (1959): A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269-271 https://doi.org/10.1007/BF01386390Heralt 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/10248079308903779Kooshki 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.141805Wang 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.xZhan 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