[논문]비대칭 비용함수 기반의 통행배정모형 해석에 관한 연구

박준환; 신성일; 임용택

비대칭 비용함수 기반의 통행배정모형 해석에 관한 연구
Study on the Solution of the Assignment Model Based on an Asymmetric Cost Function 원문보기

大韓交通學會誌 = Journal of Korean Society of Transportation, v.25 no.6, 2007년, pp.161 - 170

박준환 (서울시정개발연구원) , 신성일 (서울시정개발연구원) , 임용택 (전남대학교 교통물류학부)

초록
AI-Helper

본 연구에서는 통행배정 모형이 갖는 여러 가지 가정 중 대칭적 통행비용 함수를 갖는 가정을 극복할 수 있는 방법에 대해 살펴보았다. 통행배정 문제에 있어서 대칭적 비용함수 가정이라는 것은 링크의 통행비용은 다른 링크의 교통량에 전혀 영향을 받지 않는 않으면서, 동시에 해당 링크를 통과하는 단하나의 수단에 의해서만 결정된다는 의미이다. 본 연구에서는 이러한 가정을 극복할 수 있는 비대칭 통행배정모형의 특성을 살펴보고, 그 해석 모형에 대해 고찰하였다. 이 때 대표적 비대칭 통행배정 문제인 다수단 통행배정 모형을 중심으로 문제를 정의하여 검토하였다. 대각화(Diagonalized) 알고리즘과 Column Generation에 기반한 heuristic 모형을 다수단 통행배정 모형에 적용하여 그 결과를 분석하였다. 그 과정을 통해 대각화 알고리즘은 초기해의 수단과 수렴기준 수단에 따라 서로다른 해를 갖는 복수의 평형해(Equilibria)특성을 가지고 있음을 확인하였다. 그에 비해 Column Generation에 기반한 heuristic 모형은 Euclidean Norm을 이용한 부분최적화를 통해 복수의 평형해(Equilibria)에 관한 문제점을 개선할 수 있었다.

Abstract ▼ AI-Helper

The purpose of this study is to find the solution that overcomes the existing assumption of symmetric cost functions in multi-class assignment. In the assignment problem, the assumption of a symmetric cost function means that the link cost is determined by each unique mode and is not affected by any other modes. In this study, the authors have applied a diagonalized algorithm and a heuristic model based on column generation to a multi-class assignment model and analyzed the result. Through the study, the authors found that the diagonalized algorithm produces equilibrium solutions by the initial convergence condition. In contrast to the diagonalized algorithm, the column generation algorithm has improved the solution model to overcome the problem of equilibrium solutions in the diagonalized algorithm.

주제어

AI 본문요약
AI-Helper

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

문제 정의

다음 절에서는 이러한 한계를 개선하기 위해 Column Generation을 이용한 heuristic 모형을 활용하는 방안을 살펴본다.
본 연구에서는 비대칭 통행배정모형의 특성을 살펴보고, 그 해석 모형에 대해 고찰한다. 이 때 대표적 비대칭 통행배정 문제인 다수단 통행배정 모형을 중심으로 문제를 정의하여 검토한다.
본 연구에서는 여러 가지 가정 중 대칭적 통행비용 함수를 갖는 가정을 극복할 수 있는 방법에 대해 논의하고자 한다. 통행배정 문제에 있어서 대칭적 비용함수 가정이라는 것은 하나의 링크 통행비용이 해당 링크의 교통량에 의해서만 결정된다는 가정을 의미한다.
본 연구에서는 이러한 가정을 극복할 수 있는 비대칭 통행배정모형의 특성을 살펴보고, 그 해석 모형에 대해 고찰하였다. 이 때 대표적 비대칭 통행배정 문제인 다수단 통행배정 모형을 중심으로 문제를 정의하여 검토하였다.
앞 절에서 제시한 대각화 알고리즘이 제시하는 해의 특성이 본 사례에서 잘 나타난다. 본 연구에서는 초기수 단정의에 따라 서로 다른 해를 도출하는 결과를 제시하였다. 즉, 승용차와 버스를 각각 초기해로 설정할 경우 서로 다른 해가 도출됨을 알 수 있다.
본 연구에서는 통행배정 모형이 갖는 여러 가지 가정 중 대칭적 통행비용 함수를 갖는 가정을 극복할 수 있는 방법에 대해 살펴보았다. 통행배정 문제에 있어서 대칭적 비용함수 가정이라는 것은 링크의 통행비용은 다른 링크의 교통량에 전혀 영향을 받지 않는 않으면서, 동시에 해당 링크를 통과하는 단하나의 수단에 의해서만 결정된다는 의미이다.
이 때 대표적 비대칭 통행배정 문제인 다수단 통행배정 모형을 중심으로 문제를 정의하여 검토한다. 비대칭 통행배정 모형의 특성을 기반으로 기존에 사용되던 해석 모형의 문제점을 검토하여 새로운 방법론을 모색해 보고자 한다. 더불어 예제 네트워크를 대상으로 해석 알고리즘을 적용하여 평가한다.

가설 설정

더불어 과 같은 네트워크 속성을 갖는 것으로 가정 하였다.
이 때 버스의 경우 노선별 배차간격에 따라 교통량이 결정되어 있는 것으로 가정하였다.

제안 방법

그 연구에서는 승용차와 버스, 트럭으로 구성된 통행 배정모형을 바탕으로 대각화 알고리즘을 적용하여 해를 도출하였다¹⁾. 이 때 링크 a의 비용은 식(6)과 같이 정의할 수 있다.
균형해를 도출한 후 Attractive line 집합을 정리하게 되고, 교통량이 0인 경로는 Attractive line에서 제외된다. 그리고 링크 통행량, 최적 경로 등 통행배정 결과를 제시한다.
그리하여 결과의 차이를 비교할 수 있다. 그리고, 3개 수단의 경우에 대해 Column Generation Method를 적용한 분석 사례를 살펴본다.
그리고, 업데이터된 교통량 및 경로통행비용의 수렴 여부에 대해 검토하는 과정을 통해 수렴해를 판단한다. 이 때 수렴조건은 iteration에 따른 경로별 통행비용의 일치 여부에 따라 판단하게 된다.
비대칭 통행배정 모형의 특성을 기반으로 기존에 사용되던 해석 모형의 문제점을 검토하여 새로운 방법론을 모색해 보고자 한다. 더불어 예제 네트워크를 대상으로 해석 알고리즘을 적용하여 평가한다. 적용한 결과를 바탕으로 알고리즘의 특성을 분석하여 각 알고리즘의 장점과 한계를 구체화한다.
비대칭 비용함수에 관한 해석모형을 검토하기 위해 대표적 비대칭 비용함수 문제인 다수단 통행배정 모형을 통해 문제의 해석방법을 검토한다.
앞 절에서 제시한 Column Generation Method을 기반으로 한 heuristic 알고리즘과 대각화 알고리즘을 하나의 통행배정 문제에 적용하여 본다. 그리하여 결과의 차이를 비교할 수 있다.
본 연구에서는 이러한 가정을 극복할 수 있는 비대칭 통행배정모형의 특성을 살펴보고, 그 해석 모형에 대해 고찰하였다. 이 때 대표적 비대칭 통행배정 문제인 다수단 통행배정 모형을 중심으로 문제를 정의하여 검토하였다.
더불어 예제 네트워크를 대상으로 해석 알고리즘을 적용하여 평가한다. 적용한 결과를 바탕으로 알고리즘의 특성을 분석하여 각 알고리즘의 장점과 한계를 구체화한다.
지금까지 정의한 다수단 통행배정 모형을 기반으로 한 비대칭통행배정 모형을 살펴보았다. Column generation 알고리즘을 이용하여 도출한 해를 각 링크별, 경로별, 수단별로 정리하면 <그림 11> 및 <표 13>과 같다.
지금까지의 Column Generation 알고리즘 기반의 heuristic 알고리즘을 보다 구체적인 다수단 통행배정에 적용하여 균형해의 도출 여부를 살펴본다.
하나의 다수단 통행배정 문제를 대각화 알고리즘과 Column Generation 알고리즘을 이용하여 해석한 결과를 살펴본다.

이론/모형

Xu et al.(2006)의 연구를 통해 더욱 발전된 형태로 개선된 Column Generation Method 기반의 heuristic method를 적용한다.
같은 문제를 Column Generation Method를 사용하여 풀이한 결과를 과 에 제시하였다.
다중수단 통행배정에서는 비용함수 설정이 중요한데 본 연구에서는 김현철(1997)에서 제시한 다음과 같은 조건에 따라 함수를 설정하였다.
대각화 알고리즘을 보다 구체적으로 살펴보기 위해 다수단 통행배정 모형을 정의하여 대각화 알고리즘을 적용해 볼 필요가 있다. 대각화 알고리즘을 이용한 다수단 통행배정문제는 김현철(1997)에서 제시한 내용을 중심으로 살펴본다.
대각화(Diagonalized) 알고리즘과 Column Generation에 기반한 heuristic 모형을 다수단 통행배정 모형에 적용하여 그 결과를 분석하였다. 그 과정을 통해 대각화 알고리즘은 초기해의 수단과 수렴기준 수단에 따라 여러개의 균형해(Equilibria)를 갖는 특성을 가지고 있었다.

성능/효과

각 링크별로 도출된 승용차(A)와 트럭(T)의 통행배정 결과를 <그림 4>～<그림 7>을 통해 제시하였다. 그 결과 초기해의 조건과 수렴조건의 기준수단에 따라 링크별 통행량이 차이가 있음을 확인할 수 있다.
그 과정을 통해 대각화 알고리즘은 초기해의 수단과 수렴기준 수단에 따라 여러개의 균형해(Equilibria)를 갖는 특성을 가지고 있었다. 그에 비해 Column Generation에 기반한 heuristic 모형은 Euclidean Norm을 이용한 부분최적화를 통해 하나의 균형해를 얻을 수 있다는 사실을 제시하였다.
대각화 알고리즘을 이용하여 풀이한 통행배정 모형의 결과는 다수의 해를 갖는 것으로 나타났다. 다수해는 수단별 초기해 도출 순서와 수렴 조건의 기준 수단에 따라 총 4개의 해를 갖는 것으로 나타났다.
첫째, 각 차종이 동일한 V/C비를 갖는 링크에 있어서 차종별 통행비용의 크기는 비혼잡상태의 경우 트럭이 가장 크고, 버스, 승용차의 순서이다. 둘째, 트럭과 버스의 통행비용 차이는 버스와 승용차와의 차이에 비해 크지 않다. 셋째, 혼잡상태에 가까워지면 세 차종의 통행비용은 수렴하게 된다.
본 모형의 적용 결과 경로별 통행비용이 균형을 이루게 됨을 알 수 있었다. 더불어 각 링크별 수단별 통행량이 도출되었고, 대각화 알고리즘과는 달리 수렴조건에 따른 여러 개의 균형해(Equilibria)를 갖는 문제점은 해결된다.
둘째, 트럭과 버스의 통행비용 차이는 버스와 승용차와의 차이에 비해 크지 않다. 셋째, 혼잡상태에 가까워지면 세 차종의 통행비용은 수렴하게 된다. 이러한 조건을 바탕으로 제시된 각 차종별 통행비용함수는 식(12)와 같다.
첫째, 각 차종이 동일한 V/C비를 갖는 링크에 있어서 차종별 통행비용의 크기는 비혼잡상태의 경우 트럭이 가장 크고, 버스, 승용차의 순서이다. 둘째, 트럭과 버스의 통행비용 차이는 버스와 승용차와의 차이에 비해 크지 않다.

후속연구

본 연구결과를 기반으로 향후 보다 개선된 해를 갖는 해석모형의 개발 및 활용이 이루어지기를 바란다.
본 연구를 통해 새롭게 제시할 수 있는 연구 과제가 몇가지 있다. 첫째, 비대칭 비용함수는 승용차 통행배정모형 비용함수의 대칭성 가정에 대한 개선을 다룬 것인데, 이런 방법을 대중교통 통행배정이나 통행자의 다양한 특성을 반영할 수 있는 연구에 적용할 수 있도록 하여야 할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	통행배정 모형이란?	교통 수요예측의 주요한 과정 중 하나인 통행배정 모형은 여러 가지 많은 가정을 포함하고 있다. 예를 들어, 모든 운전자는 모든 경로의 통행비용을 알고 있다거나, 각 링크의 통행비용은 그 링크를 이용하는 통행량에 의해서만 결정된는 가정 등을 바탕으로 모형이 구축되어 있다.
	비대칭 통행배정의 비용함수는 어떤 형태로 구분할 수 있는가?	비대칭 통행배정의 비용함수는 우선 자신의 링크교통량만의 함수인 형태와 다른 링크교통량의 영향을 고려하는 형태로 구분할 수 있다. 두 형태를 수식으로 표현하면 다음과 같다.
	통행배정 모형은 어떤 가정을 포함하고 있는지 예를 들어보면?	교통 수요예측의 주요한 과정 중 하나인 통행배정 모형은 여러 가지 많은 가정을 포함하고 있다. 예를 들어, 모든 운전자는 모든 경로의 통행비용을 알고 있다거나, 각 링크의 통행비용은 그 링크를 이용하는 통행량에 의해서만 결정된는 가정 등을 바탕으로 모형이 구축되어 있다. 통행배정 모형은 이러한 여러 가정들을 극복해가는 과정을 통해 개선되고 발전되고 있다.

참고문헌 (7)

김현철.(1997), '복수수단 통행배정모형에 의한 대기오염물질의 배출량 산정에 관한 연구', 서울대학교 석사학위 논문
백승걸(2001), '유전알고리즘을 이용한 링크관측교통량으로부터의 기종점 통행행렬 추정', 서울대학교 박사학위 논문
임강원, 임용택(2004), '교통망 분석론', 서울대학교 출판부
Howard Anton and Robert Busby(2004), 'Contemporary linear algebra', John Wiley & Sons
M.H. Xu, W.H.K. Lam, H. Shao, G.F. Luan (2006), 'A heuristic algorithm for network equilibration', Applied Mathematics and Computation, 174, pp.430-446

상세보기
T. Leventhal, G. Nemhauser, L. Trotter, Jr. (1973), 'A column generation algorithm for optimal traffic assignment', Trans. Sci., Vol. 7, pp.168-176

상세보기
William H.K. Lam & Hai-jun Huang(1992), 'A combined trip distribution and assignment for multiple user classes', TR- B, Vol 26, no. 4, pp pp.275-287

저자의 다른 논문 :

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

연합인증