НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o144.pdf (1002.12Кб)

УДК 519.87+519.6+681.324

1 Россия,  Институт вычислительной математики и математической геофизики СО РАН

В работе рассматривается задачи оптимизации структуры инженерных сетей обеспечивающей минимальную суммарную стоимость строительства и эксплуатации инженерных сетей. Приведена математическая постановка задачи на языке теории гиперсетей учитывающая взаимозависимость показателей элементов, область размещения и проектируемую сеть. Область размещения инженерной сети (территория) представлена цифровой моделью местности, в нашем случае, это будет взвешенная решетка (граф первичной сети) с выделенными вершинами-потребителями и вершиной-источником для данной инженерной коммуникации. Веса ребер будут определяться затратами на строительство и эксплуатацию трассы между заданными вершинами сети. В качестве начального решения задачи минимизации суммарных затрат будем использовать минимальное покрывающее дерево, полученное на взвешенном полном  графе, вершины которого представляют собой заданные вершины-потребители и вершина-источник для данной инженерной коммуникации, а веса ребер - расстояния между заданными вершинами на взвешенном графе первичной сети. Предложен метод дифференциальной эволюции для решения задачи в гиперсетевой постановке, который позволяет улучшить первоначального решения путем отображения ребер вторичной сети в первичную сеть с использованием дополнительных точек Штейнера. Как показали вычислительные эксперименты, используемый алгоритм дифференциальной эволюции позволяет  сократить в среднем суммарные затраты для заданной инженерной сети по сравнению с начальным решением на 5% - 15%, в зависимости от конфигурации, параметров и области размещения.

1. Ловягин В.Ф. Геоинформационные технологии в инженерных изысканиях трасс линейных сооружений. Новосибирск: СГГА, 2010. 153 с.
2. Райфельд В.Ф. Инженерно-геодезические работы при изысканиях линейных сооружений. М.: Недра, 1983. 143 с.
3. Попков В.К. Математические модели связности / отв. ред. А. С. Алексеев. 2-е изд. Новосибирск: ИВМиМГ СО РАН, 2006. 490 с.
4. Попков В.К., Токтошов Г.Ы., Юргенсон А.Н. Об одном подходе к оптимизации инфраструктуры инженерных сетей // Вестник СибГУТИ. 2012. № 3. С. 11-28.
5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: пер. с англ. М .: Мир , 1982. 416 с . [Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Co., 1979.].
6. Storn R., Price K. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces // Journal of Global Optimization. 1997. Vol . 11, no . 4. P . 341-359. DOI: 10.1023/A:1008202821328
7. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с .
8. Zaheer H., Pant M., Kumar S., Monakhov O., Monakhova E., Deep K. A new guiding force strategy for differential evolution // International Journal of System Assurance Engineering and Management. 2015. Vol. 6. P . 1-14. DOI: 10.1007/s13198-014-0322-6
9. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: пер. с англ . 2- е изд .  М .: Вильямс , 2006. 1296 с . [ Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms . 2^nd ed. MIT Press and McGraw-Hill, 2001.].