Monday, 28 November 2016

A comparative study of heuristic algorithms for the multiple target access problem

Published Date
Volume 19, Issue 5, pp 437–449


Original Article
DOI: 10.1007/s10310-013-0432-z

Cite this article as: 
Shirasawa, H. & Hasegawa, H. J For Res (2014) 19: 437. doi:10.1007/s10310-013-0432-z

Author
Abstract

Through computational experiments, we conducted a comparative study of the performance of heuristic algorithms for the multiple target access problem (MTAP). MTAP requires the minimum cost road network accessible to given targets on forest land to be designed via the construction of new roads from existing road networks. We first show that MTAP can be transformed into the Steiner tree problem (STP) in graph theory, by identifying nodes representing existing road networks. This allows us to use STP algorithms for solving MTAP. Because of NP-hardness of STP, we apply heuristic algorithms in this study. In our computational experiments, each of 14 heuristic STP algorithms, of which many have the performance guarantee of twice the optimal, solves 1,120 MTAP instances with various properties. Upon analysis of the results, we conclude that the average distance heuristic (ADH) and repetitive applications of the shortest path heuristic (SPH-V, SPH- Z, SPH-zZ, and SPH-ZZ) exhibit consistently superior performance in terms of solution quality. Additionally, we confirm that ADH, SPH-V, and SPH-ZZ design similarly shaped road network layouts.

References 

  1. Akay AE, Sessions J (2005) Applying the decision support system, TRACER, to forest road design. West J Appl For 20:184–191Google Scholar
  2. Anderson AE, Nelson J (2004) Projecting vector-based road networks with a shortest path algorithm. Can J For Res 34:1444–1457, doi:10.1139/x04-030CrossRefGoogle Scholar
  3. Aruga K, Sessions J, Akay AE (2005) Application of an airborne laser scanner to forest road design with accurate earthwork volumes. J For Res 10:113–123. doi:10.1007/s10310-004-0116-9 (ISSN 1341–6979)CrossRefGoogle Scholar
  4. Bondy J, Murty U (2008) Graph theory (Graduate Texts in Mathematics vol 244), volume 244 of Graduate Texts in Mathematics. Springer, New YorkGoogle Scholar
  5. Chen N (1983) New algorithms for Steiner tree on graphs. In: Proceedings of the IEEE International Symposium on Circuits and Systems, 1217–1219
  6. Chung W, Sessions J (2001) Designing a forest road network using heuristic optimization techniques. In: MWJ Wang and J McNeel (Eds.) Proceedings of the 24th Meeting of the Council of Forest Engineering Snowshoe, Wyo, 15-19 July
  7. Chung W, Sessions J, Heinimann H (2004) An application of a heuristic network algorithm to cable logging layout design. Int J For Eng 15:11–24Google Scholar
  8. Chung W, Stückelberger J, Aruga K, Cundy TW (2008) Forest road network design using a trade-off analysis between skidding and road construction costs. Can J For Res 38:439–448. doi:10.1139/X07-170CrossRefGoogle Scholar
  9. Church RL, Murray AT, Weintraub A (1998) Locational issues in forest management. Locat Sci 6:137–153. doi:10.1016/S0966-8349(98)00051-5 (ISSN 0966–8349)CrossRefGoogle Scholar
  10. Dean DJ (1997) Finding optimal routes for networks of harvest site access roads using GIS-based techniques. Can J For Res 27:11–22. doi:10.1139/x96-144CrossRefGoogle Scholar
  11. Duin CW, Volgenant A (1989) Reduction tests for the steiner problem in grapsh. Networks 19:549–567. doi:10.1002/net.3230190506CrossRefGoogle Scholar
  12. Esbensen H (1995) Computing near-optimal solutions to the steiner problem in a graph using a genetic algorithm. Networks 26:173–185. doi:10.1002/net.3230260403 (ISSN 1097–0037)CrossRefGoogle Scholar
  13. Feremans C, Labbé M, Laporte G (2003) Generalized network design problems. Eur J Oper Res 148:1–13. doi:10.1016/S0377-2217(02)00404-(ISSN 0377–2217)CrossRefGoogle Scholar
  14. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of Np-completeness. Freeman, San Francisco (ISBN 9780716710455)Google Scholar
  15. Geospatial Information Authority of Japan (2012) Fundamental geospatial data [online]. http://www.gsi.go.jp/kiban/index.html. Accessed 20 Aug 2013
  16. Gucinski H, Furniss M, Ziemer R, Brookes M (2001) Forest roads: a synthesis of scientific information. Technical report, USDA Forest Service, PortlandGoogle Scholar
  17. Hwang FK, Richards DS, Winter P (1992) The Steiner tree problem (annals of discrete mathematics), North-Holland, Amsterdam. (ISBN 9780444890986)
  18. Koch T, Martin A, Voß S (2013) SteinLib: an updated library on Steiner tree problems in graphs, tech. Rep. ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, Berlin, 2000. http://elib.zib.de/steinlib. Accessed 20 Aug
  19. Kou L, Markowsky G, Berman L (1981) A fast algorithm for Steiner trees. Acta Inform 15:141–145. doi:10.1007/BF00288961 (ISSN 0001–5903)CrossRefGoogle Scholar
  20. Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48–50CrossRefGoogle Scholar
  21. Legues AD, Ferland JA, Ribeiro CC, Vera JR, Weintraub A (2007) A tabu search approach for solving a difficult forest harvesting machine location problem. Eur J Oper Res 179:788–805. doi:10.1016/j.ejor.2005.03.071 (ISSN 0377-2217)CrossRefGoogle Scholar
  22. Liu K, Sessions J (1993) Preliminary planning of road systems using digital terrain models. Int J For Eng 4:27–32Google Scholar
  23. Meignan D, Frayret J-M, Pesant G, Blouin M (2012) A heuristic approach to automated forest road location. Can J For Res 42:2130–2141, doi:10.1139/x2012-140CrossRefGoogle Scholar
  24. Murray A (1998) Route planning for harvest site access. Can J For Res 28:1084–1087, doi:10.1139/x98-122CrossRefGoogle Scholar
  25. Picard N, Gazull L, Freycon V (2006) Finding optimal routes for harvesting tree access. Int J For Eng 17:35–49Google Scholar
  26. Polzin T (2003) Algorithms for the Steiner problem in networks. PhD thesis, Universität des Saarlandes
  27. Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401CrossRefGoogle Scholar
  28. Rayward-Smith V (1983) The computation of nearly minimal Steiner trees in graphs. Internat. Internat J Math Ed Sci Tech 14:15–23, doi:10.1080/0020739830140103CrossRefGoogle Scholar
  29. Rayward-Smith VJ, Clare A (1986) On finding steiner vertices. Networks 16:283–294. doi:10.1002/net.3230160305 (ISSN 1097–0037)CrossRefGoogle Scholar
  30. Richey MB, Parker RG (1986) On multiple steiner subgraph problems. Networks 16:423–438. doi:10.1002/net.3230160408 (ISSN 1097–0037)CrossRefGoogle Scholar
  31. Stückelberger J, Heinimann H, Chung W (2004) Improving the effectiveness of automatic grid cell based road route location procedures. In: Clark M (Ed) Proceedings of the 12th International Mountain Logging Conference, pp 13–16
  32. Stückelberger J, Heinimann H, Burlet E (2006) Modeling spatial variability in the life-cycle costs of low-volume forest roads. Eur J For Res 125:377–390. doi:10.1007/s10342-006-0123-9 (ISSN 1612–4669)CrossRefGoogle Scholar
  33. Stückelberger J, Heinimann HR, Chung W (2007) Improved road network design models with the consideration of various link patterns and road design elements. Can J For Res 37:2281–2298, doi:10.1139/X07-036CrossRefGoogle Scholar
  34. Takahashi H, Matsuyama A (1980) An approximate solution for the Steiner problem in graphs. Math Jap 24:573–577Google Scholar
  35. Talbi E-G (2009) Metaheuristics: from design to implementation, 1st edn. Wiley, New JerseyCrossRefGoogle Scholar
  36. Tan J (1999) Locating forest roads by a spatial and heuristic procedure using microcomputers. Int J For Eng 10:91–100Google Scholar
  37. The Mathworks (2013) Parallel Computing Toolbox. http://www.mathworks.com/products/parallel-computing/. Accessed 20 Aug 2013
  38. Voß S (1992) Steiner’s problem in graphs: heuristic methods. Discrete Appl Math 40:45–72. doi:10.1016/0166-218X(92)90021-2 (ISSN 0166–218X)CrossRefGoogle Scholar
  39. Voß S (2006) Steiner tree problems in telecommunications. In: Resende MGC, Pardalos PM (Eds) Handbook of optimization in telecommunications. Springer, New York, pp 459–492CrossRefGoogle Scholar
  40. Wang S (1985) A multiple source algorithm for suboptimum Steiner trees in graphs. In: Noltemeier H (Ed) Proceedings of International Workshop on Graphtheoretic Concepts in Computer Science, Trauner, Würzburg, pp 387–396
  41. Weintraub A, Murray AT (2006) Review of combinatorial problems induced by spatial forest harvesting planning. Discrete Appl Math 154:867–879. doi:10.1016/j.dam.2005.05.025(ISSN 0166–218X)CrossRefGoogle Scholar
  42. Winter P, Smith JM (1992) Path-distance heuristics for the Steiner problem in undirected networks. Algorithmica 7:309–327. doi:10.1007/BF01758765 (ISSN 0178–4617)CrossRefGoogle Scholar
  43. Wong R (1984) A dual ascent approach for steiner tree problems on a directed graph. Math Program 28:271–287. doi:10.1007/BF02612335 (ISSN 0025–5610)CrossRefGoogle Scholar
  44. Wright PH (1996) Highway engineering, 6th edn. Wiley, New YorkGoogle Scholar

For further details log on website :
http://link.springer.com/article/10.1007/s10310-014-0450-5

No comments:

Post a Comment