from 01.01.1989 to 01.01.2024
Almaty, Kazakhstan
An important stage in the design of engineering networks is the development of network configurations that meet pre-defined conditions. The main thing for constructing optimization geometric models is to construct the shortest connecting lines for a given discrete set of points in space. The specified points have different weights. Such models also identify geometric factors and determine certain properties of the network configuration in the considered physical space. Geometric models define the image of the projected object and you can build various network tracing configurations that allow you to choose the optimal network. To solve this engineering problem, the article investigates and develops optimization geometric models on planes with Euclidean, orthogonal, polar metrics and algorithms. A unified algorithm for tracing extensive engineering networks on planes with different metrics has been developed. This goal is achieved by applying and generalizing the Steiner method. As you know, the Steiner problem related to the tasks of constructing a minimal spanning tree has not been solved in a general way. The practical solution to the tracing problem is to find the configuration of an extensive network with the smallest length, which has a greater impact on its cost. At the first stage of design, geometric models of engineering networks are developed, then optimization problems are solved, which are reduced to various generalizations of the problem J. Steiner [5,27]. The algorithm for solving the Steiner problem is based on dividing the given discrete points of the plane into a local subset, using the principle of least elongation and a comparative analysis of various geometric models, which allows you to select and build a network of the required configuration. A unified tracing algorithm is formulated for constructing the configuration of a Euclidean, orthogonal, and polar network. The complexity of solving the Steiner problem and engineering tracing problems is due to the fact that these problems belong to the extreme and to the class of NP-hard discrete optimization problems.
geometric models, network tracing, shortest lines, Steiner's problem, Steiner's Euclidean network, Steiner's orthogonal network, Steiner's polar network
1. Anan'ev A.A. Novyy algoritm optimizacii dizayna transportnyh setey s uchetom ogranicheniy [Tekst] / A.A. Anan'ev, P.V. Lomovickiy, D.V. Uzhegov, A.N. Hlyupin // Vychislitel'nye metody i programmirovanie. — M.: Nauchno-issledovatel'skiy vychislitel'nyy centr MGU im. M.V. Lomonosova, 2017. T. 18. — S. 158–168. — DOI:https://doi.org/10.26089/NumMet.v18r213 EDN: https://elibrary.ru/VQSUNP
2. Babayan B.A. Nahozhdenie svyazyvayuschey seti absolyutno minimal'noy dliny [Tekst] / B.A. Babayan, B.S. Popov // Tr. seminara otdela strukturnyh logicheskih shem. M.: ITM i VT AN SSSR, 1969. — Vyp. 7. — S. 27–45.
3. Bagov M.A. Nelokal'noe reshenie setevoy zadachi Shteynera [Tekst] / M.A. Bagov // Vestnik KRAUNC. Fiz.mat nauka. — 2018. — № 4. — S. 148–157. — DOIhttps://doi.org/10.18454/2079-6641- 2018-24-4-148-157 DOI: https://doi.org/10.18454/2079-6641-2018-24-4-148-157; EDN: https://elibrary.ru/VQHNBI
4. Gil'bert E.N. Minimal'nye derev'ya Shteynera [Tekst] / E.N. Gil'bert, G.O. Pollak // Kiberneticheskiy sbornik. — M.: Mir, 1974. — Vyp. 8. — S. 19–50.
5. Esmuhan Zh.M. Prikladnaya geometriya inzhenernyh setey: monografiya [Tekst] / Zh.M. Esmuhan, K.A. Kuspekov. — Almaty: Nauka, 2012. — 132 s.
6. Kel'mans A.K. O postroenii kratchayshey svyazyvayuschey seti [Tekst] / A.K. Kel'mans // Kibernetika i upravlenie. — M.: Nauka, 1967. — S. 115–130.
7. Kureychik V.V. Teoriya evolyucionnyh vychisleniy [Tekst] / V.V. Kureychik, V.M. Kureychik, S.I. Rodzin. M.: Fizmatlit, 2013. — 260 s.
8. Kureychik V.M. Gibridnyy algoritm razbieniya na osnove prirodnyh mehanizmov prinyatiya resheniy [Tekst] / V.M Kureychik., B.K. Lebedev, O.B. Lebedev // Izvestiya RAN. Iskusstvennyy intellekt i prinyatie resheniy. 2012. — S. 3–15.
9. Kureychik V.M. Planirovanie sverhbol'shih integral'nyh shem na osnove integracii modeley adaptivnogo poiska [Tekst] / V.M. Kureychik, B.K. Lebedev, V.B. Lebedev // Izvestiya RAN. Teoriya i sistemy upravleniya. 2013 — № 1. — S. 84–101.
10. Kuspekov K.A. Metod razbienie i postroeniya kratchayshih setey na ploskosti s evklidovoy metrikoy [Tekst] / K.A.Kuspekov // Materialy Mezhdunarodnoy-Vserossiyskoy 66-nauchno-prakticheskoy konferencii. 18–19 oktyabrya 2012 g. Sibirskaya gosudarstvennaya avtomobil'no-dorozhnaya akademiya (SibADI). — Omsk, 2012. — S. 178–181.
11. Kuspekov K.A. Geometricheskie metody trassirovki transportno-logisticheskih setey [Tekst] / K.A Kuspekov., S.I. Rotkov // Materialy 26-y Mezhdunarodnoy konferencii po komp'yuternoy grafike i zreniyu, GrafiKON. — 2016. — S. 531–534.12. Kuspekov K.A. Algoritm postroeniya optimal'noy konfiguracii transportnoy seti zavodov [Tekst] / K.A. Kuspekov. — Almaty: Doklady Nacional'noy akademii nauk Respubliki Kazahstan. — 2010. – № 3. S. 97–99. EDN: https://elibrary.ru/XCVXSR
12. Kuspekov K.A. Metodika postroeniya optimal'noy konfiguracii kratchayshih svyazyvayuschih linii dlya n tochek ploskosti s polyarnoy metrikoy [Tekst] / K.A. Kuspekov // Vestnik KuzGTU. — 2012. — № 2. — S. 86–87. EDN: https://elibrary.ru/OXWNON
13. Kuspekov K.A. Svidetel'stvo. Paket programm dlya EVM: Postroenie geometricheskoy modeli rascheta trassirovki seti na ploskosti s evklidovoy, ortogonal'noy i polyarnoy metrikoy primenyaemye v reshenii razlichnyh inzhenernyh zadach [Tekst] / K.A. Kuspekov, Sh.A. Dzhomartova, A.T. Mazakova. — № 1912, IS009522. Minyust RK, g. Astana. — 1 avgusta 2017.
14. Lebedev B.K. Intellektual'naya procedura postroeniya dereva Shteynera na osnove procedur otsechki i suzheniya [Tekst] / B.K. Lebedev // Izvestiya TRTU. — 2000. № 1. — S. 89. EDN: https://elibrary.ru/IJLUGZ
15. Leparov M.N. O geometricheskih osnovah proektirovaniya tehnicheskogo ob'ekta [Tekst] / M.N. Leparov // Geometriya i grafika. — 2019. — T. 7. — № 2. — S. 28–38. DOI:https://doi.org/10.12737/2308-4898-2023-11-4-3-14 DOI: https://doi.org/10.12737/article_5d2c187251b6c8.21632403; EDN: https://elibrary.ru/CFHAMF
16. Lotarev D.T. Lokal'naya optimizaciya v zadache Shteynera na evklidovoy ploskosti [Tekst] / D.T. Lotarev, A.V. Suprun, A.P. Uzdemir // Avtomatika i telemehanika. — 2004. — № 7. — S. 60–70. EDN: https://elibrary.ru/NQYVZF
17. Lotarev D.T. Zadacha Shteynera dlya transportnoy seti na poverhnosti zadannoy cifrovoy model'yu [Tekst] / D.T. Lotarev // Avtomatika i telemehanika. — 1980. № 10. — 104–115.
18. Prim R.K. Kratchayshie svyazyvayuschie seti i nekotorye obobscheniya [Tekst] / R.K. Prim // Kiberneticheskiy sbornik. — 1961. — № 2. — S. 95–107.
19. Prokof'ev V.M. Nekotorye svoystva kratchayshey linii, soedinyayuschey lyuboe chislo tochek ploskosti [Tekst] / V.M. Prokof'ev // Uchenye zapiski Mosk. gos. ped. in-ta im. V.I. Lenina. — M.: Izd-vo MGPI, 1957. Vyp. 3. — S. 53–67.
20. Sal'kov N.A. Otrazheniya razvitiya inzhenernoy geometrii v zhurnale «Geometriya i grafika» [Tekst] / N.A. Sal'kov, N.S. Kadykova // Geometriya i grafika. 2020. — T. 8. — № 2. — S. 82–100. — DOI:https://doi.org/10.12737/23084898-2020-82-100 DOI: https://doi.org/10.12737/2308-4898-2020-82-100; EDN: https://elibrary.ru/PZHJOC
21. Sal'kov N.A. Geometricheskaya sostavlyayuschaya tehnicheskih innovacii [Tekst] / N.A. Sal'kov // Geometriya i grafika. –2018. — T. 6. — № 2. — S. 85–94. — DOIhttps://doi.org/10.12737/article5b55a5163fa05307622109 DOI: https://doi.org/10.12737/article_5b55a5163fa053.07622109; EDN: https://elibrary.ru/XVRALZ
22. Chernyshev Yu.O. K voprosu o postroenii derev'ev Shteynera s razlichnoy shirinoy vetvey dlya svyazyvaniya elementov trehmernyh SBIS [Tekst] / Yu.O. Chernyshev, N.N. Vencov // Izvestiya YuFU. Tehnicheskie nauki. 2009. — № 4. — S. 72–76. EDN: https://elibrary.ru/KUWJHV
23. Boyce W.M. An improved program for the full Steiner tree problem // ACM. Trans, on Math. Software. 1977. V. 3, pp. 359–385. DOI: https://doi.org/10.1145/355759.355764
24. Chang S. The generation of minimal trees with a Steiner topology // I. ACM. 1972. V. 19, pp. 669–711. DOI: https://doi.org/10.1145/321724.321733
25. Cockayne E. J. Exact computation on Steiner minimal trees in the plane / E.J. Cockayne, E.E. Hewgill // Inf. Proc. Letters.1989. V. 22, pp. 151–156. DOI: https://doi.org/10.1016/0020-0190(86)90062-1
26. Courant R. What is Mathematics / R. Courant, H. Robbins. Oxford University Press, 1996, p. 556. DOI: https://doi.org/10.1093/oso/9780195105193.001.0001
27. Hwang F. The Steiner Tree Problem / F.K. Hwang, D.S. Richards, P. Winter // Annals of Discrete mathematics. 1992. V. 53.
28. Korhonon P. An algorithm for transfor ming a spanning tree into a Steiner // Procc. 9 th Int. Progn. Symp., Budapest 1976. North Holland, Amsterdam, 1979, pp. 343–357.
29. Kuspekov K.A. Optimization geometric models of transport network tracing used in city planning. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences — ISPRS Archives, 2023, 48(5/W2-2023), pp. 63–69. DOI: https://doi.org/10.5194/isprs-archives-xlviii-5-w2-2023-63-2023; EDN: https://elibrary.ru/MINOUX
30. Melzak S.A. On the problem of Stelner // J. Canad. Math. Bull. 1961. V. 4, pp. 143–148. DOI: https://doi.org/10.4153/CMB-1961-016-2
31. Smith I.M. An 0 (n logn) heuristic algorithm for the Steiner minimal tree problems on the euclidaen metric / I.M. Smith, D.T. Lee, I.S. Liebman // Networks. 1981. V. 11, pp. 23–29. DOI: https://doi.org/10.1002/net.3230110104
32. Trifonov A.G. Formulation of the Optimization Problem and Numerical Methods of Its Solution, http://matlab.exponenta.ru/optimiz/book_2/index.php. Cited April 24, 2017.
33. Winter P. Anargoritm for the Steiner problem in the euchlidean plane // Networks. 1985. V. 15, pp. 323–345. DOI: https://doi.org/10.1002/net.3230150305
