[논문]누적환승함수를 고려한 경험적 최적경로탐색 방안

신성일; 백남철; 남두희

doi:10.12815/kits.2016.15.3.060

누적환승함수를 고려한 경험적 최적경로탐색 방안
A Heuristic Optimal Path Search Considering Cumulative Transfer Functions 원문보기

韓國ITS學會論文誌 = The journal of the Korea Institute of Intelligent Transportation Systems, v.15 no.3, 2016년, pp.60 - 67

신성일 (서울연구원 교통시스템연구실) , 백남철 (한국건설기술연구원, ICT융합연구소) , 남두희 (한성대학교 공과대학 정보시스템공학과)

초록
AI-Helper

환승누적함수에서 환승회수가 증가되면 환승비용에 대한 개별적인 환승의 영향이 선형 또는 비선형적으로 증가된다. 이 함수는 버스 또는 철도와 같이 대중교통노선에서 경로를 선택하는 승객의 행태를 효과적으로 설명한다. 이 함수로 통행시간이 더 소요되더라도 환승이 적은 대중교통노선을 선택하는 일반적인 상황의 구현이 가능하다. 그러나 환승누적함수가 포함되는 통행비용은 비가산성비용으로 최적경로탐색을 위해서 경로열거라는 어려운 상황을 포함한다. 본 연구는 환승누적함수를 고려하여 최적경로를 탐색하는 효과적인 방안을 제안하였다. 이를 위해 우선 환승누적함수가 포함되는 경우 경로탐색과정에서 나타나는 최적경로역전 현상을 설명하였다. 또한 복수의 경로를 탐색해서 최소의 비용경로를 최적경로로 선택하는 경험적인 방안을 제안하였다. 유입링크기반 전체경로삭제기법을 복수경로탐색기법으로 채택하여 알고리즘의 경로최적조건의 증명성에 기반하여 K개의 경로를 탐색하는 방안을 제안하였다. 환승계수를 도입하는 사례연구를 통하여 제안된 방안의 실제 교통망에 대한 활용성을 논의하였다.

Abstract ▼ AI-Helper

In cumulative transfer functions, as number of transfer increase, the impact of individual transfer to transfer cost increase linearly or non linearly. This function can effectively explain various passengers's travel behavior who choose their travel routes in integrated transit line networks including bus and railway modes. Using the function, it is possible to simulate general situations such that even though more travel times are expected, less number of transfer routes are preferred. However, because travel cost with cumulative transfer function is known as non additive cost function types in route search algorithms, finding an optimal route in integrated transit networks is confronted by the insolvable enumeration of all routes in many cases. This research proposes a methodology for finding an optimal path considering cumulative transfer function. For this purpose, the reversal phenomenon of optimal path generated in route search process is explained. Also a heuristic methodology for selecting an optimal route among multiple routes predefined by the K path algorithm. The incoming link based entire path deletion method is adopted for finding K ranking path thanks to the merit of security of route optimality condition. Through case studies the proposed methodology is discussed in terms of the applicability of real situations.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 연구는 출발지부터 환승이 발생하는 시점까지 환승의 영향을 누적적으로 반영하는 최적경로탐색 수식을 제시했다. 또한 누적환승함수의 사례로서 파라메타로 반영하는 방법을 토이네트워크를 통행 검증했다.
본 연구는 한정된 경로집합의 생성을 통하여 최적경로를 선정하는 효과적인 방안을 제안한다. 제안된 기법은 세 가지 측면- 1) 복수경로탐색의 적용, 2) 최적해의 선정, 3) 실제 교통망에의 적용 -에서 검토된다.

가설 설정

9]은 새롭게 제안된 전체경로삭제기법이다. 일단 최적경로로 가정하고 표지확정을 진행한다. 탐색된 경로에 대하여 비용 등 정보를 갱신한다.

제안 방법

누적환승함수가 포함된 통행비용은 비가산성 문제로서 경로열거가 요구됨을 증명했다. 경로열거에서 표지확정 문제를 우회하는 방안으로 최적경로집합조건을 제시했다. 이 조건을 구축하는 K경로탐색기법으로서 유입링크기반 전체경로삭제 기법을 수정하여 제안했다.
본 연구는 출발지부터 환승이 발생하는 시점까지 환승의 영향을 누적적으로 반영하는 최적경로탐색 수식을 제시했다. 또한 누적환승함수의 사례로서 파라메타로 반영하는 방법을 토이네트워크를 통행 검증했다. 누적환승함수가 포함된 통행비용은 비가산성 문제로서 경로열거가 요구됨을 증명했다.
탐색된 경로에 대하여 비용 등 정보를 갱신한다. 또한 현재까지 구축된 링크 및 노드표지 불확정성을 가정하여 출발지와 도착지를 연결하는 새로운 경로를 경로탐색을 통하여 구축한다. 최종적으로 구축된 경로 K개에 대하여 최적경로를 선정한다.
본 연구에서 최적경로집합조건을 만족하도록 구성하는 K경로탐색기법은 유입링크기반 전체경로삭제기법[6, 7]을 변형한 것이다. 전체경로삭제기법은 출발지와 도착지가 정해진 두 지점에서 K개의 경로를 구축하는 기법으로 이전 네트워크(N)에서 기 탐색된 경로를 모두 제거한 네트워크(N')를 구축하여 경로를 탐색하는 방안이다.
경로열거에서 표지확정 문제를 우회하는 방안으로 최적경로집합조건을 제시했다. 이 조건을 구축하는 K경로탐색기법으로서 유입링크기반 전체경로삭제 기법을 수정하여 제안했다.
주요개념은 탐색링크집합에서 가장 적은 비용의 링크를 선정하여 링크의 도착노드를 시작노드로 하는 링크표지를 확정한다. 이 방법을 이용해서 표지를 확정하는 과정은 기본적으로 노드표지 확정과정과 동일하다.
환승계수로 구축된 누적환승함수를 포함하여 토이네트워크에 대하여 최적조건이 성립하지 않는 상황을 검토한다. d_ab =2인 상황에 대하여 [Fig.

이론/모형

제안된 기법은 세 가지 측면- 1) 복수경로탐색의 적용, 2) 최적해의 선정, 3) 실제 교통망에의 적용 -에서 검토된다. 이를 위해 복수경로탐색을 위해서는 제안된 K경로탐색 알고리즘은 유입링크기반 전체경로삭제기법[5, 6]을 통하여 최적해의 포함을 위한 실제 교통망에서 상한(Upper Bound)에 대하여 논의한다.

후속연구

본 연구는 토이네트워크를 대상으로 결과의 타당성을 제시했으나, 대규모 현실 교통망에 대한 추가적인 검증이 필요할 것으로 판단된다. 특히 표지 확정과정에서 발생하는 다양한 문제에 대해서는 향후 구체적으로 확인하는 절차가 필요하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	환승누적함수가 포함되는 통행비용의 한계는 무엇인가?	이 함수로 통행시간이 더 소요되더라도 환승이 적은 대중교통노선을 선택하는 일반적인 상황의 구현이 가능하다. 그러나 환승누적함수가 포함되는 통행비용은 비가산성비용으로 최적경로탐색을 위해서 경로열거라는 어려운 상황을 포함한다. 본 연구는 환승누적함수를 고려하여 최적경로를 탐색하는 효과적인 방안을 제안하였다.
	누적환승함수의 역할은 무엇인가?	본 연구에서 제안하는 ‘누적환승함수’이라는 용어는 환승에 대한 ‘느낌’을 정량화하는 개념이다. 누적환승함수는 환승회수가 늘어날수록 개별 환승 자체에서 발생하는 실제비용보다 더 많이(적게) 인식되도록 한다. 간단하게는, 출발지부터 환승이 발생하는 시점까지 환승의 영향을 파라메타로 반영하는 방법이 있으며, 선형 및 비선형함수 등 다양한 형태로 적용도 가능하다.
	누적환승함수를 적용하는 방법에는 무엇이 있는가?	누적환승함수는 환승회수가 늘어날수록 개별 환승 자체에서 발생하는 실제비용보다 더 많이(적게) 인식되도록 한다. 간단하게는, 출발지부터 환승이 발생하는 시점까지 환승의 영향을 파라메타로 반영하는 방법이 있으며, 선형 및 비선형함수 등 다양한 형태로 적용도 가능하다.

참고문헌 (15)

Bellman R.(1957), "Dynamic Programming," Princeton University Press, Princeton, New Jersey.
Gabriel S. and Bernstein D.(1997), "The Traffic Equilibrium Problem with Nonadditive Path Costs," Transportation Science, vol. 20, no. 5, pp.337-348.
Yang Y., Zhang X. and Meng Q.(2004), "Modeling Private Highways in Networks with Entry-Exit Based Toll Charges," Transportation Research B, vol. 38, pp.191-213.

상세보기
Chen P. and Nie Y.(2013), "Bicriterion Shortest Path Problem with A General Nonadditive Cost," Social and Behavioral Sciences 80, pp.553-575.
Martins E. Q. V.(1984), "An Algorithm for Ranking Paths that May Contain Cycles," European Journal of Operational Research, vol. 18, pp.123-130.

상세보기
Azevedo J. A., Costa M. E. O. S., Madeira J. J. E. R. S. and Martins E. Q. V.(1993), "An Algorithm from the Ranking of Shortest Paths," European Journal of Operational Research, vol. 69, pp.97-106.

상세보기
Shin S.(2004), "Finding the First K Shortest Loopless Paths in A Transportation Network," Journal of Korean Society of Transportation, vol. 22, no. 6, pp.121-131.
Moore E. F.(1957), "The Shortest Path through A Maze," Proc. Int. Conf. on the Theory of Switching, Harvard Univ., Cambridge, MA.
Dijkstra E. W.(1959), "A Note of Two Problems in Connected with Graphs," Numer. Math. 1, pp.269-271.

상세보기
Kirby R. F. and Potts R. B.(1969), "The Minimum Route Problem for Networks with Turn Penalties and Prohibitions," Transportation Research 3, pp.397-408.

상세보기
Lee M.(2015), "Transportation Network Models and Algorithms Considering Directional Delay and Prohibitions for Intersection Movement," Ph.D. Thesis, University of Wisconsin at Madison.
Shier R. D.(1979), "On Algorithm from Finding the K Shortest Paths in A Network," Networks, vol. 9, pp.195-214.

상세보기
Yen J. Y.(1971), "Finding the K Shortest Loopless Paths in A Network," Management Science, vol. 17, pp.711-715.
Pollack M.(1961), "The Kth Best Route Through A Network," Operations Research, vol. 9, pp.578-580.

상세보기
Bellman R. and Kalaba R.(1968), "On Kth Best Policies," J. SIAM 8, pp.5832-588.

저자의 다른 논문 :

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

연합인증