[논문]실시간 경로 조언을 위한 지능형 시스템의 설계 및 구축

김성인; 김현기

실시간 경로 조언을 위한 지능형 시스템의 설계 및 구축
Design and Implementation of an Intelligent System for Real-Time Route Guidance 원문보기

산업공학 = IE Interfaces, v.15 no.4, 2002년, pp.374 - 381

김성인 (고려대학교 산업시스템정보공학과) , 김현기 (고려대학교 산업시스템정보공학과)

Abstract ▼ AI-Helper

In this paper, we design and implement a real-time route guidance system(RGS) in large-scale networks. Coupled with the well-known mathematical routing algorithms, we devise an RGS for knowledge aquisition and self-learning ability within the framework of the expert system. Through off-line construction of database, on-line treatment of unexpected traffic accidents, etc., the developed RGS can provide drivers with good quality real-time routing information. The practical effectiveness of the proposed system is demonstrated in terms of response time and route appropriateness.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

ITS를 구성하는 주요 요소의 하나는 경로 안내 시스템(RGS: Route Guidance System)이며, 그 목적은 도착지를 향해 운행하는 차량에게 현재의 교통 상황을 고려하여 최적 경로를 제공하는 것이다. 도로상의 운전자, 특히 초행길의 운전자는(Adler, 2001) 각종 정 보망을 통해 실시간으로 수집 된 다양한 교통 정보를 차내 항법 장치를 이용해 중앙센터로부터 수신하며, 또한 최적 경로를 조언 받는다’ 이러한 RGS가 갖추어야 할 기능은 다음과 같다.
이를 위하여 시스템 구조의 각 부분을 모듈별로 구성하며, 시 스템의 기초가 되는 데이터베이스(DB : Database)를 구축하고, 시스템의 운영 방법을 제시한다. 여기에서 지능형의 성격을 갖기 위하여 수리적 알고리듬과 함께 전문가의 지식을 획득하 여 활용하는 방법을 개발한다. 제3절에서는 구죽된 시스템을 실제 문제에 적용해 보고, 시스템의 타당성을 검증한다.
이 연구에서는 지능형 교통시스템(ITS : Intelligent Transportation System)의 핵심 기술인 경로 조언을 위한 지능형 시스템을 설계하고 구축하였다. 이 시스템은 온라인과 오프라인으로 나뉘어 운영된다.

제안 방법

에 사고가 발생하였다고 하자. 먼저, 인공지능 알고리듬을 적용하여 새로운 경로 A -» B⑴를 찾고, O — ——» A(2) — A⑴ t A B(l) — B(2) — » DA —» B⑴의 거리를 계산한다. 이와 같이, A⑴-fB, A⑴ 一»B(1), A(2)--B, A(2)-»B(1), .
운영된다. 시스템 사용자(운전자)로부터 O-D 경로의 질의가 들어오면, 오프라인으로 미리 구축된 DB의 정보를 이용하여 온라인에서 최소한의 비교로써 경로를 결정하고 이를 운전자에게 조언한다. 한편, 교통 사고, 교통 정체, 집회, 도로 공사등 돌발적 인 상황이 발생하는 경우에는 온라인으로 가장 빨리 수행되는 인공지능 알고리듬을 적용하여 경로를 구하고 이를 운전자에게 조언한다.
실시간 자료의 처리는 돌발적인 상황에 대하여 인공지능 알고리듬을 적용하여 O-D 경로를 구하고, 이를 운전자에게 실시간으로 제공할 수 있도록 한다. 대용량 트랜잭션의 관리 및 처리는 모든 노드, 링크, 각종 O-D 경로 정보 등을 대규모, 중규모 및 소규모 도로망으로 구분하여 대용량 데이터베이스의 관리 및처 리를 간소화한다.
이 논문에서 경로는 전문가의 제시, 인공지능 알고리듬과 수리적 알고리듬의 세 가지 방법에 의하여 구해진다. 이들 경 로는 전문가들(직업 운전자, 자가용 출•퇴근 운전자, 교통 관 련 업무자등)에 의해 비교, 검토되어 적합성 등급이 매겨지고, 이를 수시로 점검, 갱신됨으로써 이 시스템은 지능형의 성격 과 학습 능력을 갖는다.
이러한 전문가의 지식, 경험, 규칙 등을 경험적 해법인 A* 알고리 듬(Dechter and Pearl, 1985; Gelperin, 1977)과 병 합하여 새 로운 알고리듬을 개발한다. 즉, 기존 A* 알고리듬의 노드 탐색에서 위의 사항들을 고려하여 탐색 대상을 줄인다.
저절에서는 시스템을 설계하고 운영하는 방법을 제시한다. 이를 위하여 시스템 구조의 각 부분을 모듈별로 구성하며, 시 스템의 기초가 되는 데이터베이스(DB : Database)를 구축하고, 시스템의 운영 방법을 제시한다. 여기에서 지능형의 성격을 갖기 위하여 수리적 알고리듬과 함께 전문가의 지식을 획득하 여 활용하는 방법을 개발한다.
최종 경로는 도로망의 규모별로 정해져 있는 경로들을 비교하여 찾는 CGM을 적용한다. 아울러 여러 개의 도로망으로 분할하여 하나의 도로망에서 구한 지역(Local) 최적해를 이용하여 전역 (Global) 최적해를 구하는 분할 알고리듬(DA: Decomposition Algorithm), 출발지와 도착지의 양쪽 방향에서 동시에 탐색을 시도하는 양방향 탐색(BS: Bi-directional Search) 등이 적용된다.

대상 데이터

구체적인 사례로서 이 시스템은 우리나라 전국 규모의 간선도로망에서 100개 노드와254개 링크, 서울특별시 규모의 주요도로망에서 102개 노드와 354개 링크, 그리고 성북-동대문구 규모의 상세 도로망에서 96개 노드와 320개 링크를 대상으로 운영되었다. 많은 경우에 세 가지 방법들은 납득할 만한 경로들을 찾고 있다.

이론/모형

본 시스템은 Microsoft사의 Access 2000을 사용한다. 이는 관계형 DBMS로서, 이차원의 테이블, 즉 행과 열로 구성되는 데이터 구조를 이루고 있다.
주어진 도로망 내의 모든 노드들 간의 경로를 결정하므로 이 에 가장 적 합하면서 최 적 알고리듬으로 알려 진(Backhouse a al., 1994), Dijkstra 알고리듬(Nemhauser, 1988)과 Floyd-Warshall 알고리듬(Ahujaer此 1993)을 적용한다. 이 시스템에서는 이들 최적 알고리듬 이외에도 보다 더 실제적인 교통 상황(회전 금지, U 턴, P 턴 둥)과 교통망의 복잡도를 고려하면서 탐색 시간을 줄이는 어떠한 다른 경험적(heuristic) 해법(예를 들면 유전자 알고리듬, Kim er”, 2001)도 수용할 수 있다.
또한 이 시스템은 도로의 정상적인 상 황과 돌발적인 상황을 구분하여 지능형 경로를 결정함으로써 실용성을 높인다. 참고로 이 시스템에는 경로를 보다 빠른 시 간에 탐색하기 위하여 독자적으로 개발한 단계적 세분화 방법 (CGM : Coarse Grid Method)을 적용한다. 아울러 분할 알고리듬 (DA : Decomposition Algorithm), 양방향 팀색(BS : Bi-directional Search) 등이 적용된다.
또한 이 시스템은 도로의 정상적인 상 황과 돌발적인 상황을 구분하여 지능형 경로를 결정함으로써 실용성을 높인다. 참고로 이 시스템에는 경로를 보다 빠른 시 간에 탐색하기 위하여 독자적으로 개발한 단계적 세분화 방법 (CGM : Coarse Grid Method)을 적용한다. 아울러 분할 알고리듬 (DA : Decomposition Algorithm), 양방향 팀색(BS : Bi-directional Search) 등이 적용된다.

성능/효과

세 가지 방법에 의한 경로들이 모두 일치하는 것은 전국 도로망의 경우 87%, 서울특별시 도로망의 경우 76%, 성북-동대 문구 도로망의 경우 67%에 달하여 도로망이 세분화될수록 일 치하는 비율이 감소한다. 그 이유는 규모가 작아질수록 링크 간의 거리가 짧아져 약간의 차이도 큰 변동을 가져오기 때문 일 것이다.

후속연구

이들 경 로는 전문가들(직업 운전자, 자가용 출•퇴근 운전자, 교통 관 련 업무자등)에 의해 비교, 검토되어 적합성 등급이 매겨지고, 이를 수시로 점검, 갱신됨으로써 이 시스템은 지능형의 성격 과 학습 능력을 갖는다. 또한 이 시스템은 도로의 정상적인 상 황과 돌발적인 상황을 구분하여 지능형 경로를 결정함으로써 실용성을 높인다. 참고로 이 시스템에는 경로를 보다 빠른 시 간에 탐색하기 위하여 독자적으로 개발한 단계적 세분화 방법 (CGM : Coarse Grid Method)을 적용한다.
이들 경 로는 전문가들(직업 운전자, 자가용 출•퇴근 운전자, 교통 관 련 업무자등)에 의해 비교, 검토되어 적합성 등급이 매겨지고, 이를 수시로 점검, 갱신됨으로써 이 시스템은 지능형의 성격 과 학습 능력을 갖는다. 또한 이 시스템은 도로의 정상적인 상 황과 돌발적인 상황을 구분하여 지능형 경로를 결정함으로써 실용성을 높인다. 참고로 이 시스템에는 경로를 보다 빠른 시 간에 탐색하기 위하여 독자적으로 개발한 단계적 세분화 방법 (CGM : Coarse Grid Method)을 적용한다.
이 시스템은 러시 아워(rush-hour), 교통사고 등으로 인한 교통 혼잡도에 따라 그때그때 경로를 변경하는 등의 운전자 판단을 쉽게 반영할 수 있다. 앞으로 이 시스템이 충분히 정교하여져서 실용화되기를 기대한다,
이 시스템은 소프트웨어로 개발된다. 이 시스템을 우리나라 전국의 실제 도로망에 적용하여 운전자에게 적합한 경로를 실 시간으로 조언함으로써, 교통 문제의 심각성을 해 결할 수 있 는 기반이 될 수 있음을 보인다. 이 시스템은 보다 더 실제적 인 상황통행시간, 신호체 계 등)을 고려할 수 있고 또한 보다 적 절 한 다른 알고리듬들을 수용할 수 있다.
시스템 사용자(운전자)로부터 O-D 경로의 질의가 들어오면, 오프라인으로 미리 구축된 DB의 정보를 이용하여 온라인에서 최소한의 비교로써 경로를 결정하고 이를 운전자에게 조언한다. 한편, 교통 사고, 교통 정체, 집회, 도로 공사등 돌발적 인 상황이 발생하는 경우에는 온라인으로 가장 빨리 수행되는 인공지능 알고리듬을 적용하여 경로를 구하고 이를 운전자에게 조언한다.

참고문헌 (24)

Adler, J. I. (2001), Investigating the learning effects of route guidance and traffic advisories on route choice behavior, Transportation Research: Part C,9, 1-14
Adler, J. I. and Blue, V.J. (1998), Toward the design of intelligent traveler information systems, Transportation Research: Part C,6, 157-172
Ahuja, R K, Magnanti, T.I. and Orlin, J. B.(1993), Network Flows, Prentice Hall
Backhouse.R, C, vanden Eijnde,J. P. H. W. and van Gasteren, A.J. M.(1994), Calculating path algorithms, Science of Computer Programming, 22, 3-19
Batini, C, Ceri, S. and Navathe, S. B.(1992), Conceptual Database Design, The Benjamin/Cummings Publishing Company, Inc
Dechter, R and Pearl, J. (1985), Generalized best-first search strategies and the optimality of A*,Journal of the Association for Computing Machine,. 32(3), 505-536
Elmasri, Rand Navarhe, S. B.(1994), Fundamentals of Database systems, Addison-Wesley Publishing Company
Garda-Ortiz, A.,Amin, S.M.and Wootton,J.R (1995), Intelligent transportation systems enabling technologies, Mathematical and Computer Modeling, 22(4-7),11-81
Gelperin, D. (1977), On the optimality of A*,Artificial Intelligence, 8, 69-76
Han, Y., Pan, V. Y. and Reif, J. H. (1997), Efficient parallel algorithm for computing all pair shortest paths in directed graphs, Algorithmica, 17, 399-415
Herland, I., Moller, B. and Schandersson, R (2000), Knowledge acquisition, verification, and validation in an expert system for improved traffic safety, Transportation Research Record, Issue. 1739,83-91
Kaysi, I., Ben-Akiva, M. andKoutsopoulos, H.(1993), Integrated approach to vehicle routing and congestion prediction for real-time driver guidance, Transportation Research Record, Issue. 1408, 66-74
Kim D. H. (2000), Estimation of nation wide traffic congestion costs in 1999 and its trend, Report of Traffic Development Institute
Kim, H. K. (2002), Design and implementation of an intelligent system for real-time route advice in a complicated large network, Ph.D. Dissertation, Korea University
Kim, S. S.,Jeong, J. D. and Lee J. H. (2001), Development of dynamic route guidance system for multiple shortest paths using genetic algorirhm, IE Interfaces, 14(4),374-384
Lee, C. (1994), A multiple-path routing strategy for vehicle route guidance systems, Transportation Research: Part C,2(3),185-195
Nemhauser, G. I. (1988), Integer and Combinatorial Optimization, John Wiley & Sons, Inc
Rowe, N. C. (1988), Artificial Intelligence through Prolog, Prentice-Hall, Inc
Sen, S., Pillai, R, Joshi,S. and Rathi, A.K. (2001), Amean-variance model for route guidance in advanced traveler information systems, Transportation Saence, 35(1), 37-49
Sen, A.and Thakuriah, P. (1995), Estimation of static travel times in a dynamic route guidance system, Mathematical and Computer Modeling, 22(4-7), 83-101
Thakuriah, P. and Sen, A.(1996), Quality of information given by advanced traveler information systems, Transportation Research: Part C,4(5), 249-266
Wahle,J., Annen, O., Schuster, C, Neubert, I. and Schreckenberg, M.(2001), A dynamic route guidance system based on real traffic data, European Journal of Operational Research, 131,302-308
Yu,G. and Yang,J. (1998), On the robust path problem, Computers and Operations Research; 25(6), 457-468
Ziliaskopoulos, A., Kotzinos, D. and Mahmassani, H. S.(1997), Design and implementation of parallel time-dependent least time path algorithms for intelligent transportation systems applications, Transportation Research: Part C, 5(2), 95-107

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증