Marcus Brazil

A procedure is presented for finding the shortest network connecting three given undirected points, subject to a curvature constraint on both the path joining two of the points and the path that connects to the third point. The problem is a generalisation of the Fermat–Torricelli problem and is related to a shortest curvature-constrained path problem that was solved by Dubins. The procedure has the potential to be applied to the optimal design of decline networks in underground mines.

We introduce a formal framework for the study of augmenting networks in the plane for disaster‐resilience, where a disaster is modeled by a straight‐line segment. We generalize various graph structures from classical 2‐edge‐connectivity, including minimal cuts and blocks. The key concept that we introduce is that of an ‐leaf, which builds on the fundamental “leaf‐block” concept from classical augmentation. We present a number of algorithms for constructing the above‐mentioned graph structures, including a sweep‐line algorithm that finds all edge‐cuts that can be destroyed by a single disaster. We also present an algorithm which optimally adds a single edge between a pair of ‐leaves or blocks while avoiding certain disaster regions. Finally, we present a number of heuristic schemes for solving the disaster‐resilient network augmentation problem and perform extensive experiments to demonstrate the power of the ‐leaf concept within heuristic design.

The objective of this paper is to demonstrate that the gradient-constrained discounted Steiner point algorithm (GCDSPA) described in an earlier paper by the authors is applicable to a class of real mine planning problems, by using the algorithm to design a part of the underground access in the Rubicon gold mine near Kalgoorlie in Western Australia. The algorithm is used to design a decline connecting two ore bodies so as to maximize the net present value (NPV) associated with the connector. The connector is to break out from the access infrastructure of one ore body and extend to the other ore body. There is a junction on the connector where it splits in two near the second ore body. The GCDSPA is used to obtain the optimal location of the junction and the corresponding NPV. The result demonstrates that the GCDSPA can be used to solve certain problems in mine planning for which currently available methods cannot provide optimal solutions.

It is challenging to design large and low-cost communication networks. In this paper, we formulate this challenge as the prize-collecting Steiner Tree Problem (PCSTP). The objective is to minimize the costs of transmission routes and the disconnected monetary or informational profits. Initially, we note that the PCSTP is MAX SNP-hard. Then, we propose some post-processing techniques to improve suboptimal solutions to PCSTP. Based on these techniques, we propose two fast heuristic algorithms: the first one is a quasilinear time heuristic algorithm that is faster and consumes less memory than other algorithms; and the second one is an improvement of a state-of-the-art polynomial time heuristic algorithm that can find high-quality solutions at a speed that is only inferior to the first one. We demonstrate the competitiveness of our heuristic algorithms by comparing them with the state-of-the-art ones on the largest existing benchmark instances (169 800 vertices and 338 551 edges). Moreover, we generate new instances that are even larger (1 000 000 vertices and 10 000 000 edges) to further demonstrate their advantages in large networks. The state-of-the-art algorithms are too slow to find high-quality solutions for instances of this size, whereas our new heuristic algorithms can do this in around 6 to 45s on a personal computer. Ultimately, we apply our post-processing techniques to update the best-known solution for a notoriously difficult benchmark instance to show that they can improve near-optimal solutions to PCSTP. In conclusion, we demonstrate the usefulness of our heuristic algorithms and post-processing techniques for designing large and low-cost communication networks.

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.