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

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

Original Article

First Online: 

03 January 2014

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

• Hiroaki ShirasawaEmail author
• Hisashi Hasegawa

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