The Obstacle-Avoiding Rectilinear-Link Steiner Minimum Tree Problem: applications to the design of transportation networks.

M. Rodríguez-Madrena, M. Labbé, J. Puerto

In this work we consider the Steiner minimum tree problem (SMTP) in any real space of finite dimension endowed with the Manhattan-Link metric where there exist obstacles. These regions (the obstacles) are assumed to be polyhedral. We present a reduction result that transforms the original continuous problem into the Steiner minimum tree problem on an "ad hoc" graph, where the problem can be solved using the state-of-the-art solvers for the discrete version of the SMTP. We show that, fixed the dimension of the space, the reduction can be done in polynomial time. We report some applications of the planar version of this problem to the design of transportation networks. Moreover, some preliminary computational experiments show the usefulness of our approach.

Keywords: Location with obstacles Network optimization Finite dominating sets

Á. Marín Gracia, L. F. Escudero, L. Cadarso

E. Conde Sánchez, M. Leal Palazón, J. Puerto Albandoz

F. Perea Rojas-Marcos, R. Ruiz, L. Fanjul