Новый алгоритм оптимизации дизайна транспортных сетей с учетом ограничений
DOI:
https://doi.org/10.26089/NumMet.v18r213Ключевые слова:
транспортные сети, задача Штейнера, алгоритмы на графах, оптимизация, задача с ограничениямиАннотация
Предложен эвристический алгоритм построения транспортной сети сбора оптимальной геометрии с ограничениями. Транспортная сеть представляется ориентированным взвешенным деревом Штейнера. Ограничения накладываются на максимальную суммарную длину участков коммуникаций от любой терминальной вершины до точки сбора. Учет ограничений происходит с помощью метода штрафных функций. Приведен анализ влияния параметров модели на оптимальную геометрию сети.
Библиографические ссылки
- 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).
- 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)].
- 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 - 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).
- 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).
- L. Gouveia, M. Leitner, and I. Ljubić, “Hop Constrained Steiner Trees with Multiple Root Nodes,” Eur. J. Oper. Res. 236 (1), 100-112 (2014).
- 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. - 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)].
- 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)].
Загрузки
Опубликован
24-04-2017
Как цитировать
Ананьев А., Ломовицкий П., Ужегов Д., Хлюпин А. Новый алгоритм оптимизации дизайна транспортных сетей с учетом ограничений // Вычислительные методы и программирование. 2017. 18. 158-168. doi 10.26089/NumMet.v18r213
Выпуск
Раздел
Раздел 1. Вычислительные методы и приложения
Лицензия
Copyright (c) 2017 Вычислительные методы и программирование
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
