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

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.

Keywords:

• Forest road network
• Graph theory
• Network design
• Steiner tree