전송 네트워크 분석

Transport network analysis
이 항목에 대한 자세한 내용은 근접도 분석을 참조하십시오.
운송 네트워크 수학적 그래프 이론은 흐름 네트워크를 참조하십시오.
네트워크 과학
Internet_map_1024.jpg
네트워크 유형
그래프
특징들
종류들
모델
위상
역학
  • 목록
  • 분류

{모든 목록 삭제}

교통망, 즉 교통망은 지리적 공간의 네트워크나 그래프로 이동이나 흐름을 허용하고 제약하는 인프라를 기술한다.[1] 예를 들어, 도로망, 철도, 항공로, 파이프라인, 수로, 전력선이 포함된다. 이러한 네트워크의 디지털 표현과 그 분석 방법은 공간 분석, 지리 정보 시스템, 공익 사업 및 운송 엔지니어링의 핵심 부분이다. 네트워크 분석은 그래프 이론의 이론과 알고리즘을 적용한 것으로 근접 분석의 한 형태다.

역사

지리적 현상에 대한 그래프 이론의 적용 가능성은 이른 시기로 인식되었다. 사실 그래프 이론가들이 착수했던 초기 문제들과 이론들 중 상당수는 1736년 레온하르트 오일러에 의해 해결되었을 때 그래프 이론의 원초적 토대 중 하나였던 쾨니히스베르크의 일곱 다리 문제 같은 지리적 상황에 의해 영감을 받은 것이었다.[2]

1970년대에는 초기 지리정보시스템 개발자들이 폴리곤의 위상적 데이터 구조(여기서는 관련성이 없는 것)와 교통망 분석에 이를 채용함으로써 연결이 재확립되었다. 팅클러(1977년)와 같은 초기 작품들은 주로 단순한 개략적 네트워크에 초점을 맞췄는데, 이는 상당한 양의 선형 데이터가 부족하고 많은 알고리즘의 계산 복잡성 때문일 것이다.[3] GIS 소프트웨어에 있어서의 네트워크 분석 알고리즘의 완전한 구현은 1990년대에 이르러서야 나타났지만,[4][5] 오늘날에는 다소 발전된 도구를 일반적으로 이용할 수 있다.

네트워크 데이터

네트워크 분석에는 네트워크의 요소와 그 속성을 나타내는 상세한 데이터가 필요하다.[6] 네트워크 데이터 집합의 핵심은 가장자리라고 알려진 정확한 지리적 경로나 도식도 등 이동 경로를 나타내는 폴리선의 벡터 레이어다. 또한, 회선 사이의 연결을 나타내는 네트워크 토폴로지에서 정보가 필요하므로, 한 회선에서 다른 회선으로의 전송을 모델링할 수 있다. 일반적으로 이러한 연결 지점 또는 노드는 추가 데이터 집합으로 포함된다.[7]

가장자리와 노드는 모두 이동 또는 흐름과 관련된 속성으로 귀속된다.

  • 용량, 도로의 차선 수, 통신 대역폭 또는 파이프 지름과 같이 허용되는 흐름 볼륨의 제한에 대한 측정.
  • 임피던스, 도로 교차로에서 제한 속도 또는 금지된 방향 회전 방향과 같은 흐름 또는 속도에 대한 저항의 측정
  • 거리 마찰 원리에 따라 가장자리를 따라 또는 노드를 통해 개별 이동을 통해 누적된 비용. 예를 들어, 거리 네트워크의 노드는 특정한 좌회전 또는 우회전을 하는 데 다른 시간이 필요할 수 있다. 이러한 비용은 교통량의 주간 주기에 따라 도시 거리를 따라 이동하는 패턴과 같이 시간이 지남에 따라 달라질 수 있다.
  • 흐름 볼륨, 실제 이동에 대한 측정값. 이는 트래픽 카운터와 같은 센서 네트워크를 사용하여 수집된 특정 시간 인코딩 측정치 또는 연간 평균 일일 트래픽(AADT)과 같은 일정 기간 동안의 일반적인 추세일 수 있다.

분석 방법

네트워크 흐름과 관련된 문제와 과제를 해결하기 위한 광범위한 방법, 알고리즘 및 기법이 개발되었다. 이들 중 일부는 모든 유형의 전송 네트워크에 공통적인 반면, 다른 일부는 특정 애플리케이션 도메인에 특정된다.[8] 이러한 알고리즘의 대부분은 GRASS GIS와 Esri ArcGIS로의 네트워크 분석가 확장 등과 같은 상용 및 오픈 소스 GIS 소프트웨어에서 구현된다.

최적 라우팅

주요 기사: 최단 경로 문제 및 Dijkstra 알고리즘

네트워크에서 가장 단순하고 일반적인 작업 중 하나는 네트워크를 따라 두 지점을 연결하는 최적의 경로를 찾는 것으로, 거리, 에너지 지출 또는 시간과 같은 어떤 형태의 비용을 최소화하는 것으로 최적으로 정의된다.[9] 구글 지도와 같은 거의 모든 웹 스트리트 지도 애플리케이션의 특징인 스트리트 네트워크에서 길을 찾는 것이 일반적인 예다. 대부분의 GIS와 매핑 소프트웨어에서 구현되는 이 과제를 해결하는 가장 인기 있는 방법은 Dijkstra의 알고리즘이다.[10]

기본 포인트 투 포인트 라우팅 외에도 복합 라우팅 문제도 흔하다. 여행 판매원 문제는 다수의 목적지에 도달하기 위한 최적의(최소 거리/비용) 주문 및 경로를 요구한다. NP-하드 문제지만, 솔루션 세트가 작기 때문에 제약 없는 공간보다 네트워크 공간에서 해결하는 것이 다소 쉽다.[11] 차량 경로 지정 문제는 이를 일반화하여 여러 개의 동시 경로가 목적지에 도달할 수 있도록 한다. 경로 검사 또는 "중국 우체부" 문제는 모든 가장자리를 가로지르는 최적의 (최소 거리/비용) 경로를 요구한다. 공통적인 적용은 쓰레기 트럭의 라우팅이다. 이것은 다항식 시간 알고리즘으로 해결하기에 훨씬 간단한 문제임이 밝혀졌다.

위치분석

주요 기사: 설비위치 문제 및 위치할당

이 등급의 문제들은 네트워크를 따라 하나 이상의 설비에 대한 최적의 위치를 찾는 것을 목표로 하며, 네트워크의 다른 지점들에 대한 총계 또는 평균 이동 비용을 최소화하는 것으로 정의된다. 일반적인 예는 일련의 소매점에 대한 배송비를 최소화하기 위해 창고의 위치를 결정하거나, 잠재적 고객의 거주지로부터의 이동 시간을 최소화하기 위해 소매점의 위치를 결정하는 것이다. 제약받지 않는(카르트 좌표) 공간에서 이것은 로이드의 알고리즘과 같은 경험적 해결책이 필요한 NP-하드 문제지만, 네트워크 공간에서는 결정적으로 해결할 수 있다.[12]

특정 애플리케이션은 종종 기존 또는 경쟁 시설의 위치, 설비 용량 또는 최대 비용 등과 같은 문제에 추가적인 제약을 추가한다.

서비스 영역

네트워크 서비스 구역은 제한되지 않은 공간에 있는 버퍼와 유사하며, 특정 거리 또는 기타 누적 비용보다 적은 지점(일반적으로 서비스 시설)에서 도달할 수 있는 영역을 묘사한다.[13] 예를 들어, 소방서가 선호하는 서비스 구역은 적은 시간 내에 도달할 수 있는 거리 구획 집합이 될 것이다. 여러 설비가 있을 경우, 각 가장자리는 가장 가까운 설비에 할당되어 보로노이 다이어그램과 유사한 결과를 산출한다.[14]

결함분석

공공 서비스 네트워크에서 공통적인 애플리케이션은 (흔히 묻히거나 또는 직접적으로 관찰하기 어려운) 네트워크의 고장 또는 파손의 가능한 위치를 식별하는 것으로, 고객 불만사항과 같이 쉽게 찾을 수 있는 보고서로부터 추론한다.

운송공학

주요 기사: 운송 엔지니어링 및 교통 흐름

교통은 통계 물리학 방법을 사용하여 광범위하게 연구되어 왔다.[15][16][17] 최근 베이징의 실제 교통망은 네트워크 접근법과 퍼콜레이션 이론을 사용하여 연구되었다. 이 연구는 과밀 임계값을 사용하여 하루 중 한 도시의 세계 교통의 질을 특징 지을 수 있다는 것을 보여주었다. 최근 기사에서는 도시의 교통 혼잡을 연구하기 위해 과밀이론을 적용했다. 주어진 시간에 도시에서의 세계 교통의 질은 단일한 매개변수, 즉 퍼콜레이션 임계 임계값에 의해 이루어진다. 임계치는 도시 네트워크의 많은 부분을 여행할 수 있는 속도 이하의 속도를 나타낸다. 이 방법은 반복적인 트래픽 병목 현상을 식별할 수 있다. [18] 양호한 트래픽의 클러스터 크기 분포를 특징짓는 임계 지수는 과집합 이론의 지수와 유사하다.[19] 또한 출퇴근 시간 동안 트래픽 네트워크는 서로 다른 네트워크 크기와 이들 상태 간의 대체의 몇 가지 측정 가능한 상태를 가질 수 있는 것으로 밝혀졌다.[20]

교통체증 규모 분포에 관한 실증적 연구가 최근 장 외 연구원에 의해 수행되고 있다.[21] 그들은 잼 크기 분배에 대한 대략적인 보편적 동력 법칙을 발견했다.

세록 등은 도시의 유창한 교통 흐름을 나타내는 공간-임시거리의 기능 클러스터를 파악하는 방법을 개발했다.[22] G. Li 외는 도시에서 최적의 2층 교통망을 설계하는 방법을 개발했다.[23]

Percolation traffic networks
그림 1: 베이징의 통상적인 하루 동안의 교통망 정리. A 고속 클러스터를 보여준다. B에서는 거대 구성요소가 파괴되는 임계치에 있는 군집을 볼 수 있다. C 도시 전체에 도달할 수 있는 저속 케이스를 보여준다. D에서는 상대 속도의 함수로 가장 큰(녹색) 성분과 두 번째로 큰(주황색) 성분의 과대포장 동작을 볼 수 있다. E 근무일 및 주말의 주간 임계치인 q 을를) 표시한다. high q 은(는) 글로벌 트래픽이 양호함을 의미하며, low c 은(는) 출퇴근 시간 동안 트래픽이 불량함을 의미한다.

트래픽 흐름 패턴

출퇴근 시간과 비출퇴근 시간대에 대도시 도시 지역의 교통 흐름의 강과 같은 패턴은 시다 요헤이 외 연구진에 의해 연구되어 왔다.[24]

참고 항목

참조

  1. ^ Barthelemy, Marc (2010). "Spatial Networks". Physics Reports. 499 (1–3): 1–101. arXiv:1010.0302. Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002. S2CID 4627021.
  2. ^ 오일러, 레온하르트(1736). "Solutio publicatis ad geometriam situs associatedis". 댓글을 달다. 아카드. 공상과학. U. Petrop 8, 128–40.
  3. ^ Tinkler, K.J. (1977). "An Introduction to Graph Theoretical Methods in Geography" (PDF). CATMOG (14).
  4. ^ Ahuja R K, Magnanti T L, Orlin J B(1993) 네트워크 흐름: 이론, 알고리즘 및 응용 프로그램. 미국 뉴욕 주 엥글우드 절벽의 프렌티스 홀
  5. ^ Daskin M S (1995) 네트워크 및 이산 위치 - 모델, 알고리즘 및 응용 프로그램. Wiley, NJ, 미국
  6. ^ "What is a network dataset?". ArcGIS Pro Documentation. Esri.
  7. ^ "Network elements". ArcGIS Pro Documentation. Esri. Retrieved 17 March 2021.
  8. ^ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.2.1 Overview - network and locational analysis". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
  9. ^ Worboys, Michael; Duckham, Matt (2004). "5.7 Network Representation and Algorithms". GIS: A Computing Perspective (2nd ed.). CRC Press. pp. 211–218.
  10. ^ Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID 123284777.
  11. ^ "v.net.salesman command". GRASS GIS manual. OSGEO. Retrieved 17 March 2021.
  12. ^ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.2 Larger p-median and p-center problems". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
  13. ^ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.3 Service areas". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
  14. ^ "v.net.alloc command". GRASS GIS documentation. OSGEO. Retrieved 17 March 2021.
  15. ^ Helbing, D (2001). "Traffic and related self-driven many-particle systems". Reviews of Modern Physics. 73 (4): 1067–1141. arXiv:cond-mat/0012229. Bibcode:2001RvMP...73.1067H. doi:10.1103/RevModPhys.73.1067. S2CID 119330488.
  16. ^ S., Kerner, Boris (2004). The Physics of Traffic : Empirical Freeway Pattern Features, Engineering Applications, and Theory. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783540409861. OCLC 840291446.
  17. ^ Wolf, D E; Schreckenberg, M; Bachem, A (June 1996). Traffic and Granular Flow. Traffic and Granular Flow. WORLD SCIENTIFIC. pp. 1–394. doi:10.1142/9789814531276. ISBN 9789810226350.
  18. ^ Li, Daqing; Fu, Bowen; Wang, Yunpeng; Lu, Guangquan; Berezin, Yehiel; Stanley, H. Eugene; Havlin, Shlomo (2015-01-20). "Percolation transition in dynamical traffic network with evolving critical bottlenecks". Proceedings of the National Academy of Sciences. 112 (3): 669–672. Bibcode:2015PNAS..112..669L. doi:10.1073/pnas.1419185112. ISSN 0027-8424. PMC 4311803. PMID 25552558.
  19. ^ 도시 교통 역학에서 중요한 퍼콜 모드 간 전환, G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin, 국립 과학 아카데미 진행 116(1), 23-28(2019)
  20. ^ G. Zeng, J. Gao, L. Shekhtman, S. Guo, W. Lv, J. Wu, H. Liu, O. Levy, D. Li, ... (2020). "Multiple metastable network states in urban traffic". Proceedings of the National Academy of Sciences. 117 (30): 17528–17534. doi:10.1073/pnas.1907493117. PMC 7395445. PMID 32661171.CS1 maint: 여러 이름: 작성자 목록(링크)
  21. ^ 실제 교통 체증의 스케일 프리 복원력, 리마오 장, 관원 쩡, 다칭 리, 하이준 황, H 유진 스탠리, 슐로모 하블린, 국립과학원 의사록 116(18), 8673-8678(2019)
  22. ^ Nimrod Serok, Orr Levy, Shlomo Havlin, Efrat Blumenfeld-Lieberthal (2019). "Unveiling the inter-relations between the urban streets network and its dynamic traffic flows: Planning implication". SAGE Publications. 46 (7): 1362.CS1 maint: 여러 이름: 작성자 목록(링크)
  23. ^ G. Li, S.D.S. Reis, A.A. Moreira, S. Havlin, H.E. Stanley, J.S. Andrade Jr. (2010). "Towards Design Principles for Optimal Transport Networks". Phys. Rev. Lett. 104 (1): 018701. arXiv:0908.3869. Bibcode:2010PhRvL.104a8701L. doi:10.1103/PhysRevLett.104.018701. PMID 20366398. S2CID 119177807.CS1 maint: 여러 이름: 작성자 목록(링크)
  24. ^ Y. Shida, H. Takayasu, S. Havlin, M. Takayasu (2020). "Universal scaling laws of collective human flow patterns in urban regions". Scientific Reports. 10 (1): 21405. doi:10.1038/s41598-020-77163-2. PMC 7722863. PMID 33293581.CS1 maint: 여러 이름: 작성자 목록(링크)