KR100856902B1 - 대중교통 경로탐색 방법 - Google Patents

Abstract

본 발명은 대중교통 경로탐색 방법에 관한 것으로, 출발지와 목적지를 입력하면 상기 출발지와 목적지를 기준으로 하는 설정 탐색 반경 내에서 적어도 제1 설정 개수의 출발지 후보 링크와 목적지 후보 링크를 선정하고, 상기 선정된 출발지 후보 링크와 목적지 후보 링크를 출발지 또는 목적지까지의 거리를 기준으로 우선 순위를 결정한 후, 우선 순위에 따라 순차적으로 상기 출발지 후보 링크에서 목적지 후보 링크, 그리고 상기 목적지까지의 대중교통 경로 탐색을 수행하여 제1 대중교통 경로를 획득하여 제공한다. 이에 따라 본 발명은 사용자가 원하는 형태이면서 적어도 하나 이상의 대중교통 경로 정보를 정확하고 빠르게 제공할 수 있게 한다.

보행자, 대중교통, 경로, 지하철, 버스

Description

대중교통 경로탐색 방법{Method for searching path of masstransportation and server for providing service of masstransportation path}

도 1은 본 발명의 실시예에 따른 길안내 서비스를 제공하기 위한 네트워크 구성도이다.

도 2는 본 발명의 실시예에 따른 보행자 경로 제공서버의 블록 구성도이다.

도 3은 본 발명의 대중교통 경로탐색 방법에 대한 개략적인 순서도이다.

도 4는 본 발명의 제1 실시예에 따른 후보링크 선정 방법을 보인 순서도이다.

도 5는 본 발명의 실시예에 따른 버스경로 탐색방법을 보인 순서도이다.

도 6은 본 발명의 실시예에 따른 지하철경로 탐색방법을 보인 순서도이다.

도 7은 본 발명의 실시예에 따른 버스경로 지하철 경로간의 관계를 보인 도면이다.

도 8은 본 발명의 제1 실시예에 따른 대중교통 경로탐색 방법을 보인 순서도이다.

도 9는 도 8에 도시된 지하철 경로 탐색 방법을 도시한 순서도이다.

도 10은 본 발명의 제2 실시예에 따른 대중교통 경로탐색 방법을 보인 순서도이다.

본 발명은 길안내 서비스에 관한 것으로, 특히, 보행자를 위한 대중교통 경로탐색 방법에 관한 것이다.

일반적으로 길안내 서비스는 사용자가 출발지(또는 현재위치)와 목적지 정보를 제공하면 출발지와 목적지간의 이동 경로를 찾아 제공하는 서비스이다. 현재 길안내 서비스는 차량 운전자를 위해 차량의 이동 경로를 제공하거나, 보행자를 위해 대중교통 수단의 이동 경로를 제공하고 있다.

이 중, 보행자를 위한 길안내 서비스는 사용자가 선택한 대중교통수단를 대상으로 한 이동 경로를 제공하거나, 최적이라고 판단되는 하나의 이동 경로를 탐색하여 제공하고 있다.

그러므로, 보행자를 위한 길안내 서비스는 사용자가 원하는 다양한 경로 정보를 정확하고 빠르게 제공할 수 있는 방법이 요구된다.

본 발명은 이러한 요구에 대응하여 안출된 것으로, 동종 및 이종 대중교통 수단간의 환승 및 최적, 최단, 최소 비용 등에 의해 달라지는 다양한 이동 경로를 정확하고 빠르게 제공할 수 있도록 하는 것이다.

상기 과제를 해결하기 위한 본 발명의 제1 특징에 따르면, 동종 및 이종 대 중교통 수단의 설정 경로를 기반으로 한 대중교통 경로탐색 방법이 제공된다. 이 대중교통 경로탐색 방법은, 출발지와 목적지를 입력하는 제1 단계; 상기 출발지와 목적지를 기준으로 하는 설정 탐색 반경 내에서 적어도 제1 설정 개수의 출발지 후보 링크와 목적지 후보 링크를 선정하는 제2 단계; 상기 선정된 출발지 후보 링크와 목적지 후보 링크를 출발지 또는 목적지까지의 거리를 기준으로 우선 순위를 결정하는 제3 단계; 및 우선 순위에 따라 순차적으로 상기 출발지 후보 링크에서 목적지 후보 링크, 그리고 상기 목적지까지의 대중교통 경로 탐색을 수행하여 제1 대중교통 경로를 획득하는 제4 단계를 포함한다.

또한, 상기 과제를 달성하기 위한 본 발명의 제2 특징에 따르면, 동종 및 이종 대중교통 수단의 설정 경로를 기반으로 한 대중교통 경로탐색 방법이 제공된다. 이 대중교통 경로탐색 방법은 출발지와 목적지를 입력하는 제1 단계; 상기 출발지와 목적지를 기준으로 하는 설정 탐색 반경 내에서 적어도 제1 설정 개수의 출발지 후보 링크와 목적지 후보 링크를 선정하는 제2 단계; 상기 선정된 출발지 후보 링크와 목적지 후보 링크를 출발지 또는 목적지까지의 거리를 기준으로 우선 순위를 결정하는 제3 단계; 상기 출발지와 목적지를 기준으로 복수개의 출발지 기준 지하철 출입구 링크와 목적지 기준 지하철 출입구 링크를 선정하는 제4 단계; 우선 순위에 따라 순차적으로 상기 출발지 후보 링크에서 상기 출발지 기준 지하철 출입구 링크까지의 버스 경로를 탐색하는 제5 단계; 상기 출발지 기준 지하철 출입구 링크에서 상기 목적지 기준 지하철 출입구 링크까지의 지하철 경로를 탐색하는 제6 단계; 및 상기 목적지 기준 지하철 출입구 링크에서 상기 목적지 후보 링크, 그리고 상기 목적지까지의 대중교통 경로 탐색을 수행하여 제1 대중교통 경로를 획득하는 제7 단계를 포함한다.

아래에서는 첨부한 도면을 참고로 하여 본 발명의 실시예에 대하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.

또한 어떤 부분이 어떤 구성요소를 ”포함“한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미한다.

이제 본 발명의 실시예에 따른 대중교통 경로탐색 방법에 대하여 도면을 참고로 하여 상세하게 설명한다.

우선, 본 발명을 설명하기에 앞서 다음과 같이 각 용어를 정의한다.

- 버스 노드 : 실제 도로에서의 교차로 부분에 해당하는 네트워크 요소

- 버스 링크 : 버스 노드와 버스 노드의 연결부분인 실제 도로상의 연결 구간을 나타내는 네트워크 요소, 출발노드와 종료노드로 이루어진 네트워크 연결 구간

- 지하철 노드 : 지하철 역에 해당하는 네트워크 요소

- 지하철 링크 : 지하철 노드와 지하철 노드의 연결 부분인 실제 지하철 역 과 역 사이를 나타내는 네트워크요소,

- 지하철 출입구 링크 : 지하철 출입구와 지하철 역의 연결 부분인 네트워크 요소.

- 기본링크 : 네트워크상의 기본적인 단일 링크

- 연결링크 : 기본링크의 종료노드와 네트워크적인 연결성을 갖는 인접링크

- 출발지 후보링크 : 출발지로부터 탐색된 경로 탐색의 시작 기준이 되는 대중교통 링크

- 목적지 후보링크: 목적지로부터 탐색된 경로 탐색의 종료 기준이 되는 대중교통 링크

- 환승 링크 : 동종 또는 이종 대중교통의 노드간 연결 부분인 네트워크 요소.

도 1은 본 발명의 실시예에 따른 길안내 서비스를 제공하기 위한 네트워크 구성도이다. 도 1에 도시된 바와 같이, 본 발명의 길안내 서비스를 위한 네트워크는 사용자 단말(100)과 보행자 경로 제공서버(200)를 포함한다.

사용자 단말(100)은 사용자의 요구에 따라 보행자 경로 제공서버(200)에 접속하여 데이터 통신을 할 수 있는 모든 종류의 단말을 통칭한다. 예컨데, 사용자 단말(100)은 데이터망(예; 인터넷)에 무선 접속하는 무선단말(예; 핸드폰, PDA(Personal Digital Assistant), 노트북, PMP(Portable Multimedia Player) 등)(110)과, 데이터망에 유선 접속하는 유선단말(예: PC, 노트북 등)(120)이 있다.

보행자 경로 제공서버(200)는 데이터 망에 구축되며, 사용자 단말(100)로부 터 길안내 서비스 요청 신호를 수신하면, 버스(마을 버스 포함), 지하철 등의 대중교통 수단을 이용하여 출발지에서 목적지로 갈 수 있는 다양한 경로를 탐색하고, 적어도 하나 이상의 최적, 최단 또는 최소비용의 경로를 사용자 단말(100)에 제공한다.

이하, 도 2를 참조로 하여 상기 보행자 경로 제공서버(200)의 내부 구성을 설명한다. 도 2는 본 발명의 실시예에 따른 보행자 경로 제공서버의 블록 구성도이다.

도 2에 도시된 바와 같이, 보행자 경로 제공서버(200)는 경로 탐색부(210), 최적경로 결정부(220), 최단경로 결정부(230)와, 데이터베이스(240)를 포함한다.

경로 탐색부(210)는 사용자로부터 출발지와 목적지 정보를 수신하면, 출발지와 목적지를 기준으로 적어도 설정 개수 이상의 대중교통 후보링크를 선정하고, 출발지에 가까운 후보링크부터 먼 후보링크의 순서로 대중교통 경로 탐색을 수행하여 적어도 2 이상의 경로를 얻는다. 이때 경로 탐색부(210)는 출발지와 목적지의 지역 정보로 해당 지역의 대중교통 수단의 종류를 확인하고, 확인한 해당 교통수단에 대한 탐색을 수행한다. 또한 경로 탐색부(210)는 사용자가 원하는 형태의 경로 정보(예; 최적 경로, 최단 경로, 최소 비용 경로 등)를 제공하기 위해, 경로 탐색한 하나 이상의 경로 정보를 최적경로 결정부(220) 또는 최단경로 결정부(230)에 제공한다.

최적경로 결정부(220)는 최적경로 변수 DB(244)를 이용하여 경로 탐색부(210)에 의해 얻어진 하나 이상의 경로 중 최적 경로를 결정한다. 최적 경로는 최소 시간으로 목적지까지 도착할 수 있는 경로이다.

최단경로 결정부(230)는 최단경로 변수 DB(245)를 이용하여 경로 탐색부(210)에 의해 얻어진 하나 이상의 경로 중 최단 경로를 결정한다. 최단 경로는 출발지에서 목적지까지의 거리가 가장 최소인 경로이다.

데이터베이스(240)는 지도 DB(241), 버스 경로 DB(242), 지하철 경로 DB(243), 최적경로 변수 DB(244), 최단경로 변수 DB(245), 경로안내 DB(미도시)와, 비용 DB(미도시)를 포함한다.

지도 DB(241)는 지도 정보, POI 정보 등을 저장한다. 버스 경로 DB(242)는 버스에 관련된 정보를 저장하고 있으며, 지하철 경로 DB(243)는 지하철에 관련된 정보를 저장하고 있다.

버스 경로 DB(242)는 버스 네트워크 정보, 버스 노드 정보, 버스 정류장 정보와 버스개별정보를 포함한다. 버스 네트워크 정보는 버스 링크정보, 링크별 통행시간, 링크 방향, 링크 종류, 링크의 도로종별, 지역코드, 링크별 선형정보 등을 포함한다. 버스 노드 정보는 노드 속성, 노선코드, 노선명칭 등을 포함한다. 버스 정류장 정보는 정류장 속성(중앙차선, 종합환승주차장 등), 정류장에서 환승 가능한 버스번호/지하철 출입구 정보, 환승 거리/시간 정보 등을 포함한다. 그리고 버스개별정보는 버스번호, 기점/종점 명칭, 배차시간, 첫차/막차 시간정보 등을 포함한다.

지하철 경로 DB(243)는 지하철 네트워크 정보, 지하철 노드 정보, 지하철개별정보, 환승정보 등을 포함한다. 지하철 네트워크 정보는 노선코드, 지하철 노선 정보, 방향별 통행시간를 포함하고, 지하철 노드 정보는 노드속성(환승역, 일반역, 종착역, 출구 등), 각 지하철 정보가 저장된 데이터 위치를 포함하며, 지하철개별정보는 플랫폼 위치, 지하철 역과 각 지하철 출입구까지의 시간(또는 거리), 만남의 장소, 내리는 문의 위치, 화장실 유무의 위치, 환승주차장 유무 등의 부가 정보를 포함한다. 그리고 환승정보는 해당 역에서 환승할 수 있는 버스의 정보(정류장 위치, 정류장까지의 거리, 버스 번호 등)를 포함한다.

최적경로 변수 DB(244)는 최적 경로 탐색할 수 있는 각종 변수를 저장한다. 예컨데, 최적경로 변수 DB(244)는 기본통행속도, 교통혼잡도, 이종차종간의 환승 가중치, 동일차종간의 환승 가중치, 환승 속도, 버스우선기준, 지하철우선기준 등을 포함한다. 기본통행속도는 버스, 지하철 링크별 통행속도를 정의하여 출발지역에서 목적지역까지의 총 통행시간을 계산하는 기본 데이터로 사용된다. 교통혼잡도는 도로의 혼잡도를 정의하는 속도의 기준을 나타내며, 원활/서행/정체로 구분한다. 각 환승가중치는 환승시에 경로 탐색에 반영하는 가중치로서, 환승이 적을수록 가중치가 작고, 동종 차종간의 환승 가중치가 이종 차종간의 환승 가중치보다 작게 설정되는 것이 바람직하다. 버스/지하철 우선기준은 사용자의 요구에 대응하기 위한 것으로, 사용자가 버스를 우선으로 경로 탐색을 요구하거나, 지하철을 우선으로 경로를 탐색하는 경우에 적용된다. 버스/지하철 우선기준을 적용하는 경우에 후보링크 중 우선으로 지정된 대중교통수단에 대한 후보링크를 우선으로 하여 경로를 탐색한다.

최단경로 변수 DB(245)는 최단 경로를 탐색할 수 있는 각종 변수를 저장한 다. 예컨데 최단경로 변수 DB(245)는 링크의 거리, 환승거리, 이종/동종 차종간 환승 가중치를 포함한다.

이하, 도 3을 참조로 하여 본 발명에 따른 대중교통 경로탐색 방법에 개념을 설명한다. 도 3은 본 발명의 대중교통 경로탐색 방법에 대한 개략적인 순서도로서, 보행자 경로제공 서버(200)의 동작 순서도이다.

사용자 단말(100)로부터 출발지 정보와 목적지 정보가 입력되면(S301), 보행자 경로제공 서버(200)의 경로 탐색부(210)는 출발지 정보와 목적지 정보를 통해 서비스 가능한 대중교통 수단의 종류를 파악한다(S302). 예컨데, 국내에서 지하철은 서울, 부산, 대구, 광주, 인천 및 일부 경기 지역에서만 운행된다. 그러므로 보행자 경로제공 서버(200)는 출발지와 목적지에 대한 지역 정보 확인을 통해 경로 탐색시 서비스 제공되지 않는 불필요한 대중교통 수단에 대한 경로 탐색을 배제하여 빠른 처리가 이루어지게 한다.

이를 위해 경로 탐색부(210)는 서비스 가능한 대중교통 수단의 종류를 파악하여 지하철 운행 여부를 판단하고(S303), 지하철이 운행하지 않는 지역이면 버스와 버스간의 경로 탐색을 수행하는 모드를 설정하고(S304), 지하철이 운행하는 지역이면 버스와 버스간의 경로 탐색, 버스와 지하철간의 경로 탐색을 수행하는 복합 모드를 설정한다(S305).

경로 탐색부(210)는 S304 또는 S305를 통해 특정 모드를 설정하면, 경로 탐색의 시작지점과 최종지점을 결정하기 위해 출발지와 목적지에 대응된 후보 링크를 선정한다(S306). 이때 선정되는 출발지 후보 링크와 목적지 후보 링크 각각은 설정 된 개수 이상이 되도록 선정되며, 출발지 후보 링크는 경로 탐색의 시작지점이고, 목적지 후보 링크는 경로 탐색의 최종지점이다.

경로 탐색부(210)는 복수의 출발지 후보 링크에 대하여 경로 탐색의 우선순위를 결정하기 위하여, 출발지와 각 출발지 후보링크간의 도보 거리(또는 도보 시간)를 산출하고, 도보 거리(또는 도보 거리)가 짧은 출발지 후보 링크에 대하여 높은 우선 순위를 부여한다(S307).

출발지 후보 링크들 각각에 대하여 우선 순위가 결정되면, 경로 탐색부(210)는 우선 순위에 따라서 먼저 우선 순위가 가장 높은 출발지 후보 링크를 시작으로 경로 탐색을 수행한다(S308). S308 과정에서 경로 탐색부(210)는 모든 후보 링크에 대해 경로 탐색을 할 수 있지만, 빠른 처리를 위해 설정 개수의 경로가 탐색되면 남은 출발지 후보 링크가 있더라도 경로 탐색을 중지할 수 있다. 그리고 S308에서 하나의 후보 링크에 대한 경로 탐색은 동종 및 이종 대중교통 수단과의 환승 경로를 포함하기 때문에 적어도 하나 이상의 경로가 탐색되나, 경로 탐색부(210)는 하나의 후보 링크에 대해 복수개의 경로가 탐색되어도 가장 빨리 탐색되는 하나 또는 2개의 경로를 선택한다. 그리고 경로 탐색부(210)에 의해 탐색된 경로 중 설정 횟수 이상의 환승을 가지는 경로는 선택에서 제외된다. 이때 지하철/버스 우선순위가 적용되는 경우 출발지 후보 링크의 우선 순위가 변경되어, 경로 탐색이 이루어진다.

출발지와 목적지간에 설정 개수의 경로가 선택되면, 경로 탐색부(210)는 사용자로부터 입력된 원하는 형태의 경로 요청에 따라 출발지와 출발지 링크간의 도 보 경로와, 목적지와 목적지 링크간의 도보 경로를 선택된 경로에 더하여 최적경로 결정부(220) 또는 최단경로 결정부(230)에 제공한다(S300).

그러면, 최적경로 결정부(220) 또는 최단경로 결정부(230)는 경로 탐색부(210)로부터 제공받은 복수의 경로 중 사용자가 원하는 경로(최적, 최단 등)를 파악하여(S309), 이를 사용자 단말(100)에 제공한다(S310).

이하에서, 도 3에서 설명한 각 과정 중 요부 과정을 보다 상세히 설명하고자 한다. 우선, 도 4를 참조로 하여 상기 S306의 과정에 대한 제1 실시예 방법을 설명한다. 도 4는 본 발명의 제1 실시예에 따른 후보링크 선정 방법을 보인 순서도로서, 출발지 후보 링크를 선정하는 방법에 대한 것이다. 목적지 후보 링크 선정 방법은 출발지 후보 링크 선정 방법과 동일하므로 설명을 생략한다.

출발지가 입력되면(S401), 경로 탐색부(210)는 출발지를 기준으로 제1 탐색반경 내에 버스 링크 또는 지하철 출입구 링크가 존재하는지를 파악한다(S402). 경로 탐색부(210)는 S402 과정에서 파악된 버스 링크 또는 지하철 출입구 링크의 수가 설정 개수(예; 2개)보다 많은지를 판단한다(S403).

경로 탐색부(210)는 상기 판단(S403)에서 제1 탐색 반경 내에 2개 이상의 링크가 존재하면 이 링크들을 출발지 후보링크로 설정하여 후보링크 선정 동작을 끝내지만(S409), 제1 탐색 반경 내에 2개 미만의 링크가 존재하면 제1 탐색 반경보다 큰 제2 탐색 반경을 적용하여 버스 링크 또는 지하철 출입구 링크를 파악한다(S404).

그리고 경로 탐색부(210)는 제2 탐색 반경 내에 2개 이상의 링크가 존재하는 지를 판단하고(S405), 2개 미만의 링크가 존재하면 다시 탐색 반경을 확장하여 제3 탐색 반경 내의 버스 링크 또는 지하철 출입구 링크를 파악한다(S406).

경로 탐색부(210)는 제3 탐색 반경 내에도 2개 미만의 링크가 존재하면(S407), 최대 탐색 반경을 적용하여 최대 탐색 반경내의 버스 링크 또는 지하철 출입구 링크를 파악하고(S408), S408 과정에서 파악된 링크를 출발지 후보링크로 선정한다(S409).

여기서, 후보 링크 선정을 위해 탐색되는 탐색 반경의 확장 개수는 설계자에 의해 임의로 결정된다.

도 4에 설명된 바와 같이, 출발지 및 목적지 후보 링크가 선정이 되면 출발지 후보 링크에 대한 우선 순위가 부여된 후 본격적으로 경로 탐색이 수행된다. 이때 경로 탐색은 버스와 버스간 경로 탐색과, 버스와 지하철간 경로 탐색으로 나눌 수 있다.

이하에서는 도 5 내지 도 7을 참조로 하여 버스와 버스간 경로 탐색, 지하철 경로 탐색 및 버스와 지하철간 경로 탐색에 대하여 설명한다.

도 5는 본 발명의 실시예에 따른 버스경로 탐색방법을 보인 순서도이다. 도 5에서 실선은 출발지 후보 링크(L1)를 가지는 특정 번호(예; 1번 버스)의 노선이고, 동그라미로 표기된 것은 버스 노드(n1 내지 n5)이며, 노드를 잇는 실선은 버스 링크(L1 내지 L4)이다.

버스와 버스간 경로 탐색은 출발지 후보 링크 즉, 버스 링크(L1)를 시작으로 경로가 탐색되는데, 출발지 후보 링크(L1)는 적어도 1번 버스와 2번 버스의 노선이 다. 그러므로 경로 탐색부(210)는 1번 버스 또는 2번 버스 중 하나를 대상으로 경로를 탐색하는데, 도 5에서는 1번 버스에 대한 경로를 우선 탐색한다고 한다.

1번 버스에 대한 경로 탐색은 탐색 버스 링크(L1)에 연결된 다음 버스 링크(L2)를 확인하고, 버스 링크(L2)가 목적지 후보 링크인지를 확인한다. 만약 버스 링크(L2)가 목적지 후보 링크이면 탐색을 종료한 후 지금까지 탐색한 경로를 결과물로 선택한다. 그러나 버스 링크(L2)가 목적지 후보 링크가 아니면 버스 링크(L1)의 종료노드(n2)에 연결된 연결링크(L5)가 2번 버스의 노선인지 확인하고, 2번 버스의 노선이면 연결링크(L5)를 1번 버스 -> 2번 버스로의 환승 경로로 결정한다.

따라서 1번 버스에 대한 경로 탐색은 링크(L1)에서 링크(L2)로의 1번 버스에 대한 경로와 링크(L1)에서 링크(L5)로의 환승 경로로 나누고, 1번 버스에 대한 경로 탐색과 2번 버스에 대한 경로 탐색을 동시에 수행한다. 환승된 2번 버스에 대한 경로 탐색은 1번 버스의 경로 탐색과 동일하게 진행된다(도 5의 a 참조).

다음으로, 버스 링크(L2)는 1번 버스와 3번 버스의 노선이다. 경로 탐색부(210)는 버스 링크(L2)와 연결된 다음 버스 링크(L3)를 확인한다. 그리고 버스 링크(L3)가 목적지 후보 링크인지를 확인한 후 목적지 후보 링크가 아니면 버스 링크(L2)의 종료 노드에 연결된 연결링크(L6)가 3번 버스인지를 확인한다.

만약 연결링크(L6)가 3번 버스의 노선이 아니면 1번 버스에 대한 다음 버스 링크(L4)를 파악하지만, 연결링크(L6)가 3번 버스의 노선이면 연결링크(L6)를 1번 버스 -> 3번 버스로의 환승 경로로 결정한다.

따라서, 경로 탐색부(210)는 버스 경로(L3)를 탐색하는 시점에서, 1번 버스 에 대한 경로 탐색, 환승된 2번 버스에 대한 경로 탐색과, 환승된 3번 버스에 대한 경로 탐색을 수행한다(도 5의 a 참조).

경로 탐색부(210)는 1번 버스에 대한 경로 탐색을 목적지 후보 링크를 찾거나 1번 버스의 종착지에 연결된 버스 링크를 찾을 때까지 수행되고, 동시에 종료 노드로부터 환승 경로 탐색을 계속한다.

이렇게 1번 버스 및 1번 버스의 환승 버스에 대한 경로 탐색을 동시에 수행하게 되면, 결국엔 다음 버스 링크가 목적지 후보 링크인 하나 이상의 경로가 발견된다.

경로 탐색부(210)는 이렇게 발견된 경로 중 발견 시간이 빠른 적어도 설정 개수(예; 2)의 경로를 선택한다. 이때 경로 탐색부(210)는 환승 경로 중 환승 횟수가 설정치보다 많은 환승 경로는 선택에서 제외시킬 수 있다.

상기와 같이 1번 버스에 대한 경로 탐색을 수행하면 출발지 후보 링크(L1)에 포함된 2번 버스에 대한 경로 탐색을 수행하고, 다음으로 우선 순위가 낮은 다음 출발지 후보 링크에 대한 경로 탐색을 수행한다.

다음으로, 도 6을 참조로 지하철경로 탐색방법을 설명한다. 도 6은 본 발명의 실시예에 따른 지하철경로 탐색방법을 보인 순서도이다.

설명에 앞서, 지하철경로 탐색방법은 목적지 지하철 출입구 링크를 결정한 상태에서 수행된다. 예컨데, 목적지 후보 링크 선정시 지하철 출입구 링크가 선정되면 이를 목적지 지하철 출입구 링크로 결정하고, 목적지 후보 링크 선정시 지하 철 출입구 링크가 선정되지 않으면 출발지로부터 가까운 복수의 지하철 출입구 링크를 찾아 이를 목적지 지하철 출입구 링크로 결정한다.

도 6에서, 삼각형은 지하철 출입구 노드(P1 내지 P4)이고, 사각형은 지하철 역 즉, 지하철 노드이며, 지하철 노드를 연결하는 실선은 지하철 링크(L10 내지 L50)이다. 그리고 지하철 출입구 노드와 지하철 노드를 연결하는 점선은 지하철 출입구 링크(k1 내지 k4)이고, 둥근 점선에서 지하철 노드를 연결하는 점선은 다른 번호의 지하철 노선에 연결되는 환승 링크(L21)이다.

후보 링크 선정 방법에 의해 지하철 출입구 링크(k1 내지 k4)가 후보 링크로 선정된다. 그러면 경로 탐색부(210)는 각 지하철 출입구 링크의 거리(및 도보 시간)를 확인한 후, 후보 링크에 연결된 지하철 노드(n10)를 시작으로 경로 탐색을 시작한다. 이때 경로 탐색은 버스와 달리 양방향으로 이루어지는데, 도 6에서는 한 방향에 대해서만 도시하였다.

지하철 노선은 노선별로 대표 노드가 존재하므로, 경로 탐색부(210)는 노선을 기반으로 연결링크가 환승링크인 경우까지 계속 경로 탐색을 한다. 즉, 도 6에서 환승링크를 가지는 지하철 노드(n30)까지 탐색을 한다.

지하철 노드(n30)는 다른 번호의 지하철 노선이 가지는 링크(L40 및 L50)에 연결된다. 따라서 경로 탐색부(210)는 지하철 노드(n3)에서 다음 링크(L3)로 진행하는 경로 탐색, 링크(L40)로 환승되는 환승 경로 탐색, 링크(L50)로 환승되는 환승 경로 탐색을 동시에 수행한다. 그리고 경로 탐색부(210)는 이와 같은 경로 탐색동작을 반복하여 지하철 경로 탐색을 수행한다.

여기서 지하철 경로 탐색도 버스 경로 탐색과 마찬가지로, 다음 링크를 파악하면 다음 링크에 관련된 지하철 출입구 링크가 목적지 지하철 출입구 링크인지를 확인하는 과정을 수행하며, 이 과정을 통해 목적지까지의 경로가 하나 이상이 발견된다.

그리고 경로 탐색부(210)는 이렇게 발견된 경로 중 발견 시간이 빠른 적어도 설정 개수(예; 2)의 경로를 선택한다. 이때 경로 탐색부(210)는 환승 경로 중 환승 횟수가 설정치보다 많은 환승 경로는 선택에서 제외시킬 수 있다.

그 다음으로, 도 7을 참조로 하여 버스와 지하철간의 경로 환승에 대하여 설명한다. 도 7은 본 발명의 실시예에 따른 버스경로 지하철 경로간의 관계를 보인 도면이다.

도 7에 도시된 바와 같이, 버스 경로 정보에는 버스 링크(L1, L2)와 해당 버스 링크(L1, L2)에 위치한 정류장 정보, 정류장 정보에 매칭된 지하철 출입구 노드(P1 내지 P5)의 정보를 포함하고 있다. 그리고 지하철 경로 정보에는 지하철 노드(즉, 지하철 역(승강장))와, 해당 지하철 노드에 매칭된 지하철 출입구 링크(k1, k2)와 지하철 출입구 노드(P1 내지 P5)를 포함하고 있다.

그러므로, 버스 경로 탐색의 경우에 경로 탐색부(210)는 하나의 버스 링크를 탐색하면, 이 버스 링크의 종료 노드에 연결된 연결 링크(즉, 환승 경로)를 파악함과 더불어 이 버스 링크에 관련된 지하철 출입구 링크를 확인한다. 만약, 버스 링크에 관련된 지하철 출입구 링크가 있으면, 지하철 출입구 링크로의 경로를 이종 대중교통 수단의 환승 경로로 결정하고 지하철 경로 탐색으로 탐색 대상을 변경한 다.

마찬가지로, 지하철 경로 탐색의 경우에 경로 탐색부(210)는 하나의 지하철 노드를 탐색하면, 이 지하철 노드에 관련된 버스 환승 정보를 통해 환승 가능한 버스 링크를 확인하고, 확인된 버스 링크로의 경로를 이종 대중교통 수단의 환승 경로로 결정하고 버스 경로 탐색으로 탐색 대상을 변경한다.

여기서, 환승되는 지하철 역이 다수개이고, 환승되는 버스 링크가 다수개인 경우에, 경로 탐색부는 후보 링크 선정과 같이 거리를 기반으로 우선 순위를 부여한 다음에 환승 경로 탐색을 수행한다.

이제, 도 8을 참조로 하여 본 발명의 제1 실시예에 따른 대중교통 경로탐색 방법을 설명한다. 도 8은 본 발명의 제1 실시예에 따른 대중교통 경로탐색 방법을 보인 순서도로서, 복수개의 후보 링크가 선정된 이후의 과정을 도시하였다. 이때의 출발지 후보 링크 선정 방법은 도 4를 참조로 설명한 후보 링크 선정 방법을 사용하였다. 그리고 지하철 노선이 제공되는 지역에서의 경로 탐색 방법에 관한 것이다.

설정 개수 이상의 출발지 후보 링크가 선정되면, 경로 탐색부(210)는 우선 순위가 가장 높은 출발지 후보 링크를 선택하고(S801), 출발지와 후보 링크까지의 도보 경로를 파악한 후 선택한 출발지 후보 링크가 지하철 출입구 링크인지 버스 링크인지 판단한다(S802).

출발지 후보 링크가 버스 링크이면, 경로 탐색부(210)는 도 5를 참조로 설명한 버스 경로 탐색 및 도 7을 참조로 설명한 버스 ->지하철 경로 탐색을 수행한 다(S803). 반면에 출발지 후보 링크가 지하철 출입구 링크이면, 경로 탐색부(210)는 도 6을 참조로 설명한 지하철 경로 탐색을 수행한다(S804).

버스 -> 지하철 환승 경로 탐색(S803) 및 지하철 경로 탐색(S804)의 경우에, 경로 탐색부(210)는 지하철 경로 탐색에 의해 목적지 지하철 출입구 링크로의 경로를 탐색한 후, 목적지 지하철 출입구 링크에서 목적지까지 도보로 이동 가능한지를 판단한다(S805). 여기서, 단일 버스 및 버스->버스간 경로 탐색의 경우는 도 5를 참조로 한 설명과 동일하므로 설명은 생략한다.

상기 판단(S805)에서, 도보로 이동 가능하지 않으면 경로 탐색부(210)는 환승 가능한 버스 링크(환승 버스 후보 링크)를 선정하고(S806), 환승 버스 후보 링크를 목적지 지하철 출입구 링크까지의 거리에 따라 우선순위를 결정한다(S807).

그런 다음, 경로 탐색부(210)는 우선 순위가 높은 환승 버스 후보 링크를 우선으로 버스 경로를 탐색하고(S808), 이렇게 탐색된 환승 버스 경로 중 목적지 후보 링크에 도달하는 환승 버스 경로를 획득한다(S809). 경로 탐색부(210)는 획득한 환승 버스 경로에 목적지 후보 링크와 목적지간의 도보 경로를 더하여 최종적으로 출발지와 목적지간의 경로를 획득한다(S810).

경로 탐색부(210)는 하나의 출발지 후보 링크에 대해 제1 설정 개수의 경로가 획득되면, 다음 우선 순위의 출발지 후보 링크를 시작으로 경로 탐색을 시작한다.

여기서 경로 탐색부(210)는 획득한 경로가 제2 설정 개수(제1 설정 개수보다 큼)만큼 획득되었는지를 판단하고(S811), 제2 설정 개수만큼 획득되지 않았으면 계 속해서 다음 우선 순위의 출발지 후보 링크에 대한 경로 탐색을 수행한다.

반면에, 제2 설정 개수만큼의 경로를 획득하면 경로 탐색부(210)는 사용자가 원하는 형태의 경로(최적, 최단 등) 또는 사용자의 요구가 없을 시에 디폴트로 설정된 경로(최적, 최단 중 하나)를 추출하기 위해 상기 획득한 경로를 최적경로 결정부(230) 또는 최단경로 결정부(240)에 제공한다.

최적경로 결정부(230) 또는 최단경로 결정부(240)는 경로 탐색부(210)로부터 입력된 제2 설정 개수의 경로 중 최단 또는 최적에 부응하는 복수개의 경로를 추출하여 사용자 단말(100)에 제공한다(S810).

여기서, 사용자에게 제공된 복수의 경로는 우선 순위가 부여되어 있고, 사용자가 우선 순위를 확인할 수 있다.

한편, 도 8을 참조로 한 본 발명의 제1 실시예에 따른 대중교통 경로탐색 방법은 지하철 경로 탐색시(S803, S804) 도 9에 도시된 바와 같이 지하철 노선만을 대상으로 한 경로 탐색이 아닌, 각 지하철 노드마다 버스로의 환승 여부 및 버스 환승 경로를 탐색하는 동작을 수행한다.

즉, 도 9에 도시된 바와 같이 다음 지하철 링크를 탐색하고(S901), 다음 지하철 링크가 목적지 후보 링크(즉, 목적지 출입구 링크)에 연결된 지하철 링크인지를 파악한다(S902), 만약 목적지 후보 링크이면 도 8의 S810 과정으로 진행하고, 목적지 후보 링크가 버스 또는 다른 지하철 노선으로 환승 가능한지를 파악한다(S904). 그리고 환승 가능하지 않으면(S905), 계속해서 동일 지하철 노선에 대한 경로를 탐색하고, 환승이 가능하면(S905), 동일 지하철 노선에 대한 경로 탐색 및 환승 경로에 대한 탐색을 수행한다(S906).

이하에서는 도 10을 참조로 하여 본 발명의 제2 실시예에 따른 대중교통 경로탐색 방법을 설명한다. 도 10은 본 발명의 제2 실시예에 따른 대중교통 경로탐색 방법을 보인 순서도로서, 지하철 노선이 제공되는 지역에 대한 것이며, 복수개의 후보 링크가 선정된 이후의 과정을 도시하였다. 이때의 출발지 후보 링크 선정 방법은 도 4를 참조로 설명한 후보 링크 선정 방법을 사용하였다.

본 발명의 제1 실시예에 따른 방법은 출발지 후보 링크를 시작으로 다음 링크로의 진행에 따라 단일 경로 및 환승 경로를 탐색하고, 이 과정에서 자연스럽게 지하철 노선으로의 환승 경로가 탐색되는 경우에 대한 것이다.

이에 반해, 본 발명의 제2 실시예에 따른 방법은 지하철 탐색 경로를 필수로 하고, 출발지 후보 링크와 목적지 후보 링크를 지하철 노선에 연결시키는 방법이다.

설정 개수 이상의 출발지 후보 링크와 목적지 후보 링크가 선정되면, 경로 탐색부(210)는 출발지/목적지 후보 링크에 지하철 출입구 링크가 있는지를 확인한다. 만약, 출발지/목적지 후보 링크에 지하철 출입구 링크가 없으면 출발지/목적지에서 가장 가까운 복수개의 지하철 출입구 링크를 찾고, 이를 출발지/목적지 기준 지하철 출입구 링크로 선정한다.

그런 다음 경로 탐색부(210)는 순위가 가장 높은 출발지 후보 링크를 선택하고(S1001), 출발지와 출발지 후보 링크까지의 도보 경로를 파악한 후 출발지 후보 링크와 출발지 기준 지하철 출입구 링크까지의 버스 경로를 탐색하고(S1002), 버스 경로를 획득한다(S1003).

경로 탐색부(210)는 상기 S1001 내지 S1003 과정을 모든 출발지 후보 링크와 복수의 출발지 기준 출입구 링크에 대하여 수행한다(S1004).

경로 탐색부(210)는 S1004를 수행함으로써 복수개의 버스 경로가 획득하게 되면, 최적경로 결정부(220) 또는 최단경로 결정부(230)를 이용하여 상기 획득한 버스 경로에 해당 버스 경로 상에 포함된 출발지 기준 출입구 링크의 환승시간(또는 환승거리)을 반영하여, 사용자가 원하는 설정 개수의 최소 또는 최적 경로를 선택한다(S1005).

그런 다음, 경로 탐색부(210)는 출발지 기준 출입구 링크에 연결된 지하철 링크를 시작지점으로 하고 목적지 기준 출입구 링크(또는 이에 연결된 지하철 노드)를 목적지로 하는 지하철 경로 탐색을 수행한다(S1006).

다음으로, 경로 탐색부(210)는 목적지 기준 지하철 출입구 링크에서 목적지까지 도보로 이동 가능한지를 판단한다(S1007).

상기 판단(S1007)에서, 도보로 이동 가능하지 않으면 경로 탐색부(210)는 환승 가능한 버스 링크(환승 버스 후보 링크)를 선정하고, 환승 버스 후보 링크를 목적지 지하철 출입구 링크까지의 거리에 따라 우선순위를 결정한 후, 우선 순위가 높은 환승 버스 후보 링크를 우선으로 버스 경로를 탐색한다(S1008).

경로 탐색부(210)는 S1008에 의해 목적지 후보 링크에 도달하는 복수개의 환승 버스 경로를 획득하면, 다시 최적경로 결정부(220) 또는 최단경로 결정부(230)를 이용하여 상기 획득한 복수개의 환승 버스 경로 중 사용자가 원하는 설정 개수 의 최소 또는 최단 경로를 파악한다(S1009).

그리고 경로 탐색부(210)는 상기 S1009에서 파악한 경로 상의 목적지 후보 링크와 목적지까지의 도보 경로를 파악하고(S1010), 이렇게 파악한 도보 경로를 환승 버스 경로에 더하여 전체 대중교통 경로를 파악한다(S1011).

그러면, 최적경로 결정부(220) 또는 최단경로 결정부(230)는 S1011에서 얻은 전체 대중교통 경로 중 최적 또는 최단을 가장 만족하는 설정 개수의 대중교통 경로를 추출하고 이를 사용자 단말(100)에 제공한다(S1012).

한편, 전술한 본 발명의 실시예에서는 출발지 후보링크부터 경로 탐색을 시작하는 것으로 설명하였으나, 목적지 후보링크부터 경로 탐색을 시작할 수 있다.

이상에서 설명한 본 발명의 실시예는 장치 및 방법을 통해서만 구현이 되는 것은 아니며, 본 발명의 실시예의 구성에 대응하는 기능을 실현하는 프로그램 또는 그 프로그램이 기록된 기록 매체를 통해 구현될 수도 있으며, 이러한 구현은 앞서 설명한 실시예의 기재로부터 본 발명이 속하는 기술분야의 전문가라면 쉽게 구현할 수 있는 것이다.

이상에서 본 발명의 실시예에 대하여 상세하게 설명하였지만 본 발명의 권리범위는 이에 한정되는 것은 아니고 다음의 청구범위에서 정의하고 있는 본 발명의 기본 개념을 이용한 당업자의 여러 변형 및 개량 형태 또한 본 발명의 권리범위에 속하는 것이다.

이상에서와 같이, 이 발명의 실시예에 따르면, 사용자가 원하는 형태이면서 적어도 하나 이상의 대중교통 경로 정보를 정확하고 빠르게 제공할 수 있다.

Claims (17)

1. 동종 및 이종 대중교통 수단의 설정 경로를 기반으로 한 대중교통 경로탐색 방법에 있어서,

   출발지와 목적지를 입력하는 제1 단계;

   상기 출발지의 지역과 상기 목적지의 지역에서 제공되는 대중 교통 수단의 종류를 파악하는 제2 단계;

   상기 파악한 각 종류별 대중 교통 수단을 대상으로 상기 출발지와 상기 목적지를 기준으로 하는 적어도 하나의 설정 탐색 반경 내에서 적어도 제1 설정 개수의 출발지 후보 링크와 목적지 후보 링크를 선정하는 제3 단계;

   상기 선정된 출발지 후보 링크와 목적지 후보 링크를 출발지 또는 목적지까지의 거리를 기준으로 우선 순위를 결정하는 제4 단계; 및

   우선 순위에 따라 순차적으로 상기 출발지 후보 링크에서 상기 목적지 후보 링크, 그리고 상기 목적지까지의 대중교통 경로탐색을 수행하여 제1 대중교통 경로를 획득하는 제5 단계를 포함하되,

   상기 대중교통 경로탐색은 상기 제2 단계에서 파악한 대중 교통 수단의 종류가 2가지 이상인 경우에 이종 대중 교통 수단으로의 환승 경로 탐색 및 환승한 이종 대중교통 수단에 대한 경로 탐색을 포함하는,

   대중교통 경로탐색 방법.
2. 제1항에 있어서,

   상기 제3 단계는 상기 출발지 후보 링크와 상기 목적지 후보 링크를 선정시에 상기 설정 탐색 반경을 최소 탐색 반경으로 하여 탐색을 시작하되, 상기 최소 탐색 반경 내에 탐색된 링크의 수가 상기 제1 설정 개수보다 작은 해당 후보 링크가 있으면 해당 후보 링크의 수가 적어도 상기 제1 설정 개수만큼 될 때까지 상기 설정 탐색 반경을 확장하여 후보 링크를 탐색하는 대중교통 경로탐색 방법.
3. 제1항 또는 제2항에 있어서,

   상기 제5 단계에서 하나 이상의 대중 교통수단이 존재하는 경우에 상기 대중교통 경로탐색은 탐색중인 제1 링크에 매칭된 동종 또는 이종 대중교통수단으로의 환승 정보가 있는지를 파악하고, 환승 정보가 있으면 상기 제1 링크에 매칭된 환승 경로를 추가하여 탐색을 수행하는 대중교통 경로탐색 방법.
4. 제3항에 있어서,

   상기 대중교통 경로탐색은 경로 탐색시 환승 횟수가 설정치 이상이면 경로 탐색을 중지하는 대중교통 경로탐색 방법.
5. 제4항에 있어서,

   상기 제5 단계는 설정 개수의 상기 제1 대중교통 경로를 획득하면 경로탐색을 수행하지 않는 상기 출발지 후보 링크가 있더라도 상기 제1 대중교통 경로탐색을 중지하는 대중교통 경로탐색 방법.
6. 제4항에 있어서,

   상기 제5 단계는,

   우선 순위가 높은 상기 출발지 후보 링크를 우선으로 하여 대중교통 경로탐색을 수행하는 대중교통 경로탐색 방법.
7. 삭제
8. 삭제
9. 동종 및 이종 대중교통 수단의 설정 경로를 기반으로 한 대중교통 경로탐색 방법에 있어서,

   출발지와 목적지를 입력하는 제1 단계;

   상기 출발지와 목적지를 기준으로 하는 설정 탐색 반경 내에서 적어도 제1 설정 개수의 출발지 후보 링크와 목적지 후보 링크를 선정하는 제2 단계;

   상기 선정된 출발지 후보 링크와 목적지 후보 링크를 출발지 또는 목적지까지의 거리를 기준으로 우선 순위를 결정하는 제3 단계;

   상기 출발지와 목적지를 기준으로 복수개의 출발지 기준 지하철 출입구 링크와 목적지 기준 지하철 출입구 링크를 선정하는 제4 단계;

   우선 순위에 따라 순차적으로 상기 출발지 후보 링크에서 상기 출발지 기준 지하철 출입구 링크까지의 버스 경로를 탐색하는 제5 단계;

   상기 출발지 기준 지하철 출입구 링크에서 상기 목적지 기준 지하철 출입구 링크까지의 지하철 경로를 탐색하는 제6 단계; 및

   상기 목적지 기준 지하철 출입구 링크에서 상기 목적지 후보 링크, 그리고 상기 목적지까지의 대중교통 경로 탐색을 수행하여 제1 대중교통 경로를 획득하는 제7 단계를 포함하는

   대중교통 경로탐색 방법.
10. 제9항에 있어서,

    상기 획득한 제1 대중교통 경로 중 제2 설정 개수의 제1 대중교통 경로를 추출하여 제공하는 제8 단계를 더 포함하는

    대중교통 경로탐색 방법.
11. 제9항 또는 제10항에 있어서,

    상기 제4 단계는,

    상기 제3 단계에서 선정한 상기 출발지 후보 링크와 상기 목적지 후보 링크에 상기 지하철 출입구 링크가 포함되어 있으면, 상기 지하철 출입구 링크를 상기 출발지 기준 지하철 출입구 링크 및 목적지 기준 지하철 출입구 링크로 선정하는

    대중교통 경로탐색 방법.
12. 제11항에 있어서,

    상기 제5 단계는,

    사용자가 요청한 최적경로 또는 최단경로에 해당하는 버스 경로를 탐색하여 설정 개수의 버스 경로를 획득하는

    대중교통 경로탐색 방법.
13. 제12항에 있어서,

    상기 제6 단계는,

    사용자가 요청한 최적경로 또는 최단경로에 해당하는 버스 경로를 탐색하여 설정 개수의 지하철 경로를 획득하는

    대중교통 경로탐색 방법.
14. 제12항에 있어서,

    상기 제5 단계는,

    상기 설정 개수의 버스 경로를 획득하면 경로 탐색을 수행하지 않는 상기 출발지 후보 링크가 있더라도 버스 경로 탐색을 중지하는

    대중교통 경로탐색 방법.
15. 제14항에 있어서,

    상기 제5 단계는,

    우선 순위가 높은 상기 출발지 후보 링크를 우선으로 하여 대중교통 경로 탐색을 수행하는

    대중교통 경로탐색 방법.
16. 삭제
17. 삭제

Images