DOI: https://doi.org/10.26089/NumMet.v18r213

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

Authors

  • A.A. Ananev
  • P.V. Lomovitskiy
  • D.V. Uzhegov
  • A.N. Khlyupin

Keywords:

transport networks
Steiner problem
graph algorithms
optimization
constrained problems

Abstract

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.

New computational technologies

Downloads

Published

2017-04-24

Issue

Vol. 18 (2017): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biographies

A.A. Ananev

Center for engineering and technology of MIPT
• Engineer

P.V. Lomovitskiy

Center for engineering and technology of MIPT
• Engineer

D.V. Uzhegov

Center for engineering and technology of MIPT
• Engineer

A.N. Khlyupin

Center for engineering and technology of MIPT
• Research Team Leader

References

  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)].

License

Copyright (c) 2017 Вычислительные методы и программирование

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.