GPS 수집자료를 이용하여 최적경로를 결정하기 위한 단계별 세분화 방법

The Coarse Grid Method for the Determining Optimal Route Using of Global Positioning System Data

대규모의 도로망에서 방대한 정보를 분석하여, 실시간으로 최적경로를 탐색해야 하는 경로안내시스템에서는 탐색효율이 필수적이다. 이를 위하여 많은 연구들이 탐색대상이 되는 노드와 링크의 수를 줄이려고 노력해 왔다. 이 논문에서는 일부 영역만의 탐색으로 함수의 최적값을 찾는 단계별 세분화 방법(CGM: coarse grid method)의 원리를 도로망에 응용한다. 처음에는 소규모 도로망, 다음에는 중규모 도로망, 그 다음에는 대규모 도로망 등으로 그 대상을 단계적으로 세분화함으로써, 동시에 수많은 노드들간의 경로를 찾는 기존 방법에서의 탐색시간을 단축한다. 이 시스템을 경기도 고양시 일산구의 충분히 세분화된 실제 도로망에 적용하여, 시스템의 효율성, 실용성과 실시간 운영 가능성을 경로의 탐색시간, 경로의 적합성 등에서 입증한다.

The efficiency of real-time Route Guidance System(RGS) depends largely on the quality of route search algorithms. In this paper, We implement the Coarse Grid Method(CGM) in mathematical programming for finding a good quality route of real-time RGS in large-scale road networks. To proposed CGM examines coarser and wider networks as the search phase proceeds, in stead of searching the whole network at once. Naturally, We can significantly reduce computational efforts in terms of search time and memory requirement. We demonstrate the practical effectiveness of proposed CGM with nationwide real road network simulation of IlSan-Ku in Goyang city.