| 논문 정보 | |
| 제목 |
Framework for constructing multimodal transport networks and routing using a graph database:
A case study in London |
| 저자 | |
| 소속 |
SpaceTimeLab, Department of Civil, Environmental & Geomatic Engineering, University College London, London, UK
|
| 저널 | Wiley |
| 주제 | Transactions in GIS |
| 논문제출일 | 2023.01.04 |
| 인용수 | 6회 (2024.12.23 기준) |
도로 네트워크 모델링에 관한 논문을 찾다가
현재 우리 연구실에서 진행하고있는 프로젝트와
결이 비슷한 논문이라고 생각하여 한 번 읽어보기로 하였다
내가 궁금했던건
기존 여러 데이터를 바탕으로
어떻게 도로 네트워크를 그래프 형태로 모델링하는지였는데
아주 비슷한 연구는 아니지만
훨씬 더 복잡한 교통 네트워크를 graph database를 활용하여
모델링하고 그 성능을 측정한 연구였다
내가 연구주제를 찾는데에 도움을 받을 수 있을 것 같아서
리뷰해보고자한다
지금까지 논문 리뷰는 논문의 기본 구조를 따라
그냥 나름대로의 정리식이었는데
이번 논문 리뷰는 논문의 기본 구조에서 벗어나서
조금 이해하기 쉬운 방식으로 정리해보려한다
논문 제목에서부터 나와있지만
본 논문은 multimodal transport network 구축에 관한 논문이다
그렇다면 multimodal transport network란 무엇인가?
우리가 흔히 지도를 통해 경로를 찾을 때
대중교통, 운전, 자전거 경로 등
다양한 교통수단의 경로를 찾을 수 있다
multimodal transport routing는 이러한 교통수단을
다양하게 이용하여 경로를 찾는 것을 뜻한다
이는 사용자의 개인화된 요구사항(예, 시간 절약, 비용 최소화 등)을
반영하면서 여러 교통수단 간 환승과 연결을 고려하며 경로를 찾는다
예를 들어
경복궁에서 출발하여 서울역까지 가는 경로를 찾을 때
버스 + 지하철 + 도보 등을 모두 합하여
최적의 경로를 찾는 것을 말한다
따라서 multimodal transport network는
이렇게 다양한 교통수단을 이용하여
routing을 할 수 있도록 데이터를 모델링하는 것인데
본 논문의 introduction에 따르면
실제 상용되는 네비게이션 시스템들이
정확히 어떤 방식으로 데이터를 구축하고있는지 공개하지는 않지만
대부분 일반적으로 관계형데이터베이스(RDBMS)를 사용한다고한다
하지만 이런 네트워크 모델을 관계형데이터베이스를 이용하여 저장하면
비정형적 정보를 데이터베이스 모델에 통합하기 어렵고
유연하지 못한 스키마 때문에
데이터의 유연한 확장에 어려움을 겪는다
또한, 이전에 제안된 multimodal routing을 위해 제안된
multilayer-network에서는 독립적으로 layer를 구축하고
layer간 상호 연결은 동일한 정거장(정류장, 장소 등)을
공통 node로 지정하였다
하지만 이러한 방식은 각 교통수단간의
완벽한 환승을 설명할 수 없다
이에 따라, multimodal routing을 위한 network 모델링은
layer 분리, 쿼리 성능을 고려한 entitiy labeling,
layer간 상호 연결 방식을 포함하여
모든 지역에 대해 확장 가능하도록 세부 구조를 제공해야한다
따라서, 본 논문에서는
관계형데이터베이스와 이전 multimodal network 연구의 한계점을 극복하고자
Graph Database(neo4j)와 여러 문제를 해결할 수 있는
개념적 데이터 모델을 설계하기 위한 framework를 개발하는 것을 목적으로 하였다
기존 공간 교통 네트워크 데이터를 기반으로
graph database를 효율적으로 구축하기 위한 접근법이 제안되었으며
이를 검증하기 위해 런던을 사례로 실제 구축하였다
또한, graph 구축, projection 및 여러 조건에서
유용성을 평가하였다
MULTIMODAL TRANSPORT GRAPH DATABASE
Conceptual model for multimodal transport in graphs
보통 일정 크기 이상의 도시에서는
개인 이동 수단(eg,. 자동차, 자전거, 도보)과
대중교통 수단(eg,. 지하철, 버스)을 포함하여
이들간의 조합을 활용하여 도시 내에서 이동한다
각 교통 수단의 특징을 조금 살펴보자면
버스나 지하철과 같은 대중교통은
정해진 노선과 방향에 따라 운행되고
특정 정류장 혹은 역을 정해진 순서대로 이동한다
따라서 이러한 대중교통은
정류정 혹은 역을 node로 나타내고
각 노드 간의 연결은 미리 정해져있는
노선/라인으로 표현한다
철도(eg., 지하철)의 경우는
각 역(node)간의 이동 시간이 정해져있기때문에
역 간 이동시간을 relationship의 속성으로 사용하면 되지만
버스의 정류장과 정류장 간 이동 시간은
교통상황에 따라 달라지기 때문에
정류장 간 네트워크 거리를 바탕으로 비용을 계산하여
relationship 속성으로 나타내야한다
이와 반대로, 개인 교통수단(eg., 도보, 자차, 자전거)은
고정된 노드 순서에 따라 이동하지 않는다
따라서 이러한 개인 교통수단을
도로 네트워크를 그래프로 모델링해야하는데
일반적인 구조로는
교차로는 node로, 교차로를 연결하는 도로 구간은 realtionship으로 구축된다
각 node간의 거리와 이동 시간은 relationship 속성으로 설정된다
각 mode의 layer는 label을 이용하여 식별할 수 있으며
개인 교통수단은 중복되는 경우가 많으므로
독립적인 레이어로 구성되지 않고
n:Road:Walk:Cycle과 같이 구성하였다
또한, 이전 연구와 같이 환승을 위해서 중복노드(환승 노드)를 포함하지 않으며
보통은 대중교통을 이용한 후는 최소한의 도보 노드를 포함하기 때문에
다양한 교통수단 연결을 위해 도보 레이어와 연결하였다
도보 layer는 보통 양방향으로 이동할 수 있으므로 양방향으로
자전거와 자가용경로는 단방향으로 구성하였다
또한, 교통수단의 시간표 정보를 반영할수있도록
시간 layer를 구성하여 대중교통 수단의 entity를
시간과 연결하였다
이전의 연구에서는 개별 entity property로
대중교통의 시간정보가 설정되었지만
이는 시간 정보가 바뀔 경우 모든 대중교통의 시간정보를
변경해야한다는 어려움이 있었기에
시간 정보를 담는 time entity를 따로 생성하여
해당 대중교통과 연결하여 시간 정보를 반영하였다
또한, 여기서 time layer를 구성할때는
시간 트리 개념을 참조하여 모델링하였으며,
연도에서 밀리초까지의 시간 indexing을 지원하는
계층적 시간 인덱스 구조로 구성된다
국가의 교통시스템은 다른 요금을 적용하기위해
구역(zone) 구분이 사용될 수 있으며
이를 위해 zone layer를 따로 생성하여
요금을 관리하였다
아래 figure1은 지금까지 설명한 데이터의
conceptual model(개념적 모델)을 나타낸 것이다
Entity
총 Entity의 집합 E는
Road, Walk, Cycle, Station, BusStop, Time, Zone
총 7개의 entity의 합집합으로 구성되어있다
1. Road: 도로 네트워크 교차로와 교차로의 끝점
Walkways, Cycleways가 포함되어 여러 레이블이 생길 수 있다
2. Walk: 보행자 네트워크의 교차로와 교차로의 끝점
3. Station: 지하철 혹은 기차역
공통된 Station label을 공유하며 두개 이상의 노선이 지나가는
역에서는 노드가 복제되고, 노선 이름이 label로 지정된다
예: (n1:Station:Northern {name: ‘Warren Street’}), (n2:Station:Victoria {name: ‘Warren Street’})
4. BusStop: 버스 정류장
공통된 BusStop이라는 label을 가지지만
각 버스 노선에 따라 노드가 복제되고
노선 번호 조합을 사용하여 별도의 label이 할당된다
예: (n:BusStop:R18 {code: ‘36542’})
5. Time: Hour과 Minute로 구성
hour은 0-23까지 24개의 node가 생성되고
minute은 0-59까지 60개의 node가 생성된다
6. zone: 요금정보를 위한 구역을 나타낸다
relationship
relationship을 정의할 때 몇 가지 규칙을 정하고
그에 맞게 구현하였다
본 논문에서 나온 규칙은 총 9가지였지만
그 중 중요한 부분만 정리해보겠다
자차, 보행로, 자전거 entity는 네트워크를 따라
자차, 보행로, 자전거 entity들과 relationship을 갖는다
또한 자차 도로와 자전거 도로는 이동 방향에 따라
단방향으로 생성되고, 양방향으로 이동할 수 있는 도로는
단일 선으로 표현되며 양방향으로 모델링된다
BusStop간의 relationship은 노선 번호로 정의된다
예: (n1:BusStop)-[:BUS30]->(n2:BusStop)
Station 간의 relationship도 노선 이름으로 정의된다
예: (n1:Northern {name: 'Warren Street'})-[:Northern]->(n2:Northern {name: 'Euston'})
BusStop과 Station은 CONNECTS relationship을 통해
가장 짧은 거리로 Walk entity와 연결된다
다른 line을 가진 동일한 station은
TRANSFER 관계로 연결된다
BusStop과 Station은 운행 시간표에 따라
DAY_RUN relationship을 통해 Time entity와 연결된다
구역 entitiy에서 요금이 달라지는 구간은 FARE 유형 관계의
속성으로 저장된다
Implementation
neo4j graph database를 사용하여 구축되었으며
데이터는 미리 구축된 데이터셋을 사용하였다
또한 대량의 node와 relationship을 생성하기 위해서
단일 트랜잭션으로 효율적으로 처리하기위해
neo4j csv importer를 사용하여 csv 파일을 이용하여 생성하였다
아래 Figure 2는 단방향과 양방향 도로에 대한
relationship 구현 예시이다
Evaluation
이전 연구를 참고하여 본 데이터 모델링에 대한 평가는
graph creation(그래프 생성)
graph loading(그래프 로딩)
graph query(그래프 쿼리)
이를 위하여
1. 제안된 모델 구조에 따라 graph database를 구축하는 동안
그래프 생성 시간을 측정하고
2. 각 모드에 대한 graph를 projection하는 동안
projection time을 측정하였고
3. routing 성능 측정을 위해 routing query 시간을 측정하였다
Data and test area
본 논문은 런던 지역을 테스트 지역으로 삼았다
런던 관련 공공 교통 정보를 참조하여
796개의 버스 노선과 28개의 지하철 및 기차 노선을
database에 포함시켰다
아래 Table은 데이터의 출처를 나타낸다
또한 테스트 지역의
그래프 기반 multimodal database를 구축한 모습은
아래와 같다
Graph database construction using prebuilt dataset
버스 및 철도 레이어는 일반적으로
정류장 및 정거장의 순서를 기준으로 구축되었다
철도의 경우 양방향 LINE 관계가 생성되었고
서로 다른 라벨을 가진 동일한 정거장 노드는
TRANSFER 관계로 연결되었다
런던에서는 요금이 시간대에 따라 다르기 때문에
6개의 Zone 노드(1~6)가 생성되었고
그 Zone 는 PEAKFARE와 OFFPEAKFARE 2가지의 관계로 연결되어
요금을 속성으로 설정하였다
예: (n:Zone {zone:1})-[:PEAKFARE {fare: 3.2}]-(m:Zone {zone:2})
버스의 경우는 정류장 간의 네트워크 거리를 계산하기 위해
복잡한 과정을 걸쳐서 구현되었다
1. 위치정보를 포함한 BusStop entity를 생성하고
2. R30과 같은 Route Label을 추가하였다
3. BusStop point를 bus network에 snapping하고
snapping된 정류장을 기준으로 bus network를 segment로 분할하였다
4. 매칭된 BusStop을 찾아 노선 정보에 따라 단방향 관계로 연결한다
4. segment 거리 속성을 사용하여
distance 및 travel time 속성을 설정한다
도로 및 경로 네트워크는 노드와 링크 레이어로 구성되며
OS(Ordnance Survey) 고속도로 헌정 데이터를 사용하여
각 노드를 DRIVE_WAY라는 단방향 관계로 연결하였다
multimodal routing을 위해서 가상의 버스 시간표를 구축하였으며
BusStop node가 Hour-Minute node와 DAY_RUN 관계로 연결되었다
이렇게 대중교통의 시간표를 제공하면
특정 출발 및 도착 시간에 적합한 필터링된 그래프를 형성하여
효율적으로 routing을 할 수 있다
또한, 버스, 자동차 도로, 도보, 자전거 도로의 경우
네트워크간 거리를 계산하여 distance 속성으로 저장하였고
이동속도를 이용하여 이동 시간을 계산하여 travel time 속성에 저장하였다
Results
런던의 모든 교통 노드를 포함하여
총 1,079,962개의 node가 생성되었고
구성은 아래와 같다
또한 Relationship(관계)는 아래와 같다
graph creation time
테스트 블록에 대한 전체 graph database는
21분(1242초) 안에 구축되었다
대부분(19분)은 버스 노드와 관계를 생성하는데 사용되었다
버스는 다양한 노선번호 라벨을 가지고 있어
다른 모드보다 생성 시간이 더 길었다
도로, 보행, 자전거 노드는 단일 라벨과
관계 타입을 사용하여 5.43초만에 동시 생성되었다
graph projection time
neo4j의 graph data science library를 사용하여
분석에 필요한 subgraph를 구성하였다
subgraph를 사용할 경우
압축된 형태로 저장할 수 있어 쿼리에 효율적이고
특정 노드와 관계만 포함된 subgraph로 routing query를 실행하면
query 속도를 높일 수 있다
아래 그래프는 각각 그래프 구축과
projection(투영)에 걸린 시간을 나타낸다
Multimodal routing results
런던 내의 test block에서는 node 8808개
relationship 52203개로 구성되었다
2가지 유형으로 routing을 진행했다
1. [출발지, 목적지, mode, 선호도]
2. multi-stop routing with multimode(다중 정차 다중 모드)
1번의 경우 임의로 선택한 두 지점 A와 B를 Origin-Destination(OD) 쌍으로 설정한 후
모든 교통수단을 사용하는 가장 빠른 경로를 도출하고,
이후 동일한 OD 쌍에 대해 도보 및 버스로만 routing을
마지막으로 모든 교통수단을 사용하되 최소 환승 조건을 적용하여 routing을 구성하였다
2번 다중 정차의 경우는,
임의로 5개의 정차 지점과 방문 순서를 설정한 후
3개의 중간 정차를 포함한 모든 교통수단을 사용하는
가장 빠른 경로를 도출하였다
neo4j graph data science(v.1.8.2)를 사용하여
routing query를 실행하였으며
평균 교통수단별 속도를 기반으로
이동 시간을 계산하였다
본 실험의 목적은 정확한 경로 추출이 목적이 아닌
제안된 모델을 기반으로 구축된 그래프 데이터베이스가
multimode routing 문제에 적용이 가능한지를 확인하는 것이다
따라서 경로 비용을 단순화하여 routing을 수행하였으며
성인의 평균 도보 속도는 1.3m/s
평균 자동차 속도를 9.5mph,
평균 버스 속도는 9.3mph,
두 역간의 이동 시간은 2분,
다른 철도 노선 간 환승 시간은 3분,
그리고 버스 정류장과 역 사이를 연결하는
CONNECTS 관계의 이동시간은 1분으로 설정하여
위 시간을 바탕으로 다익스트라 알고리즘으로
routing을 실행하였다
a에서 b까지의 모든 교통수단을 사용한 가장 빠른 route 결과이다
a에서 b까지 버스와 도보만을 사용한 가장 빠른 route 결과이다
a에서 b까지의 가장 빠른 driving route 결과이다
a에서 b까지의 최소 환승으로 최단 route 결과이다
a와 b까지 Google Map의 최단 경로 결과이다
본 실험에서 구축된 데이터베이스에서 반환된 경로가
Google Maps의 최적 경로 목록에 포함된 것을 확인하였다
반환된 경로의 시간이 Google Maps는 22분
본 실험은 28분으로 다르지만
이는 본 실험이 실제 이동 시간이 아닌
실험적 가정으로 이동 시간을 계산하였기 때문이다
a, b, c 각 쿼리의 쿼리 시간은
261ms, 224ms, 146ms으로 점차 줄어드는 것을 확인할 수 있는데
이는 모든 교통수단에서
도보-버스 -> 자동차로 filtering 되면서
그래프 projection으로 subgraph 내부에서 쿼리하면서
graph size가 줄어들고 이에 따라
쿼리 수행시간이 줄어드는 것으로 나타났다
다중 정차 routing test 결과를 나타낸다
결론적으로 구축된 그래프 데이터베이스를 활용하여
지하철(tube)와 버스를 포함한 다양한 교통 수단,
서로 다른 노선 간의 환승
정류장 및 역까지의 도보 이동 등을
효과적으로 탐색할 수 있음을 확인했다
쿼리 시간 측정을 위해
(a) 여러 개의 OD 쌍을 계속해서 늘려가며 쿼리 수행시간을 측정했고
(b) stop(경유지)의 개수의 늘려가며 쿼리 수행 시간을 측정하였다
(a)에서는 OD 쌍의 수를 10개에서 2000개까지 증가시켰고
쿼리 시간이 OD 쌍의 수에 증가하여
선형적으로 증가함이 확인되었는데,
이는 전체 반복 수와 상관없이 안정적인 쿼리 성능이
보장된다는 것을 뜻한다
또한, 위 쿼리 실행 test는
cold run(db를 재부팅하거나 cache를 flush한 직후 실행)
hot run(cold run이후 cache를 flush하지 않고 실행)
두 가지 환경에서 실행하였다
Timetables and fares
본 연구에서는 버스 및 대중교통의 시간표와
요금 정보도 새로운 레이어로 모델링하였다
Old Marylebone Town Hall 버스 정류장에서
Euston Square Station 버스 정류장까지의 경로를 쿼리한 결과이다
동일 노선에 대하여 월요일 오후 12시 30분 이전 출발을 가정한 결과이다
30번 노선 버스만 검색되었다
30번 버스 노선은 12시 25분에 탑승이 가능하다
동일 노선에 대하여 월요일 오후 12시 30분 이후 출발을
쿼리한 결과이다
이 때는 18번 노선의 버스만 검색되었고
이 버스는 12시 36분에 탑승이 가능하다
또한, PEAK 타임과 OFFPEAK 타임에 대한
요금 정보도 모델링하였다
Finchley Central(Zone 4) 역에서 Marble Arch(Zone 1) 역 까지의
PEAK FARE 결과이다
위와 동일한 경우에서
OFFPEAKFARE 쿼리 결과이다
Conclusion and Future work
그래프 데이터베이스는 데이터 통합, 확장 및 업데이트 측면에서
관계형 데이터베이스에 비해서 더 유연한 스키마를 기반으로
다중모드 네트워크를 효과적으로 관리할 수 있음을
본 논문에서 입증하였다
또한 향구 연구 방향으로는
3가지 측면을 고려하였다
1. 다른 data source에서 semantic information 통합
본 연구에서는 다중 교통수단 경로와
시간표, 요금 정보 같은 정보에 초점을 맞추었다
하지만 SNS나 기사와 같은 text data,
도로 임시 폐쇄 여부,
교통 수단 별 교통 흐름 등과 같은
추가적인 정보들도 graph database에 구축하여
routing 가중치로 활용할 수 있다
2. 정확한 비용값
본 연구에서는 이동 시간을 실제 시간이 아닌
계산을 통하여 가정한 비용 값을 사용했다
실제 상황에서 각 도로는 서로 다른 속도 제한을 가지며
교통량에 따라 평균 이동 속도가 달라진다
이러한 정보들을 활용하면
더욱 실용적이고 정확한 경로를 도출할 수 있다
3. 다양항 routing 확장
제안된 그래프 데이터베이스 모델로는
그저 여러 교통수단을 이용한 routing에 그칠뿐아니라
실외-실내간 경로 연결
시간 의존적 routing
개인화된 routing 등
다양한 응용 routing을 수행할 수 있다
나름대로 논문을 읽고 이해하면서
기존 논문의 구조를 벗어나
다른 방식으로 정리해보려했으나(..)
논문이라는게 사실 가장 논리적이고
가장 이해하기 쉬운 구조로 작성된 글이라
그 틀을 벗어나기 쉽지 않았던 것 같다
아무튼 본 논문은 road network에 대해서
처음 접해보는 나에게
이런 방식으로 데이터모델을 구성하는구나를
이해하게 해준 좋은 논문이었던 것 같다
그러나 아직 내가 다루기에는
조금 전문적이고 큰 주제라는 생각이 들어
본 논문에서 나온 과정 중에서
좀 더 작고 구체적인 과정들을 다룬 논문을 보며
좁은 연구주제를 선택해나가려고한다
아무튼 이번 논문리뷰 끝-!