Построение кратчайшей сети дорог на однородной территории с использованием трехточечной задачи Штейнера (на примере Чистопольского района Республики Татарстан)
Исавнин А.Г.доктор физико-математических наук, профессор кафедры математических методов в экономике, Набережночелнинский институт (филиал) Казанского (Приволжского), федерального университета, Набережные Челны, Российская Федерация isavnin@mail.ru
Шарипов Р.Ш.аспирант кафедры производственного менеджмента, Набережночелнинский институт (филиал) Казанского (Приволжского) федерального университета, Набережные Челны, Российская Федерация radik@sharipov.com
Предмет/тема. Статья посвящена проблеме соединения нескольких населенных пунктов системой дорог таким образом, чтобы по этим дорогам можно было из каждого пункта добраться в любой другой, причем длина пути должна быть минимальной. Рассмотрена возможность соединения ряда населенных пунктов Чистопольского района Республики Татарстан кратчайшей сетью дорог на основе трехточечной задачи Штейнера. Цели/задачи. Целью статьи является практическое применение задачи Штейнера в разработке и построении сетей кратчайших дорог на однородной территории на примере нескольких населенных пунктов Чистопольского района Республики Татарстан. Методология. Исследование проведено с помощью трехточечной задачи Штейнера. Результаты. Рассмотрена возможность практического использования задачи Штейнера при проектировании и реконструкции автомобильных дорог, получена новая сеть дорог минимальной длины. Для примера рассмотрено соединение нескольких населенных пунктов Чистопольского района Республики Татарстан (с. Старое Иванаево, с. Белая Гора и пос. Николаевка). Обоснована экономия бюджетных средств за счет сокращения длины пути и уменьшения затрат на дорожное строительство. Доказано, что такая экономия будет способствовать увеличению количества соединенных населенных пунктов с общей сетью автомобильных дорог при том же финансировании. Выводы/значимость. Сделан вывод о том, что применение трехточечной задачи Штейнера при проектировании и реконструкции автомобильных дорог на однородной территории позволяет значительно сократить объемы строительных работ, уменьшить длину пути между населенными пунктами, сократить время прохождения участка, что будет способствовать развитию транспортного потенциала региона.
Ключевые слова: задача Штейнера, точки Штейнера, однородная территория, проектирование дорог, трехточечная задача, сокращение длины пути
Список литературы:
Халтурин Р.А. Состояние и опыт строительства дорожной сети в России и за рубежом // Экономические науки. 2011. № 74. С. 223–226.
Лотарев Д.Т. Неформальные описательные модели транспортных коммуникаций, транспортных сетей и территорий в задаче прокладки путей и коммуникаций // Труды Института системного анализа Российской академии наук. 2009. Т. 46. С. 259–273.
Лотарев Д.Т., Уздемир А.П. Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе // Автоматика и телемеханика. 2005. № 10. С. 80–92.
Melzak Z.A. On the problem of Steiner // Canadian Mathematical Bulletin. 1961. Vol. 4. P. 143–148.
Протасов В.Ю. Максимумы и минимумы в геометрии. М.: МЦНМО, 2005. 56 с.
Романовский И.В. Задача Штейнера на графах и динамическое программирование // Компьютерные инструменты в образовании. 2004. № 2. С. 80–86.
Иванов А.О., Тужилин А.А. Задача Штейнера на плоскости или плоские минимальные сети // Математический сборник. 1991. Т. 182. № 12. С. 1813–1844.
Gilbert E.N., Pollak H.O. Steiner minimal trees // SIAM Journal of Applied Mathematics. 1968. Vol. 16. № 1. P. 1–29.
Garey M.R., Graham R.L., Johnson D.S. The complexity of computing Steiner minimal trees // SIAM Journal of Applied Mathematics. 1977. Vol. 32. № 4. P. 835–859.
Препарата Ф., Шеймос М. Вычислительная геометрия. Введение: монография. М.: Мир, 1989. 478 с.
Herring M. The euclidean Steiner tree problem. Ohio: Denison University, 2004. 11 p.
Warme D., Winter P., Zachariasen M. Exact algorithms for plane Steiner tree problems: a computational study. Denmark: University of Copenhagen, 1998. P. 81–116.
Курант Р., Роббинс Г. Что такое математика? Элементарный очерк идей и методов. М.: МЦНМО, 2001. 568 с.
Andreescu T., Mushkarov O., Stoyanov L. Geometric problems on maxima and minima. Boston: Birkhauser, 2006. 272 p.
Гордеев Э.Н., Тарасцов О.Г. Задача Штейнера. Обзор // Дискретная математика. 1993. Т. 5. № 2. С. 3–28.
Hwang F.K. On Steiner minimal trees with rectilinear distance // SIAM Journal of Applied Mathematics. 1976. Vol. 30. № 1. P. 104–114.
Ермолаев О.П. Ландшафты Республики Татарстан. Региональный ланшафтно-экологический анализ: монография. Казань: Слово, 2007. 411 с.
Hwang F.K., Richards D.S., Winter P. The Steiner tree problem: monograph. Netherlands: Elsevier Science Publishers, 1992. 336 p.
Cockayne E.J. On the Steiner problem // Canadian Mathematical Bulletin. 1967. Vol. 10. № 3. P. 431–450.
Cheng X., Du D.-Z. Steiner Trees in Industry. Netherlands: Springer Science & Business Media, 2001. 507 p.
