[논문]회전 제약을 포함하고 있는 교통 네트워크의 경로 유도를 위한 개미 알고리즘

김성수; 안승범; 홍정기; 문재기

[국내논문] 회전 제약을 포함하고 있는 교통 네트워크의 경로 유도를 위한 개미 알고리즘
Ant Algorithm for Dynamic Route Guidance in Traffic Networks with Traffic Constraints 원문보기

大韓交通學會誌 = Journal of Korean Society of Transportation, v.26 no.5 = no.104, 2008년, pp.185 - 194

김성수 (강원대학교 산업공학과) , 안승범 (인천대학교 동북아물류대학원) , 홍정기 (강원대학교 산업공학과) , 문재기 (강원대학교 산업공학과)

초록
AI-Helper

본 논문에서는 기본적으로 라우팅(routing) 메커니즘을 이용하는 개미 알고리즘(ant algorithm)을 이용하여 실시간으로 변화하는 교통 상황과 U턴, P턴 및 회전제약(좌회전 및 U턴 금지)을 고려하여 다수의 최적경로를 제한된 시간내에 탐색제시 할 수 있는 경로 유도 방법을 제시하고자 한다. 이 방법은 기존 최적경로알고리즘과 비교하여 회전 제약 상황을 쉽고 빠르게 고려할 수 있는 장점이 있다.

Abstract ▼ AI-Helper

The objective of this paper is to design the dynamic route guidance system(DRGS) and develop an ant algorithm based on routing mechanism for finding the multiple shortest paths within limited time in real traffic network. The proposed ant algorithm finds a collection of paths between source and destination considering turn-restrictions, U-turn, and P-turn until an acceptable solution is reached. This method can consider traffic constraints easily comparing to the conventional shortest paths algorithms.

주제어

AI 본문요약
AI-Helper

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

문제 정의

대하여 간략하게 소개하였다. 다음 4절에서는 개미알고리즘의 수행방법을 설명하고 그 방법을 토대로 제약이 있는 경로에서의 최적경로 수행을 제시하고자 한다.
따라서, 본 논문에서는 기본적으로 라우팅 (routing) 메커니즘을 이용하는 개미 알고리즘(ant algorithm)을이용하여 실시간으로 변화하는 교통 상황과 회전제약을 고려하여 다수의 최적경로를 탐색제시 할 수 있는 경로 유도 방법을 제시하고자 한다. 이 방법의 장점은 가능해 생성 시 경로 제약의 여부를 보다 빠르게 확인 가능하다.
본 논문에서는 첨단교통정보시스템에서 다수 최적 경로를 제공할 수 있도록 개미알고리즘을 사용하여 경로 안내 시스템을 설계하고 시스템 프로토타입을 개발하였다. 개미알고리즘은 교통네트워크에서 회전금지, U턴 및 P턴 금지 등을 고려하여 제한된 시간내에 최적 경로를 제공할 수 있었다.
본 절에서는의 최적경로안내시스템의 핵심정보인 최적경로를 찾아내기 위해 사용될 개미알고리즘에 대하여 간략하게 소개하였다.

가설 설정

경로의 중심노드인 4. 6, 7, 11, 16, 19, 22에서만 순환경로(U턴, P턴)가 가능하다고 가정한다.
그리고 각 호의 비용값 또한과 같이 임의로 가정하였다.
그리고 각 호의 비용값 또한와 같이 임의로 가정하였다.
시작 노드는 학동(노드1), 도착노드는 대곡초등학교(노드24)로 가정한다. 그리고 각 호의 비용값 또한<그림 12>와 같이 임의로 가정하였다.
시작노드는 노드1, 도착노드는 노드46로 가정한다. 그리고 각 호의 비용값 또한<그림 10>과 같이 임의로 가정하였다.

제안 방법

이 방법의 장점은 가능해 생성 시 경로 제약의 여부를 보다 빠르게 확인 가능하다. 또한, 이러한 정보들을 미리 정해진 시간내에 서비스할 수 있는 정보시스템을 설계하고 Visual C+ +을 사용하여 시스템 프로토타입을 개발하였다. Dorigo, M 등 (2006)의 최근 개미알고리즘 적용 사례 연구 논문에 따르면 라우팅(routing), 할당, 스케쥴링 문제 등 다양한 문제에 적용되었으나 회전금지 등 제약 사항이 고려된 교통 네트워크 문제에 적용한 사례는 아직 없는 것으로 조사되었다.
있음을 유주할 수 있었다. 본 논문에서 제시한 알고리즘이 혼잡도가 큰 상황하에서도 최적값에 수렴한다는 것을 컴퓨터 시뮬레이션을 통하여 검증하였다.
본 논문에서는 지금까지 설명한 개미알고리즘 수행 절차에 따라 C+ + 언어를 사용하여 개미알고리즘 수행 과정을 프로그램 하였다. 이 프로그램은 교통네트워크의 변경이나 고객의 요구에 의해 사용자에 따라<표 1>과 같은 권한이 부여되고 정보 내용의 입력 데이터 파일을 생성하여 입력하여 주기만 하면 된다.
서울시 강남구의 실제지도를 교통네트워크으로 표시한 것이인데, 각 교차로를 노드번호로 표시하였고 각 교차로에 근접한 소재지를 지명으로 표시하였다.
008, 페로몬 업데이트 상수는 1, 엘리트 가중치를 1, 페로몬과 선호도의 가중치는 2와 1로 주어 1000세대를 진행했을 때 개미 알고리즘 모의실험을 하였다. 시간적인 단축을 위하여 종료조건을 100마리의 개미군이 연속적으로 같은 최적값을 가질 경우에도 종료를 하도록 설정하였다.
페로몬과 선호도의 가중치는 2와 1로 주어 1000세대를 돌렸을 경우 최적 네트워크를 위한 개미 알고리즘 모이실험을 하였다. 시간적인 단축을 위하여 종료조건을 50세대이상 같은 경로가 나올 경우예도 종료를 하도록 설정하였다.
<그림 12>예제에서 개미군의 개미수는 4마리, 증발율을 0.1, 초기 페로몬을 0.008, 페로몬 업데이트 상수는 1, 엘리트 가중치를 1, 페로몬과 선호도의 가중치는 2와 1로 주어 1000세대를 진행했을 때 개미 알고리즘 모의실험을 하였다. 시간적인 단축을 위하여 종료조건을 100마리의 개미군이 연속적으로 같은 최적값을 가질 경우에도 종료를 하도록 설정하였다.
페로몬 업데이트 값은 개미의 이동 방향에 따라 페로몬의 업데이트를 다르게 적용하여 페로몬에 따른 개미의 이동에 방향성을 주어 실제와 같이 양방향 교통 상황을 고려하였다.
008, 페로몬 업데이트 상수는 1, 엘리트 가중치를 1. 페로몬과 선호도의 가중치는 2와 1로 주어 1000세대를 돌렸을 경우 최적 네트워크를 위한 개미 알고리즘 모이실험을 하였다. 시간적인 단축을 위하여 종료조건을 50세대이상 같은 경로가 나올 경우예도 종료를 하도록 설정하였다.
회전 제약 조건들을과 같은 배열로 설정하여 이동확률 계산 시 제약 조건들을 고려하였다.
것을 보여준다. 회전 제약이 있기 전과 후를 보면 노드1을 거쳐 2에서 3으로 가는 것이 회전금지 제약이기 때문에 노드2에서 3으로 가는 확률이 계산되지 않도록 시뮬레이션 하였다.
회전금지 경로(1—>4—5, 3—6-, 8-^7^13, 1A 1—5, 1CH₆T7, 13^19―>18, 18—*22—>23)는 7개 지역으로 임의적으로 정하였고, 실제 교통네트워크에서 회전금지를 극복하기 위해 U턴이나 P턴을 사용하기 때문에 회전금지 경로의 중심노드인 4. 6, 7, 11, 16, 19, 22에서만 순환경로(U턴, P턴)가 가능하다고 가정한다.

이론/모형

한 개미당 경로해가 완성되면 그 해에 대한 로컬 페로몬업데이트(local pheromone update)를 식 (4)에 따라 시행한다. 한 개미 군의 모든 경로해가 완성되면 모든 경로해 중에서 가장 평가 값이 좋은 경로해에 대하여 글로벌 페로몬업데이트 (global pheromone updateX 식(5)에 따라 시행한다. 이 과정을 거친 후 종료조건을 만족하게 되면 종료하게 되고 그렇지 않으면 위 과정을 반복 적용하게 된다.

성능/효과

개미알고리즘 진행 결과는 펜티움IV PC를 사용하여 수초 내에 결과를 얻을 수 있었으며, 결과를 종합해보면 첫 세대의 개미들 중 최적경로길이는 167이였으며 최종단계에서의 개미의 최적경로길이는 33으로 나타나 새로운 최적의 값을 얻을 수 있었다.
이 진화 프로그램은 세대수 100에서 종료조건 (100 마리 이상이 같은 값)을 충족하여 종료하였고, 펜티엄IV PC를 사용하여 0.469초에 결과를 얻을 수 있었다.<그림 13>은 개미의 이동이 진행됨에 따른 평가값의 추이를 나타낸 것이다.
이와 같이 개미알고리즘으로 구한 최적경로가 Dijkstra 알고리즘으로 구한 경로와 일치함으로 제시한 개미알고리즘에 대하여 검증할 수 있었고 혼잡도가 큰 경우에도 본 논문에서 제시한 최적경로 알고리즘이 제 역할을 할 수 있음을 유주할 수 있었다. 본 논문에서 제시한 알고리즘이 혼잡도가 큰 상황하에서도 최적값에 수렴한다는 것을 컴퓨터 시뮬레이션을 통하여 검증하였다.
즉, GPS 데이터 분석을 통한 차량통행시간을 시시각각 예측하여 이를 바탕으로 실제 교통네트워크에서 본 논문에서 제안한 알고리즘으로 최적경로들을 산출해 낼 수 있다.

후속연구

즉, 문제 크기가 커지고 회전금지, U-turn, U-turn 금지, P-turn 등이 다양하게 겹쳐있어 복잡도가 높아지면 휴리스틱 알고리즘이 아닌 기존 알고리즘을 적용하기 어렵고(최기주, 1995) 계산시간이 기하급수적으로 증가하여 제한된 시간내에 최적해를 찾아낼 수 없고 제약 사항을 고려하기 쉽지 않다. 따라서, 이러한 기존 알고리즘의 단점을 극복하고 각종 제약 사항뿐만 아니라 동적 교통상황을 고려하여 큰 공간의 대규모 네트워크의 복잡한 도로 교통 네트워크에 대해서 주행 시간을 기준으로 출발지에서 목적지까지의 실질적인 최적 경로들을 사용자가 정보를 요구하는 시간내에 효과적으로 도출해내는 휴리스틱 알고리즘의 개발이 요구된다.

참고문헌 (18)

강맹규(1991), "네트워크와 알고리즘", 박영사
김성수.정종두.이종현(2001), "유전자 알고리즘을 사용하여 다수최적경로를 제공할 수 있는 경로유도시스템의 개발", 대한산업공학회, 제14권 제4호, pp.374-384
이상열(2002), "개미시스템 알고리듬을 이용한 동적경로 계획", ABSTRACT 학술대회 논문집 2002년 추계, pp.281-284
최규석.우광방(1997), "지능형 주행 안내 시스템을 위한 유전 알고리즘에 근거한 최적 경로 탐색 알고리즘", 제어.자동화.시스템공학 논문지
최기주(1995), "U-TURN을 포함한 가로망 표현 및 최단경로의 구현", 대한교통학회지, 제13권 제 3호, 대한교통학회, pp.35-52
Ben-Akiva, Moshe, Koutsopoulos, Haris N. and Mukandan, Anil(1994), "A dynamic traffic model system for ATMS/ATIS operations", IVHS Journal, Vol.1(4), pp.1-19
Dorigo, M, Birattari, M. and Stutzle T. (2006), "Ant Colony Optimization", IEEE Computational Intelligence Magazine, Nov. 2006
Dorigo, M., Maniezzo, V. and Colorni, A., (1996), "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Trans. on Systems, Man, and Cybernetics-Part B: Cybernetics, Vol. 26, No 1, Feb., pp.29-41

상세보기
Dorigo, M., Gambardella, L. M. (1997), "Ant Colony System: A Cooperative Learning Approach to the Travaling Salesman Problem", IEEE Trans. on Evolutionary Computation, 1, pp.53-66

상세보기
Dorigo, M. and Stutzle T. (2001), "The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, Metaheuristics Handbook, Glover and Kochenberger (Eds.)", International Seriesin Operations Researchand Management Science, Kluwer
Dorigo, M. and Stutzle T. (2004), "The Ant Colony Optimization, A Bradford Book", The MIT Press, Cambridge, Massachusetts, London, England
Gen, M., Cheng, R. and Wang, D.(1997), "Genetic Algorithms for Solving Shortest Path Problems", Proceedings of the 1997 IEEE International 97 Magnetics Conference
Inagaki, J., Haseyama, M. and Kitajima, H.(1999), "A Genetic Algorithm for Determining Multiple Routes and Its Applications", Proceedings of the 1999 IEEE International Symposium on Circuits ana Systems
Kang, D., HASHIMOTO, H. and HARASHIMA, F.(1997), "Path Generation for Mobile Robot using Genetic Algorithm", Transactions of the Institute of Electrical Engineers of Japan C -A Publication of Electronics, Information and Systems Society.
Kim, Sung-Soo and Lee, Jong-Hyun(2000), "Modified Dijkstra and Floyd-Warshall Algorithms for Turn-restriction, U-turn, and P-turn in Traffic Network", INFORMS Seoul 2000 Conference
Kim, Sung-Soo and Lee, Jong-Hyun(1999), 　"A Study on Design of Dynamic Route Guidance System Using Forecasted Travel Time Based on GPS Data and Modified Shortest Path Algorithm", IEEE International Conference on Intelligent transportation Systems, Japan
Seo, K. and Choi, G.(1998), "The Genetic Algorithm Based Route Finding Method for Alternative Paths", Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics
Voicu, L. I. and Myler, H. R.(1998), "Cloning operator and its applications", Proceedings of the Applications and Science of Computational Intelligence

저자의 다른 논문 :

표제어: 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

연합인증