Time delayed discounted Steiner trees to locate two or more discounted Steiner points

Abstract

A discounted Steiner tree is a weighted Steiner tree in which the costs of constructing the edges and values at the nodes are discounted over time. Discounted Steiner points can be located to maximise the sum of the discounted cash flows, known as the net present value, and an algorithm for doing this for a single Steiner point, known as the discounted Steiner point algorithm, was previously established. An application of this problem is underground mine planning. This article proposes an algorithm to optimally locate two junction points, given a surface portal and three ore resource points, for maximum net present value, which includes the value of the ore bodies and the construction costs. The discounted Steiner point algorithm is extended to locate two junction points where time delays may occur at a discounted Steiner point before constructing the adjacent edges. The optimal locations of the junction points are obtained for a range of discount rates. Numerical trials show that this algorithm works well. A generalisation of the algorithm to locate more discounted Steiner points is also discussed. References

• E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM J. Appl. Math., 16(1):1–29, 1968. doi:10.1137/0116001.
• F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem. Elsevier, 1992. https://www.elsevier.com/books/the-steiner-tree-problem/hwang/978-0-444-89098-6.
• K. G. Sirinanda, M. Brazil, P. A. Grossman, J. H. Rubinstein, and D. A. Thomas. Optimally locating a junction point for an underground mine to maximise the net present value. ANZIAM J., 55:C315–C328, 2014. doi:10.21914/anziamj.v55i0.7791.
• K. G. Sirinanda, M. Brazil, P. A. Grossman, J. H. Rubinstein, and D. A. Thomas. Maximizing the net present value of a Steiner tree. J. Global Optim., 62(2):391–407, 2015. doi:10.1007/s10898-014-0246-3.