Новый алгоритм оптимизации дизайна транспортных сетей с учетом ограничений

Авторы

  • А.А. Ананьев Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
  • П.В. Ломовицкий Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
  • Д.В. Ужегов Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
  • А.Н. Хлюпин Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым

DOI:

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

Ключевые слова:

транспортные сети, задача Штейнера, алгоритмы на графах, оптимизация, задача с ограничениями

Аннотация

Предложен эвристический алгоритм построения транспортной сети сбора оптимальной геометрии с ограничениями. Транспортная сеть представляется ориентированным взвешенным деревом Штейнера. Ограничения накладываются на максимальную суммарную длину участков коммуникаций от любой терминальной вершины до точки сбора. Учет ограничений происходит с помощью метода штрафных функций. Приведен анализ влияния параметров модели на оптимальную геометрию сети.

Авторы

А.А. Ананьев

Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
Институтский пер., 9, 141701, Долгопрудный
• инженер

П.В. Ломовицкий

Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
Институтский пер., 9, 141701, Долгопрудный
• инженер

Д.В. Ужегов

Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
Институтский пер., 9, 141701, Долгопрудный
• инженер

А.Н. Хлюпин

Инжиниринговый центр МФТИ по трудноизвлекаемым полезным ископаемым
Институтский пер., 9, 141701, Долгопрудный
• руководитель исследовательской группы

Библиографические ссылки

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

Загрузки

Опубликован

24-04-2017

Как цитировать

Ананьев А., Ломовицкий П., Ужегов Д., Хлюпин А. Новый алгоритм оптимизации дизайна транспортных сетей с учетом ограничений // Вычислительные методы и программирование. 2017. 18. 158-168. doi 10.26089/NumMet.v18r213

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения