"A new algorithm for the optimization of transport networks subject to constraints"
Ananev A.A., Lomovitskiy P.V., Uzhegov D.V., and Khlyupin A.N.

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.

Keywords: transport networks, Steiner problem, graph algorithms, optimization, constrained problems.

  • Ananev A.A. – Moscow Institute of Physics and Technology Center for Engineering and Technology; ulitsa Pervomayskaya 5, Dolgoprudny, 141700, Russia; Engineer, e-mail: ananev.aa@cet-mipt.ru
  • Lomovitskiy P.V. – Moscow Institute of Physics and Technology Center for Engineering and Technology; ulitsa Pervomayskaya 5, Dolgoprudny, 141700, Russia; Engineer, e-mail: lomovitskiy.pv@cet-mipt.ru
  • Uzhegov D.V. – Moscow Institute of Physics and Technology Center for Engineering and Technology; ulitsa Pervomayskaya 5, Dolgoprudny, 141700, Russia; Engineer, e-mail: uzhegov.dv@cet-mipt.ru
  • Khlyupin A.N. – Moscow Institute of Physics and Technology Center for Engineering and Technology; ulitsa Pervomayskaya 5, Dolgoprudny, 141700, Russia; Head of Research Group, e-mail: khlyupin.an@cet-mipt.ru