Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Географиялық желілерге арналған кеңістіктік талдау құралдары көлік желісі математикалық граф теориясы
Spatial analysis tools for geographic networks
transportation network mathematical graph theory
Көлік желісі – географиялық кеңістіктегі қозғалыс немесе ағынды қамтамасыз ететін және шектейтін инфрақұрылымды сипаттайтын желі немесе граф. Мысалдарға жол желілері, теміржолдар, әуе бағыттары, құбырлар, су тас жолдары және электр желілері жатады, бірақ олармен шектелмейді. Мұндай желілердің цифрлық бейнеленуі және оларды талдау әдістері кеңістіктік талдаудың, географиялық ақпараттық жүйелердің, коммуналдық қызметтердің және көлік инженериясының маңызды бөлігі болып табылады. Желілік талдау – граф теориясының теориялары мен алгоритмдерін қолдану және жақындық талдауының бір түрі.
A transport network, or transportation network, is a network or graph in geographic space, describing an infrastructure that permits and constrains movement or flow. Examples include but are not limited to road networks, railways, air routes, pipelines, aqueducts, and power lines. The digital representation of these networks, and the methods for their analysis, is a core part of spatial analysis, geographic information systems, public utilities, and transport engineering. Network analysis is an application of the theories and algorithms of graph theory and is a form of proximity analysis.
Тарих
Граф теориясының географиялық құбылыстарға қолданылуы ерте заманда-ақ анықталды. Граф теориясын зерттеушілердің көптеген алғашқы мәселелері мен теориялары географиялық жағдайларға байланысты туындады, мысалы, 1736 жылы Леонхард Эйлер шешкен Кенигсбергтің жеті көпірі мәселесі – граф теориясының бастапқы негіздерінің бірі болды. 1970-ші жылдары географиялық ақпараттық жүйелерді (ГИС) дамытушылар бұл байланысты қайта жаңғыртты, олар оны полигондардың топологиялық дерек құрылымдарында (біздің жағдайымызда маңызды емес) және көлік желілерін талдауда пайдаланды. Тинклердің (1977) сияқты алғашқы жұмыстар көбінесе қарапайым схемалық желілерге бағытталды, мұның себебі сызықтық деректердің жеткілікті көлемі болмауы және көптеген алгоритмдердің есептеу қиындығы болуы мүмкін. Желілік талдау алгоритмдері ГИС бағдарламалық құралдарында 1990-шы жылдарда толыққанды жүзеге асырылды, ал қазіргі таңда кеңейтілген құралдар қолжетімді.
The applicability of graph theory to geographic phenomena was recognized at an early date. Many of the early problems and theories undertaken by graph theorists were inspired by geographic situations, such as the Seven Bridges of Königsberg problem, which was one of the original foundations of graph theory when it was solved by Leonhard Euler in 1736. In the 1970s, the connection was reestablished by the early developers of geographic information systems, who employed it in the topological data structures of polygons (which is not of relevance here), and the analysis of transport networks. Early works, such as Tinkler (1977), focused mainly on simple schematic networks, likely due to the lack of significant volumes of linear data and the computational complexity of many of the algorithms. The full implementation of network analysis algorithms in GIS software did not appear until the 1990s, but rather advanced tools are generally available today.
Талдау әдістері
Желілік ағымға қатысты мәселелер мен тапсырмаларды шешу үшін кең ауқымды әдістер, алгоритмдер және техникалар әзірленді. Олардың кейбіреулері барлық көлік желілеріне ортақ, ал қалғандары нақты қолданыс салаларына тән. Көптеген алгоритмдер коммерциялық және ашық кодты ГИС бағдарламалық қамтамасында, мысалы GRASS GIS және Esri ArcGIS-тің Желілік талдаушы кеңейтуінде жүзеге асырылған.
A wide range of methods, algorithms, and techniques have been developed for solving problems and tasks relating to network flow. Some of these are common to all types of transport networks, while others are specific to particular application domains. Many of these algorithms are implemented in commercial and open source GIS software, such as GRASS GIS and the Network Analyst extension to Esri ArcGIS.
Оңтайлы маршрут
Желідегі ең қарапайым және кең таралған міндеттердің бірі – желі бойымен екі нүктені қосатын ең тиімді маршрутты табу, мұнда ең тиімді дегеніміз – қашықтық, энергия жұмсалымы немесе уақыт сияқты белгілі бір шығындарды азайту. Көше желісінде бағыт табу – Google Maps сияқты кез келген веб-көше карта жасау қолданбасының маңызды мүмкіндігі. Бұл мәселені шешудің ең танымал әдісі, көптеген ГИС және карта жасау бағдарламалық құралдарында қолданылатын Дикстра алгоритмі болып табылады. Бастапқы нүктеден нүктеге маршруттан басқа, күрделі маршруттау мәселелері де жиі кездеседі. Саяхатшы сатушы мәселесі бірнеше пунктке жету үшін ең тиімді (ең аз қашықтық/шығын) реттілікті және маршрутты анықтауды талап етеді; бұл NP-қиын мәселе, бірақ шешімдер жиынтығы кішірек болғандықтан желілік кеңістікте шешу оңайырақ. Көлік құралдарын маршруттау мәселесі осыған ұқсас, бірақ мақсатқа бірнеше бірдей маршруттармен жетуге мүмкіндік береді. Маршрутты тексеру немесе «қытай почташысы» мәселесі желінің барлық қабырғаларын аралап өтетін ең тиімді (ең аз қашықтық/шығын) маршрутты табуды талап етеді; оның кең таралған қолданысы – қоқыс жинау машиналарын маршруттау. Бұл полиномиалдық уақыт алгоритмдерімен шешуге болатын әлдеқайда қарапайым мәселе болып табылады.
One of the simplest and most common tasks in a network is to find the optimal route connecting two points along the network, with optimal defined as minimizing some form of cost, such as distance, energy expenditure, or time. A common example is finding directions in a street network, a feature of almost any web street mapping application such as Google Maps. The most popular method of solving this task, implemented in most GIS and mapping software, is Dijkstra's algorithm. In addition to the basic point to point routing, composite routing problems are also common. The Traveling salesman problem asks for the optimal (least distance/cost) ordering and route to reach a number of destinations; it is an NP hard problem, but somewhat easier to solve in network space than unconstrained space due to the smaller solution set. The Vehicle routing problem is a generalization of this, allowing for multiple simultaneous routes to reach the destinations. The Route inspection or "Chinese Postman" problem asks for the optimal (least distance/cost) path that traverses every edge; a common application is the routing of garbage trucks. This turns out to be a much simpler problem to solve, with polynomial time algorithms.
Орналасуды талдау
Бұл проблемалар класы желіде бір немесе бірнеше нысанды орналастыру үшін ең қолайлы жерді табуға бағытталған, мұнда ең қолайлы дегеніміз – желідегі басқа нүктелер жиынтығына (немесе олардан) баратын немесе қайтатын жалпы немесе орташа сапар шығынын азайту. Көрінетін мысал – дүкендер жиынтығына тасымалдау шығындарын азайту мақсатында қойманың орналасуын анықтау, немесе потенциалды клиенттердің үйлерінен сапар уақытын ең аз ету үшін дүкеннің орналасуын анықтау. Шектеусіз (декарт координаталары) кеңістікте бұл NP-қиын мәселе болып табылады, сондықтан Ллойд алгоритмі сияқты эвристикалық шешімдер қажет, бірақ желілік кеңістікте оны нақты шешуге болады. Нақты қолданыстар жиі проблемаға қосымша шектеулер қосады, мысалы, бұрыннан бар немесе бәсекелес нысандардың орналасуы, нысандардың сыйымдылығы немесе ең жоғары бағасы.
This class of problems aims to find the optimal location for one or more facilities along the network, with optimal defined as minimizing the aggregate or mean travel cost to (or from) another set of points in the network. A common example is determining the location of a warehouse to minimize shipping costs to a set of retail outlets, or the location of a retail outlet to minimize the travel time from the residences of its potential customers. In unconstrained (cartesian coordinate) space, this is an NP hard problem requiring heuristic solutions such as Lloyd's algorithm, but in a network space it can be solved deterministically. Particular applications often add further constraints to the problem, such as the location of pre existing or competing facilities, facility capacities, or maximum cost.
Қызмет көрсету аймақтары
Желілік қызмет көрсету аймағы – шектеусіз кеңістіктегі буфер сияқты, белгілі бір нүктеден (әдетте қызмет көрсету орнынан) белгіленген қашықтықта немесе жинақталған басқа да шығындар шегінде қолжетімді аймақты көрсетеді. Мысалы, өрт сөндіру станциясы үшін ең қолайлы қызмет көрсету аймағы – ол аз уақыт ішінде жете алатын көше кесінділерінің жиынтығы болады. Егер бірнеше қызмет көрсету орны болса, әрбір учаске ең жақын орнына бекітіледі, нәтижесінде Вороной диаграммасына ұқсас сурет пайда болады.
A network service area is analogous to a buffer in unconstrained space, a depiction of the area that can be reached from a point (typically a service facility) in less than a specified distance or other accumulated cost. For example, the preferred service area for a fire station would be the set of street segments it can reach in a small amount of time. When there are multiple facilities, each edge would be assigned to the nearest facility, producing a result analogous to a Voronoi diagram.
Қателерді талдау
Қоғамдық коммуналдық желілерде кең таралған қолданыс – желідегі ақаулардың немесе үзілістердің болу мүмкін жерлерін анықтау (әдетте, жерге көмілген немесе тікелей бақылау қиын жағдайларда), клиенттердің шағымдары сияқты анықтауға оңай есептерден шығару арқылы іске асырылады.
A common application in public utility networks is the identification of possible locations of faults or breaks in the network (which is often buried or otherwise difficult to directly observe), deduced from reports that can be easily located, such as customer complaints.
Көлік техникасы
Көлік қозғалысы статистикалық физика әдістерімен жан-жақты зерттелді.
Traffic has been studied extensively using statistical physics methods.
Тік талдау
Темір жол жүйесінің мүмкіндігінше тиімді болуын қамтамасыз ету үшін күрделілік/вертикальді талдау да жүргізілуі керек. Бұл талдау болашақ және қолданыстағы жүйелерді талдауға көмектеседі, бұл жүйенің тұрақтылығын қамтамасыз ету үшін өте маңызды (Bednar, 2022, 75-76 бб.). Вертикальді талдау жүйенің операциялық қызметтерін (күнделікті жұмысын) білуден, проблемалардың алдын алудан, бақылау шараларын жүзеге асырудан, қызметтерді дамытудан және оларды үйлестіруден тұрады.
To ensure the railway system is as efficient as possible a complexity/vertical analysis should also be undertaken. This analysis will aid in the analysis of future and existing systems which is crucial in ensuring the sustainability of a system (Bednar, 2022, pp. 75–76). Vertical analysis will consist of knowing the operating activities (day to day operations) of the system, problem prevention, control activities, development of activities and coordination of activities.