A new algorithm for the optimization of transport networks subject to constraints


  • A.A. Ananev Center for engineering and technology of MIPT
  • P.V. Lomovitskiy Center for engineering and technology of MIPT
  • D.V. Uzhegov Center for engineering and technology of MIPT
  • A.N. Khlyupin Center for engineering and technology of MIPT




transport networks, Steiner problem, graph algorithms, optimization, constrained problems


A new heuristic algorithm of finding a minimum weighted Steiner tree is proposed. A transport network can be represented in the form of a directed weighted Steiner tree. Constraints are imposed on the maximal total length of communications from any terminal vertex to the root of the tree. A penalty function method is used to take the constraints into account. The effect of model parameters on the optimal network geometry is analyzed.

Author Biographies

A.A. Ananev

P.V. Lomovitskiy

D.V. Uzhegov

A.N. Khlyupin


  1. G. Xue, T. P. Lillys, and D. E. Dougherty, “Computing the Minimum Cost Pipe Network Interconnecting One Sink and Many Sources,” SIAM J. Optim. 10 (1), 22-42 (1999).
  2. D. T. Lotarev, A. V. Suprun, and A. P. Uzdemir, “Local Optimization in the Steiner Problem on the Euclidean Plane,” Avtom. Telemekh., No. 7, 60-70 (2004) [Autom. Rem. Contr. 65 (7), 1089-1098 (2004)].
  3. Q. Xia, “Numerical Simulation of Optimal Transport Paths,” in Proc. Second Int. Conf. on Computer Modeling and Simulation, Sanya, China, January 22-24, 2010 (IEEE Press, Washington, DC, 2010),
    doi 10.1109/ICCMS.2010.30
  4. A. M. Costa, J.-F. Cordeau, and G. Laporte, “Fast Heuristics for the Steiner Tree Problem with Revenues, Budget and Hop Constraints,” Eur. J. Oper. Res. 190 (1), 68-78 (2008).
  5. M. Sinnl and I. Ljubić, “A Node-Based Layered Graph Approach for the Steiner Tree Problem with Revenues, Budget and Hop-Constraints,” Math. Prog. Comput. 8 (4), 461-490 (2016).
  6. L. Gouveia, M. Leitner, and I. Ljubić, “Hop Constrained Steiner Trees with Multiple Root Nodes,” Eur. J. Oper. Res. 236 (1), 100-112 (2014).
  7. A. G. Trifonov, Formulation of the Optimization Problem and Numerical Methods of Its Solution ,
    http://matlab.exponenta.ru/optimiz/book_2/index.php . Cited April 24, 2017.
  8. D. T. Lotarev and A. P. Uzdemir, “Location of Transport Nets on a Heterogeneous Territory,” Avtom. Telemekh., No. 7, 117-127 (2002) [Autom. Rem. Contr. 63 (7), 1146-1154 (2002)].
  9. D. T. Lotarev and A. P. Uzdemir, “Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph,” Avtom. Telemekh., No. 10, 80-92 (2005) [Autom. Rem. Contr. 66 (10), 1603-1613 (2005)].



How to Cite

Ананьев А., Ломовицкий П., Ужегов Д., Хлюпин А. A New Algorithm for the Optimization of Transport Networks Subject to Constraints // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2017. 18. 158-168. doi 10.26089/NumMet.v18r213



Section 1. Numerical methods and applications