GPS 수집자료를 이용하여 최적경로를 결정하기 위한 단계별 세분화 방법 = The Coarse Grid Method for the Determining Optimal Route Using of Global Positioning System Data

다국어 초록 (Multilingual Abstract)

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.

국문 초록 (Abstract)

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

참고문헌 (Reference)

• 1 최원범, "자동차 항법 시스템 스크린에서 제시되는 메뉴 항목수의 변화가 메뉴 선택과 운전 수행에 미치는 영향" 7 (7): 649-663, 2005
• 2 최기주, "시계열기반의 GPS 프로브 자료의 이상치 제거 알고리즘 개발" 대한교통학회 22 (22): 67-75, 2004
• 3 최승배, "공간변이성의 추정량들에 대한 예측력 비교 연구-남한지역 일산화탄소 자료를 이용하여-" 6 (6): 279-291, 2004
• 4 강창완, "공간 데이터마이닝에서의 유전자알고리즘을 이용한 예측방법의 연구" 4 (4): 103-113, 2002
• 5 최승배, "공간 데이터마이닝에서의 유전자알고리즘을 이용한 예측방법의 연구" 4 (4): 103-113, 2002
• 6 Kung,J.Y, "The Shortest Path Problem with Discrete Fuzzy Arc Lengths" 49 : 263-270, 2005
• 7 Chuang, T. N., "The Fuzzy Shortest Path Length and the Corresponding Shortest Path in a Network" 32 : 1409-1428, 2005
• 8 Cherkassky, B. V, "Shortest Paths Algorithms: Theory and Experimental Evaluation" 73 : 129-174, 1996
• 9 Zhan, F. B., "Shortest Path Algorithms: An evaluation Using Real Road Networks" 32 : 65-73, 1998
• 10 Gallo, G., "Shortest Path Algorithms" 13 : 3-79, 1998
• 11 Backhouse, "Science of Computer Programming" 3-19, 1994
• 12 Nemhauser,G.L, "Introduction to Dynamic Programming" 1966
• 13 최기주, "GPS와 GIS를 이용한 링크통행시간 예측기법" 대한교통학회지 16 (16): 197-207, 1998
• 14 이영우, "GPS 수집자료를 이용한 링크통행시간 분포 특성 분석" 22 (22): 7-17, 2004
• 15 Park, C. K, "Finding a Path in the Hierarchical Road Networks" 936-942, 2001
• 16 Fu, L., "Expected Shortest Paths in Dynamic and Stochastic Traffic Networks" 32 : 499-516, 1998
• 17 Han, Y, "Efficient Parallel Algorithm for Computing All Pair Shortest Paths in Directed Graphs" 17 : 399-415, 1997
• 18 Kim, H. G, "Design and Implementation of an Intelligent System for Real-Time Route Advice" Korea University 2002
• 19 Chou, Y. L, "Approximating Shortest Paths in Large-Scale Networks with an Application to Intelligent Transportation Systems" 10 : 163-179, 1998
• 20 Noto, M., "A Method for the Shortest Search by Extended Dijkstra Algorithm" 3 : 2316-2320, 2000
• 21 Mills,G, "A Decomposition Algorithm for the Shortest-Route Problem" 14 : 297-291, 1966
• 22 조한선, "2004년 전국 교통혼잡비용 산출과 추이 분석" 한국교통연구원 2006