Home  Journals  Regional Economics: Theory and Practice  24(399) - 2015 June

Building the shortest road network in homogeneous territories using the three-point Steiner tree problem (the Chistopolsky district of the Republic of Tatarstan case)

Vol. 13, Iss. 24, JUNE 2015

Article PDF Version

Available online: 29 June 2015

Subject Heading: ECONOMIC-MATHEMATICAL MODELING

JEL Classification: 

Pages: 2-10

Importance The article deals with the problem of linking multiple settlements with a system of roads permitting people to get from any settlement to any other one, with a minimum path length. The Chistopolsky District of the Republic of Tatarstan is a case study for the modeling the shortest road network based on the three-point Steiner tree problem.
     Objectives The purpose of the article is a practical application of the Steiner tree in designing and building networks of the shortest roads in the homogeneous territory of several settlements of the Chistopolsky District of the Republic of Tatarstan.
     Methods We conducted the study using the three-point Steiner tree problem.
     Results We have considered the possibility of using the Steiner tree for the design and reconstruction of roads and built a model of a new network of minimum-length roads.
     Conclusions and Relevance We concluded that the application of the three-point Steiner tree for the design and reconstruction of highways in homogeneous territories can significantly reduce the amount of construction work, reduce the path length between settlements, reduce the time of passing, which will contribute to the development of transport potential of the region.

Keywords: Steiner tree problem, Steiner points, homogeneous territory, road engineering, three-point, path, length

References:

1. Khalturin R.A. Sostoyanie i opyt stroitel'stva dorozhnoi seti v Rossii i za rubezhom [A condition and the experience of construction of road networks in Russia and abroad]. Ekonomicheskie nauki = Economic Sciences, 2011, no. 74, pp. 223–226.
2. Lotarev D.T. Neformal'nye opisatel'nye modeli transportnykh kommunikatsii, transportnykh setei i territorii v zadache prokladki putei i kommunikatsii [Informal descriptive models of transport communications, transport networks and territories in the task of ways and communications laying]. Trudy Instituta sistemnogo analiza Rossiiskoi akademii nauk = Works of Institute of System Analysis of RAS, 2009, vol. 46, pp. 259–273.
3. Lotarev D.T., Uzdemir A.P. Preobrazovanie zadachi Shteinera na evklidovoi ploskosti k zadache Shteinera na grafe [Conversion of the Steiner tree problem on the Euclidean plane to the Steiner tree problem on graph]. Avtomatika i telemekhanika = Automation and Remote Control, 2005, no. 10, pp. 80–92.
4. Melzak Z.A. On the problem of Steiner. Canadian Mathematical Bulletin, 1961, vol. 4, pp. 143–148.
5. Protasov V.Yu. Maksimumy i minimumy v geometrii [Maxima and minima in geometry]. Moscow, Moscow Center of Continuous Mathematical Education Publ., 2005, 56 p.
6. Romanovskii I.V. Zadacha Shteinera na grafakh i dinamicheskoe programmirovanie [Steiner tree on columns and the dynamic programming]. Komp'yuternye instrumenty v obrazovanii = Computer Tools in Education, 2004, no. 2, pp. 80–86.
7. Ivanov A.O., Tuzhilin A.A. Zadacha Shteinera na ploskosti ili ploskie minimal'nye seti [The Steiner tree problem in plane or plane minimal nets]. Matematicheskii sbornik = Sbornik: Mathematics, 1991, vol. 182, no. 12, pp. 1813–1844.
8. Gilbert E.N., Pollak H.O. Steiner minimal trees. SIAM Journal of Applied Mathematics, 1968, vol. 16, no. 1, pp. 1–29.
9. Garey M.R., Graham R.L., Johnson D.S. The complexity of computing Steiner minimal trees. SIAM Journal of Applied Mathematics, 1977, vol. 32, no. 4, pp. 835–859.
10. Preparata F., Sheimos M. Vychislitel'naya geometriya. Vvedenie: monografiya [Computing geometry]. Moscow, Mir Publ., 1989, 478 p.
11. Herring M. The Euclidean Steiner Tree Problem. Ohio, Denison University, 2004, 11 p.
12. Warme D., Winter P., Zachariasen M. Exact algorithms for plane Steiner tree problems: a computational study. Denmark, University of Copenhagen, 1998, pp. 81–116.
13. Courant R., Robbins H. Chto takoe matematika? Elementarnyi ocherk idei i metodov [What is Mathematics? An Elementary Approach to Ideas and Methods]. Moscow, Moscow Center of Continuous Mathematical Education Publ., 2001, 568 p.
14. Andreescu T., Mushkarov O., Stoyanov L. Geometric Problems on Maxima and Minima. Boston, Birkhauser, 2006, 272 p.
15. Gordeev E.N., Tarastsov O.G. Zadacha Shteinera. Obzor [The Steiner tree problem: A survey]. Diskretnaya matematika = Discrete Mathematics and Applications, 1993, vol. 5, no. 2, pp. 3–28.
16. Hwang F.K. On Steiner minimal trees with rectilinear distance. SIAM Journal of Applied Mathematics, 1976, vol. 30, no. 1, pp. 104–114.
17. Ermolaev O.P. Landshafty Respubliki Tatarstan. Regional'nyi lanshaftno-ekologicheskii analiz: monografiya [Landscapes of the Republic of Tatarstan. Regional landscape and ecological analysis: a monograph]. Kazan, Slovo Publ., 2007, 411 p.
18. Hwang F.K., Richards D.S., Winter P. The Steiner Tree Problem: A Monograph. Netherlands, Elsevier Science Publishers, 1992, 336 p.
19. Cockayne E.J. On the Steiner Problem. Canadian Mathematical Bulletin, 1967, vol. 10, no. 3, pp. 431–450.
20. Cheng X., Du D.-Z. Steiner Trees in Industry. Netherlands, Springer Science & Business Media, 2001, 507 p.

View all articles of issue

ISSN 2311-8733 (Online)
ISSN 2073-1477 (Print)

Journal current issue

Vol. 22, Iss. 4 April 2024

Archive