KR102604108B1 - 주차 루트들을 생성하기 위한 방법들 및 시스템들 - Google Patents

Abstract

지리적 영역 내 도로 네트워크 상에서 운행하는 차량을 위해 주차 루트를 결정하는 방법이 개시된다. 목적지 위치의 미리 정해진 보행 시간이나 거리 내의 도로들을 나타내는 전자 지도의 세그먼트들의 서브세트를 포함하는 서브-네트워크가 결정된다. 상기 세그먼트로부터 상기 목적지 위치로의 보행 시간이나 거리를 표시하는 데이터는, 적어도 하나의 연관된 주차 공간을 구비한 도로들을 나타내는 서브-네트워크의 세그먼트들과 적어도 연관된다. 복수의 후보 주차 루트들을 식별하기 위해 원래 위치로부터의 서브-네트워크의 세그먼트들을 조사하기 위해, 연관된 비용 함수를 구비한 검색 알고리즘이 사용되며, 여기에서 주어진 주차 루트에 대한 비용은, 차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간 또는 거리에 기반한다.

Description

주차 루트들을 생성하기 위한 방법들 및 시스템들

본 발명은 전자 지도에 의해 표현되는 지리적 영역 내 운행가능한, 예를 들면, 도로, 네트워크 상에서 운행하는 차량을 위한 하나 이상의 주차 루트 (route)들을 생성하는 방법 그리고 상기 방법 모두나 일부가 구현될 수 있는 시스템, 서버 및 내비게이션 디바이스에 관한 것이다. 상기 주차 루트들은 그래서 주차 검색 동안에, 즉, 비어 있는, 보통은 거리에 있는 주차 공간에 대한 검색 동안에 휴대용 내비게이션 디바이스 (portable navigation device (PND))와 같은 전자 내비게이션 디바이스의 사용자를 안내하기 위해 사용될 수 있지만, 전적으로 그렇게만 사용되지는 않는다.

GPS (Global Positioning System) 신호 수신 및 프로세싱 기능성을 포함하는 휴대용 내비게이션 디바이스들 (PND들)은 잘 알려져 있으며, 차량-내 또는 다른 차량 내비게이션 시스템들로서 널리 사용된다.

일반적으로, 현대의 PND는 프로세서, 메모리 (휘발성 및 비휘발성, 그리고 둘 모두 중 적어도 하나), 및 상기 메모리 내에 저장된 지도 데이터를 포함한다. 상기 프로세서 및 메모리는 협응하여 실행 환경을 제공하며, 그 실행 환경에서 소프트웨어 운영 시스템이 확립될 수 있으며, 그리고 추가적으로 PND의 기능성이 제어되는 것을 가능하게 하기 위해 그리고 다양한 다른 기능들을 제공하기 위해 하나 이상의 추가적인 소프트웨어 프로그램들이 제공되는 것은 일반적이다.

보통 이런 디바이스들은 사용자가 제어 인터페이스와 상호작용하는 것을 가능하게 하는 하나 이상의 입력 인터페이스들 그리고 정보가 상기 사용자에게 중계될 수 있도록 하는 하나 이상의 출력 인터페이스를 더 포함한다. 출력 인터페이스들의 예시들은 시각적인 디스플레이 및 가청 출력을 위한 스피커를 포함한다. 입력 인터페이스들의 예시들은 디바이스 (그 디바이스의 버튼들은 디바이스 상에 반드시 있을 필요는 없지만 그 디바이스가 차량 내에 장착되어 있다면 스티어링 휠 상에 있을 수 있음)의 온/오프 작동이나 다른 특징들을 제어하기 위한 하나 이상의 물리적 버튼들, 그리고 사용자가 말하는 것을 탐지하기 위한 마이크로폰을 포함한다. 특히 바람직한 설비에서, 상기 출력 인터페이스 디스플레이는 사용자가 터치에 의해 디바이스를 작동시킬 수 있는 입력 인터페이스를 (터치 감지 오프레이에 의해 또는 다르게) 추가로 제공하기 위해 터치 감지 디스플레이로서 구성될 수 있다.

이런 유형의 디바이스들은 하나 이상의 물리적인 커넥터 인터페이스들을 또한 포함할 것이며, 그 커넥터 인터페이스들에 의해 전력, 그리고 옵션으로는 데이터 신호들이 상기 디바이스로부터 전송되고 상기 디바이스로 수신될 수 있으며, 그리고 옵션으로 하나 이상의 무선 전송기들/수신기들을 포함하여 셀룰러 원거리통신 및 다른 신호 및 데이터 네트워크들, 예를 들면, Wi-Fi, Wi-Max GSM 등을 통한 통신을 허용한다.

이런 유형의 PND 디바이스들은 GPS 안테나를 또한 포함하여, 그것에 의해 위치 데이터를 포함하는 위성-브로드캐스트 신호들이 수신되며 이어서 프로세싱되어 상기 디바이스의 현재 위치를 판별할 수 있도록 한다.

상기 PND 디바이스는 전자 자이로스코프들 및 신호들을 산출하는 가속도계들을 또한 포함할 수 있으며, 그 신호들은 프로세싱되어 현재 각도 및 선형 가속도를 판별하게 하며, 그리고 GPS 신호로부터 유도된 위치 정보와 함께 상기 디바이스의 속도 및 상대적인 변위를 판별하며 그래서 그 디바이스가 설치된 차량의 속도 및 상대적인 변위를 판별하게 한다. 전형적으로 그런 특징들 대부분은 차량-내 내비게이션 시스템들 내에 공통적으로 제공되지만, 적절하다면 PND 디바이스들 내에 또한 제공될 수 있다.

그런 PND들의 유용성은 제1 위치 (보통은 시작 위치나 현재 위치)와 제2 위치 (보통은 목적지) 사이의 루트를 결정하기 위한 자신의 능력에서 주로 분명해진다. 이런 위치들은 아주 다양한 상이한 방법들 중 어느 하나에 의해, 예를 들면, 우편번호, 도로 이름 및 집 번호, 이전에 저장된 (유명한 장소들, (경기장이나 수영장 또는 다른 관심 포인트들과 같은) 지방자치 장소들과 같은) "잘 알려진" 목적지들 및 유명하거나 최근에 방문한 목적지들에 의해 상기 디바이스의 사용자에 의해 입력될 수 있다.

보통, 상기 PND는 지도 데이터로부터의 시작 및 목적지 주소 위치들 사이의 "최선의" 또는 "최적의" 루트를 계산하기 위한 소프트웨어에 의해 가능해진다. "최선의" 또는 "최적의" 루트는 미리 정해진 기준에 기초하여 결정되며 반드시 가장 빠르거나 최단의 루트일 필요는 없다. 운전자를 안내하기 위한 루트 선택은 매우 복잡하며, 그리고 그 선택된 루트는 이력적인, 현재의 그리고/또는 예측된 트래픽 및 도로 정보를 고려할 수 있다.

추가로, 상기 디바이스는 도로 및 트래픽 상태들을 계속해서 모니터할 수 있으며, 그리고 변경된 상태들로 인해서 나머지 여정이 이루어질 루트를 제안하거나 선택할 수 있다. 다양한 기술들 (예를 들면, 모바일폰 데이터 교환, 고정된 카메라, GPS 집단 트래킹)에 기반한 실시간 트래픽 모니터링 시스템들이 트래픽 지연들을 식별하기 위해 그리고 그 정보를 통지 시스템들에게 피드 하기 위해 사용되고 있다.

이런 유형의 PND들은 보통은 차량의 대시보드나 전면창 상에 설치될 수 있지만, 차량 라디오의 온-보드 컴퓨터의 일부로서 또는 실제로 차량 그 자체의 제어 시스템의 일부로서 또한 형성될 수 있다. 상기 내비게이션 디바이스는 또한 PDA (Portable Digital Assistant), 미디어 플레이어, 모바일 전화기 등과 같은 핸드-헬드 시스템의 일부일 수 있으며, 이 경우에, 상기 핸드-헬드 시스템의 보통의 기능은 루트 계산 및 계산된 루트를 다른 내비게이션 둘 모두를 수행하기 위한 상기 디바이스 상의 소프트웨어 설치에 의해 확장된다.

루트 계획 및 내비게이션 기능은 적절한 소프트웨어를 작동시키는 테스크탑이나 모바일 컴퓨팅 자원에 의해 또한 제공될 수 있다. 예를 들면, 온라인 루트 계획 및 내비게이션 능력이 routes.tomtom.com 에서 제공되며, 이 능력은 사용자가 시작 포인트 및 목적지를 입력하는 것을 허용하며, 그것에 의해 사용자의 PC가 연결된 서버는 루트를 계산하며 (이 모습은 사용자 특정된 것일 수 있음), 지도를 생성하며, 그리고 선택된 시작 포인트로부터 선택된 목적지까지 사용자를 안내하기 위한 포괄적인 내비게이션 명령어들의 세트를 생성한다. 상기 능력은 계산된 루트의 의사 3차원 렌더링 그리고 상기 루트를 따른 사용자 운행을 시뮬레이션하며 그에 의해 상기 계산된 루트의 미리 보기를 사용자에게 제공하는 루트 미리 보기 기능을 또한 제공한다.

PND의 환경에서, 일단 어떤 루트가 계산되면, 사용자는 소망된 계산된 루트를 옵션으로는 제안된 루트들의 목록으로부터 선택하기 위해 내비게이션 디바이스와 상호작용한다. 옵션으로, 사용자는, 예를 들면, 특정 루트들, 도로들, 위치들이나 기준이 특별한 여정을 위해 회피되거나 필수적이라고 규정함으로써 루트 선택 프로세스에 개입하거나 안내할 수 있다. PND의 루트 계산 모습은 하나의 주된 기능을 형성하며, 그리고 그런 루트를 따른 내비게이션은 다른 주된 기능이다.

계산된 루트를 따른 내비게이션 동안에, 그런 PND들이 선택된 루트를 따라 그 루트의 끝까지, 즉, 소망된 목적지까지 사용자를 안내하기 위한 시각적인 그리고/또는 청각적인 명령들을 제공하는 것은 일반적이다. PND들이 내비게이션 동안에 지도 정보를 스크린 상에 디스플레이하는 것은 또한 일반적이며, 그런 정보는 스크린 상에서 정규적으로 업데이트되어, 디스플레이된 지도 정보가 상기 디바이스의 현재 위치를 나타내도록 하며, 그래서 상기 디바이스가 차량-내 내비게이션을 위해 사용되고 있다면 사용자나 사용자의 차량의 위치를 나타내도록 한다.

스크린 상에 디스플레이된 아이콘은 현재의 디바이스 위치를 나타내는 것이 보통이며, 현재 도로의 지도 정보 그리고 현재 디바이스 위치 근방의 주변 도로들 및 디스플레이되어 있는 다른 지도 특징들을 이용하여 중심에 위치한다. 추가로, 내비게이션 정보는 디스플레이될 수 있으며, 옵션으로는 디스플레이된 정보 위의, 아래의 또는 한 측면에 있는 상태 바에 디스플레이될 수 있으며, 내비게이션 정보의 예들은 사용자가 취하기 위해 필요한 현재 도로로부터의 다음의 벗어남, 특별한 유형의 벗어남을 시사하는 추가의 아이콘에 의해 아마도 표현되는 그 벗어남의 속성, 예를 들면, 좌회전 또는 우회전을 포함할 수 있다. 상기 내비게이션 기능은 사용자가 상기 루트를 따라 안내받을 수 있는 청각적 명령들의 내용, 지속시간 및 타이밍을 또한 결정한다. 알 수 있듯이, "100 m에서 왼쪽으로 회전"과 같은 단순한 명령어는 막대한 프로세싱 및 분석을 필요로 한다. 이전에 언급된 것처럼, 사용자와의 사용자 상호작용은 터치 스크린에 의해서, 또는 추가로 또는 대안으로 스티어링 컬럼 마운트 원격 제어에 의해, 음성 구동에 의해 또는 어떤 다른 적합한 방법에 의한 것일 수 있다.

상기 디바이스에 의해 제공된 추가의 중요한 기능은, 내비게이션 동안에 이전에 계산된 루트로부터 사용자가 이탈함 (우연히 또는 고의적으로 중 어느 하나); 대안의 루트가 더 편리할 것이라고 실시간 트래픽 상태가 지시하며 그리고 상기 디바이스는 그런 상태들을 자동적으로 인식하는 것이 적합하게 가능하거나, 또는 사용자가 능동적으로 상기 디바이스로 하여금 어떤 원인에 대해 루트 재계산을 수행하도록 하는 이벤트에서의 자동적인 루트 재계산이다.

상기 루트 계산 및 내비게이션 기능들이 PND들의 전반적인 유용성에 기본적이지만, 상기 디바이스를 순수하게 정보 디스플레이를 위해 또는 "자유-운전 (free-driving)"을 위해 사용하는 것이 가능하며, 이 경우 현재 디바이스 위치에 관련한 지도 정보만이 디스플레이 되며, 그리고 이 경우 어떤 루트도 계산되지 않으며 어떤 내비게이션도 상기 디바이스에 의해 수행되지 않는다. 사용자가 운행할 것을 원하는 루트를 이미 알고 있으며 내비게이션 보조를 필요로 하지 않을 때에 그런 작동 모드는 종종 이용 가능하다.

위에서 설명된 유형의 디바이스들은 사용자들이 한 위치로부터 다른 위치로 운행하는 것을 가능하게 하기 위한 믿을 수 있는 수단을 제공한다.

목적지 위치에 도착할 때에 빈 주차 공간을 찾는 것은 힘들고 시간을 소모하는 경험이라는 것이 인정될 것이다. 예컨대, 특히 혼잡한 도심 환경들에서, 운전자들은 목적지에서 주차할 곳을 찾는 것의 불확실함에 직면하며, 그리고 빈 공간을 찾기 위해 목적지 주위에서 빙빙 돌며 운전하도록 종종 강요받는다. 이것은 귀중한 시간의 손실, 더 많은 연로 낭비 및 더 많은 차량 배기 가스들의 결과를 가져온다. 실제로, 도심 트래픽의 약 30%는 주차 공간을 찾는 사람들로 인한 것으로 추정된다. 따라서, 몇몇 내비게이션 디바이스들은 차량의 현재 위치에 가까운 또는 목적지 근방에 있는 주차 공간들로의 안내를 제공하는 기능을 가진다. 예를 들면, 사용자가 주차 장소를 찾는 것을 돕기 위해서 높은 확률로 빈 주차 공간을 수확하여 도로들을 따른 루트를 제안하는 것이 알려져 있다. 이 주차 검색 모드 작동에서 사용자는 "주차 루트" (또는 "주차 공간 검색 루트")를 따라 안내받을 수 있으며, 이는 주차 공간을 찾는 확률을 증가시키며 그래서 주차 공간 검색 동안에 소비되는 시간을 줄이도록 시도한다. 주차 루트들을 생성하기 위한 다양한 알려진 접근 방식들은, 예를 들면, EP 2075539 A2, WO 2011/157296 A1 그리고 2016년 1월 Transportation Research Board의 95차 연례 미팅에 발표 및 공개를 위해 제출된 Djuric 등의 논문 "ParkAssistant: An Algorithm for Guiding a Car to a Parking Spot"에서 설명된다. 주차 루트들을 생성하기 위한 추가의 접근 방식은 Arndt 등의 논문 "Probabilistic Routing for On-Street Parking Search" (DOI: 10.4230/LIPIcs.ESA.2016.264)에서 설명된다.

그러나 본 출원인은 그런 주차 루트들을 생성함에 있어서 향상을 위한 영역이 여전히 남아 있는 것으로 믿는다.

본 발명은 상기에서 설명된 것과 같은 주차 루트들을 생성하기 위한 방법들 및 시스템들을 제공하려고 한다.

본 발명의 첫 번째 모습에 따라 지리적 영역 내에서 도로 네트워크 상으로 운행하는 차량을 위한 주차 루트를 결정하는 방법이 제공되며, 여기에서 상기 도로 네트워크 중 적어도 일부 도로들은 연관된 적어도 하나의 주차 공간을 가지며, 상기 도로 네트워크는 그 도로 네트워크의 도로들을 나타내는 복수의 세그먼트들을 포함하는 전자 지도에 의해 표현되어 있으며, 각 세그먼트는 그 세그먼트의 길이를 표시하는 길이 속성을 포함하는 연관된 하나 이상의 속성들을 가지며, 그리고 적어도 하나의 주차 공간을 가진 도로들을 나타내는 적어도 상기 세그먼트들은 그 세그먼트 상에 빈 주차 공간이 존재하는 확률을 표시하는 확률 속성을 가지며, 상기 방법은:

상기 지리적 영역 내 목적지 위치를 획득하는 단계;

상기 목적지 위치의 미리 정해진 보행 시간이나 거리 내의 도로들을 나타내는 상기 전자 지도의 세그먼트들의 서브세트를 포함하는 서브-네트워크를 결정하는 단계;

적어도 하나의 연관된 주차 공간을 가진 도로들을 나타내는 상기 서브-네트워크의 적어도 세그먼트들에 대해, 상기 세그먼트로부터의 보행 시간이나 거리를 표시하는 데이터를 상기 목적지 위치에 연관시키는 단계;

연관된 비용 함수를 구비한 검색 알고리즘을 이용하여, 복수의 후보 주차 루트들을 식별하기 위해 상기 서브-네트워크의 세그먼트들을 원래 위치로부터 조사하는 단계로, 각 후보 주차 루트는 상기 서브-네트워크의 연결된 세그먼트들의 경로를 포함하며, 상기 조사하는 것은 상기 주차 루트의 세그먼트들 각각의 길이 속성 및 확률 속성을 이용하여 상기 비용 함수에 따라 복수의 후보 주차 루트들 각각에 대한 비용을 결정하는 것을 포함하며, 주어진 주차 루트에 대한 비용은 차량이 그 주차 루트 상의 주차 공간을 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간이나 거리에 기반하는, 조사 단계; 그리고

상기 결정된 비용들에 기반하여 출력을 위한 후보 주차 루트들 중 하나 이상을 선택하는 단계를 포함한다.

그래서, 적어도 실시예들에서, 상기 방법은 목적지 위치의 미리 정해진 보행 시간이나 거리 내에 있는, 이 경우에는 도로 네트워크인 운행가능 네트워크를 나타내는 전자 지도의 세그먼트들의 서브-네트워크를 결정함으로써 진행된다. 서브-네트워크의 세그먼트들에 의해 표현된 상기 운행가능 요소들, 즉, 도로들의 적어도 일부는 주차 공간들을 가진다. 그래서 확률 속성은 상기 세그먼트에 의해 표현된 도로 (또는 그 도로의 일부) 상에 빈 주차 공간이 존재하는 확률을 나타내는 그 세그먼트들과 연관될 수 있다. 상기 목적지 위치까지의 보행 시간이나 거리를 나타내는 데이터 또는 연관된 적어도 하나의 주차 공간을 구비한 세그먼트들에 대해 적어도 또한 제공된다. 바람직하게는 세그먼트로부터 목적지 위치까지의 보행 시간이나 거리를 표시하는 데이터는 세그먼트들의 서브-네트워크를 결정하는 단계의 일부로서 계산된다. 각 세그먼트는 세그먼트에 의해 표현된 도로 (또는 그 도로의 일부)의 길이를 표시하는 길이 속성을 또한 가지며, 그리고 실시예들에서, (운행 속도와 함께 취해질 때에) 연관된 운행 시간이 결정되는 것을 가능하게 한다. 그러면 상기 서브-네트워크 내 복수의 후보 주차 루트들은 적합한 검색 알고리즘을 사용하여, (상기 서브-네트워크에 의해 표현된 도로 네트워크의 일부 내의) 원래 위치로부터 서브-네트워크의 세그먼트들을 조사함으로써 식별될 수 있으며 그리고 각 후보 주차 루트에 대한 비용은 (여러 것들 중에서도 특히) 차량이 상기 주차 루트 상에서 주차 공간을 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간이나 거리를 고려하여 결정될 수 있다. 그래서, 주차 루트에 대한 비용은 상기 주차 루트의 복수의 세그먼트들 각각에 대한 길이 속성 및 확률 속성 그리고 목적지 위치까지의 보행 시간이나 거리를 표시하는 데이터를 사용하여 일반적으로 결정될 수 있다. 그러면 상기 후보 주차 루트들은 상기 정해진 비용들 및 하나 이상의 주차 루트들에 기초하여 순위가 정해지거나 그렇지 않다면 비교될 수 있으며, 예를 들어, 일반적으로 최적의, 예컨대, 최소의 비용을 구비한 주차 경로는 출력을 위해, 예를 들면, 사용자에게로의 디스플레이를 위해 그에 따라서 선택될 수 있다.

Arndt 등의 논문 "Probabilistic Routing for On-Street Parking Search"에서 설명된 접근 방식과 대조적으로, 후보 주차 루트들에 대한 식별 및 비용 결정은 상기 지리적 영역 내 목적지 위치의 미리 정해진 보행 시간이나 거리 내에 있는 세그먼트들의 서브-네트워크로 한정된다. 이 서브-네트워크 생성 및 이용은, 적어도 몇몇의 바람직한 실시예들에서, 알고리즘 및 도메인 모델링 관점 둘 모두로부터 다양한 이점들을 제공하는 것으로 믿어진다.

본 발명은 본원에서 설명된 본 발명의 모습들이나 실시예들 중 어느 하나에 따른 방법을 수행하기 위한 시스템으로 확장된다.

본 발명의 두 번째 모습에 따라, 지리적 영역 내에서 도로 네트워크 상으로 운행하는 차량을 위한 주차 루트를 결정하는 시스템이 제공되며, 여기에서 상기 도로 네트워크 중 적어도 일부 도로들은 연관된 적어도 하나의 주차 공간을 가지며, 상기 도로 네트워크는 그 도로 네트워크의 도로들을 나타내는 복수의 세그먼트들을 포함하는 전자 지도에 의해 표현되어 있으며, 각 세그먼트는 그 세그먼트의 길이를 표시하는 길이 속성을 포함하는 연관된 하나 이상의 속성들을 가지며, 그리고 적어도 하나의 주차 공간을 가진 도로들을 나타내는 적어도 상기 세그먼트들은 그 세그먼트 상에 빈 주차 공간이 존재하는 확률을 표시하는 확률 속성을 가지며, 상기 시스템은:

상기 지리적 영역 내 목적지 위치를 획득하는 수단;

상기 목적지 위치의 미리 정해진 보행 시간이나 거리 내의 도로들을 나타내는 상기 전자 지도의 세그먼트들의 서브세트를 포함하는 서브-네트워크를 결정하는 수단;

적어도 하나의 연관된 주차 공간을 가진 도로들을 나타내는 상기 서브-네트워크의 적어도 세그먼트들에 대해, 상기 세그먼트로부터의 보행 시간이나 거리를 표시하는 데이터를 상기 목적지 위치에 연관시키는 수단;

연관된 비용 함수를 구비한 검색 알고리즘을 이용하여, 복수의 후보 주차 루트들을 식별하기 위해 상기 서브-네트워크의 세그먼트들을 원래 위치로부터 조사하는 수단으로, 각 후보 주차 루트는 상기 서브-네트워크의 연결된 세그먼트들의 경로를 포함하며, 상기 조사하는 것은 상기 주차 루트의 세그먼트들 각각의 길이 속성 및 확률 속성을 이용하여 상기 비용 함수에 따라 복수의 후보 주차 루트들 각각에 대한 비용을 결정하는 것을 포함하며, 주어진 주차 루트에 대한 비용은 차량이 그 주차 루트 상의 주차 공간을 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간이나 거리에 기반하는, 조사 수단; 그리고

상기 결정된 비용들에 기반하여 출력을 위한 후보 주차 루트들 중 하나 이상을 선택하는 수단을 포함한다.

본 발명이 속한 기술 분야에서의 통상의 지식을 가진 자들에 의해 인정되듯이, 본 발명의 이 추가의 모습은 본 발명의 다른 모습들 중 어느 하나에 관하여 본원에서 설명된 본 발명의 바람직한 그리고 옵션의 특징들 중 어느 하나 또는 그 이상 또는 모두를 적절하게 포함할 수 있으며 바람직하게 포함한다. 명시적으로 선언되지 않는다면, 본원에서 본 발명의 상기 시스템은 자신의 모습들이나 실시예들 중 어느 하나에서 본 발명의 상기 방법에 관련하여 설명된 임의 단계를 수행하기 위한 수단을 포함할 수 있으며, 그 반대로 마찬가지이다.

본 발명이 속한 기술 분야에서의 통상의 지식을 가진 자들에 의해 인정되듯이, 본 발명의 이 추가의 모습들은 본 발명의 다른 모습들 중 어느 하나에 관하여 본원에서 설명된 본 발명의 바람직한 그리고 옵션의 특징들 중 어느 하나 또는 그 이상 또는 모두를 적절하게 포함할 수 있으며 바람직하게 포함한다

본 발명은 컴퓨터로 구현된 발명이며, 그리고 본 발명의 실시예들이나 모습들 중 어느 하나에 관련하여 설명된 단계들 중 어느 것도 하나 이상의 프로세서들의 세트의 제어 하에 수행될 수 있다. 상기 시스템에 관련하여 설명된 상기 단계들 중 어느 하나를 수행하기 위한 수단은 하나 이상의 프로세서들 및/또는 프로세싱 회로의 세트일 수 있다. 일반적으로, 상기 방법이나 시스템에 관련하여 설명된 상기 단계들 중 어느 것도 개별 프로세싱 회로 (스테이지들)를 사용하여, 또는 공유 프로세싱 리소스를 사용하여 수행될 수 있다.

일반적으로, 본원에서 설명된 본 발명의 다양한 기능들은 어떤 소망된 그리고 적합한 방식으로 수행될 수 있다. 예를 들면, 본원에서 설명된 본 발명의 단계들 및 기능들은 원하는대로 하드웨어나 소프트웨어에서 구현될 수 있다. 그래서, 예를 들어, 다르게 표시되지 않는다면, 본원에서 설명된 본 발명의 다양한 프로세싱 회로, 기능적인 요소들, 스테이지들, 및 "수단"은, 적절한 전용의 하드웨어 요소들 (프로세싱 회로) 및/또는 소망된 방식으로 작동하도록 프로그램될 수 있는 프로그래머블 하드웨어 요소들 (프로세싱 회로)처럼 다양한 단계들이나 기능들 등을 수행하기 위해 작동 가능한 적합한 프로세서나 프로세서들, 제어기나 제어기들, 기능적 유닛들, 회로, 프로세싱 로직, 마이크로프로세서 설비들 등을 포함할 수 있다.

실시예들 중 어느 하나에서의 본 발명의 시스템은 내비게이션 디바이스와 같은 어떤 적합한 디바이스의 모습일 수 있다. 일반적으로, 본 발명의 시스템은 적어도 하나의 프로세싱 디바이스일 수 있다. 어떤 프로세싱 디바이스 또는 상기 프로세싱 디바이스는, 휴대용 내비게이션 디바이스 (PND)이든 또는 통합된 디바이스이든지 관계없이 내비게이션 디바이스와 같은 모바일 디바이스의 디바이스일 수 있으며, 또는 서버의 디바이스일 수 있다.

본 발명의 상기 방법은 내비게이션 작동의 환경에서 바람직하게 구현된다. 그래서, 상기 방법은 필요성에 따라 루트 생성 능력 및/또는 내비게이션 기능성을 구비한 디바이스나 시스템의 하나 이상의 프로세서들의 세트에 의해 바람직하게 수행된다. 예를 들면, 상기 방법은 내비게이션 기능성을 가지지 않은 컴퓨터 시스템, 예를 들면, 데스크탑이나 랩탑 시스템에 의해 구현될 수 있을 것이다.

바람직한 실시예들에서 본 발명의 모습들이나 실시예들 중 어느 하나에서의 본 발명의 상기 방법은 내비게이션 디바이스와 같은 모바일 디바이스에 의해 수행되며, 그리고 본 발명은, 본 발명의 모습들이나 실시예들 중 어느 하나의 방법의 단계들을 수행하도록 배열된 모바일 디바이스, 예를 들면, 내비게이션 디바이스로 확장된다. 그 내비게이션 디바이스는 PND 또는 통합된, 예를 들면, 차량 내 디바이스일 수 있다.

본 발명의 모습들이나 실시예들 중 어느 하나에 따라, 상기 내비게이션 디바이스는 전자 지도를 사용자에게 디스플레이하기 위한 디스플레이, 디지털 지도 데이터에 액세스하고 전자 지도가 디스플레이를 경유하여 사용자에게 디스플레이되게 하도록 구성된 하나 이상의 프로세서들의 세트, 그리고 사용자가 상기 디바이스와 상호작용하는 것을 가능하게 하기 위해 사용자에 의해 작동 가능한 사용자 인터페이스를 포함할 수 있다. 그래서, 본 발명의 상기 시스템은 시스템, 예를 들면, 내비게이션 디바이스의 프로세싱 디바이스일 수 있다.

구현에 관계없이, 본 발명의 모습들이나 실시예들 중 어느 하나에서 본 발명에 따라 사용된 디바이스, 예를 들면, 내비게이션 장치는 프로세서, 메모리, 및 상기 메모리 내에 저장된 디지털 지도 데이터 (또는 전자 지도)를 포함할 수 있다. 상기 프로세서 및 메모리는 협응하여 실행 환경을 제공하며, 그 실행 환경에서 소프트웨어 운영 시스템이 설립될 수 있다. 하나 이상의 추가적인 소프트웨어 프로그램들이 제공되어, 상기 장치의 기능이 제어되는 것을 가능하게 하며, 그리고 다양한 다른 기능들을 제공한다. 본 발명의 내비게이션 장치는 바람직하게는 글로벌 내비게이션 위성 시스템 (GNSS), 예를 들면, GPS 또는 GLONASS 신호 수신 및 프로세싱 기능성을 포함할 수 있다. 상기 내비게이션 장치는 필요에 따라서 자신의 위치를 판별하기 위한 다른 수단, 예를 들면, 지상 비컨, 모바일 원거리통신 네트워크 등을 사용할 수 있다는 것이 인정될 것이다. 상기 장치는 하나 이상의 출력 인터페이스들을 포함할 수 있으며, 그 출력 인터페이스들에 의해 정보가 사용자에게 중계될 수 있다. 상기 출력 인터페이스(들)는 시각적인 디스플레이에 추가로 청각적 출력을 위한 스피커를 포함할 수 있다. 상기 장치는 하나 이상의 물리적인 버튼들을 포함하는 입력 인터페이스들을 포함하여, 그 장치의 온/오프 동작이나 다른 특징들을 제어할 수 있다.

다른 실시예들에서, 본 발명의 모습들이나 실시예들 중 어느 하나에서의 본 발명의 방법은 서버에 의해 수행될 수 있으며, 그리고 본 발명은 본 발명의 모습들이나 실시예들 어느 하나의 방법의 단계들을 수행하도록 배열된 서버로 확대된다. 본 발명의 모습들이나 실시예들 중 어느 하나의 본 발명의 시스템은, 예를 들면, 서버의 프로세싱 디바이스인 시스템일 수 있다.

물론, 본 발명의 모습들이나 실시예들 중 어느 하나의 본 발명의 방법의 단계들은 일부가 서버에 의해 그리고 일부가 내비게이션 장치에 의해 수행될 수 있다. 예를 들어, 루트 생성은, 예컨대, 내비게이션 디바이스의 요청 시에 서버에 의해 수행될 수 있으며, 그리고 사용자에게로의 출력을 위해 상기 디바이스에게 제공된다. 상기 방법의 단계들은 서버 상에서, 또는 일부는 서버 상에서 그리고 다른 것들은 내비게이션 디바이스 상에서 임의 조합으로, 또는 내비게이션 디바이스 상에서 배타적으로 수행될 수 있다. 서버 상에서 상기 단계들 중 하나 이상의 수행하는 것은 효과적일 수 있으며 내비게이션 디바이스에 부과된 계산 부담을 줄여줄 수 있다. 대안으로 하나 이상의 단계들이 내비게이션 디바이스 상에서 수행된다면, 이것은 네트워크 계산을 위해 필요한 대역폭을 줄일 수 있다. 그래서, 본 발명의 시스템은 일부는 내비게이션 디바이스나 다른 모바일 디바이스에 의해, 그리고 일부는 서버에 의해 제공될 수 있다.

가장 간단한 모습인 상기 전자 지도 (또는 때때로 알려진 것처럼 수학적인 그래프)는, 도로 교차점들을 대부분 나타내는 노드들 그리고 그 교차점들 사이의 도로들을 표현하는 그 노드들 사이의 라인들을 대표하는 데이터를 포함하는 유효한 데이터베이스이다. 더 상세산 디지털 지도들에서, 라인들은 세그먼트들로 분할될 수 있으며, 그 세그먼트들은 시작 노드 및 종료 노드에 의해 한정된다. 이 노드들은 그 노드들이 최소 세 개의 라인들이나 세그먼트들이 교차하는 도로 교차점을 나타낸다는 점에서 "실제"일 수 있으며, 또는 상기 노드들은 그 노드들이 다른 것들 중에서도 특히 도로의 특별한 확장을 위한 형상 정보 또는 도로의 몇몇 특성들, 예를 들면, 속도 제한이 변하는 상기 도로를 따른 위치를 식별하는 수단을 제공하기 위해 실제 노드에 의해 하나의 말단 또는 양 말단들에서 한정되어 있지 않은 세그먼트들을 위한 닻 (anchor)들로서 제공된다는 점에서 "인공적"일 수 있다. 실제로, 모든 현대의 디지털 지도들, 노드들 및 세그먼트들은 데이터베이스 내 데이터에 의해 다시 표현된 다양한 속성들에 의해 더 한정된다. 예를 들면, 각 노드는 자신의 실제 세계 위치, 예를 들면, 위도 및 경도를 한정하기 위해 지리적인 좌표들을 일반적으로 구비할 것이다. 노드들은 연관된 방향 조종 데이터 (manoeuvre data)를 또한 일반적으로 구비할 것이며, 그 방향 조종 데이터는 교차점에서 한 도로로부터 다른 도로로 운행하는 것이 가능한가의 여부를 표시한다; 상기 세그먼트들은 허용된 최대 속도, 차로 크기, 차로들의 개수, 중간에 디바이더가 존재하는가의 여부 등과 같은 연관된 속성들을 또한 구비할 것이다.

본원에서 사용된 "세그먼트"의 용어는 당 기술 분야에서의 자신의 일상적인 의미를 가진다는 것에 주목해야 한다. 전자 지도의 세그먼트는 두 포인트들이나 노드들을 연결하는 운행가능 링크이다. 본 발명의 실시에들이 도로 세그먼트들을 특별하게 참조하여 설명되지만, 본 발명은 경로, 강, 수로, 사이클 경로, 견인 경로, 철도선 등의 세그먼트들과 같은 다른 운행 가능 세그먼트들에도 또한 적용 가능할 수 있다는 것이 실감되어야 한다. 그래서, "도로 세그먼트"에 대한 참조는 "운행가능 세그먼트" 또는 그런 세그먼트들의 어떤 특정 유형이나 유형들에 대한 참조로 교체될 수 있다.

본 발명의 실시예들은 지리적인 영역 내 운행 가능 (도로) 네트워크 상에서 운행하는 차량을 위한 주차 루트를 결정하는 것에 관련된다. "주차 루트"는 일반적으로 그 주차 루트를 따라 빈 주차 공간을 찾을, 즉, 운전자가 성공적으로 주차할 수 있도록 하는 높은 확률을 가지는 것으로 판별된, 운행 가능 네트워크 전체에 걸친 루트라는 것이 이해될 것이다. 그러므로 주차 루트 또한 고려될 수 있으며, 그리고 대안으로 "주차 공간 검색 루트"로서 언급될 수 있다. 그래서 상기 주차 루트는, 목적지 위치 근방 내의 주차 공간을 찾기 위해 시도할 때에 주차 검색 동안에 사용자가 안내받을 수 있는 루트를 표시한다. 그런 주차 루트는 미리 정해진 목적지 위치로의 루트를 처음에 계획하는 것의 일부로서, 즉, 상기 루트의 끝 부분이 주차 검색을 통합하도록 생성될 수 있다. 그러나, 더 전형적으로 상기 주차 루트는 차량의 현재 위치로부터 또는 그 현재 위치에 기반하여 생성된다. 사용자 요청에 대한 응답이건 아니건간에 이것은 미리 정해진 루트의 끝을 향할 수 있으며, 또는 주차 루트 생성의 시작은 자유 운전 중의 사용자 요청에 응답한 것일 수 있다.

예를 들면, 실시예들에서, 상기 목적지 위치는 사용자가 안내받고 있는 미리 정해진 루트의 끝 포인트 또는 최후의 목적지일 수 있다. 즉, 상기 목적지 위치는 상기 운행가능 네트워크 내 미리 정해진 알려진 위치일 수 있다. 그래서, 차량 (즉, 디바이스)이 상기 미리 정해진 루트의 끝 포인에 접근하고 있을 때에, 내비게이션 안내는 보통의 루트 내비게이션 모드로부터 주차 검색 모드로 스위치할 수 있으며, 그 주차 검색 모드에서 주차 루트가 결정되어 상기 루트의 끝 포인트 근방 내에 있는 주차 공간을 찾을 가능성을 증가시키며 (최대화하며) 그리고 사용자는 그 결정된 주차 루트를 따라 유도된다. 목적지에 접근할 때에 (예를 들면, 차량 (디바이스)이 상기 목적지의 미리 정해진 임계 거리 내에 있는 것으로 판별될 때에, 이는 예를 들면 상기 목적지 그리고 그 목적지 근방 내 주차 공간들의 예상 가용성에 종속하여 세팅될 수 있음) 이 스위치는 자동적으로 발생할 수 있다. 그러나, 더 전형적으로는, 목적지 위치에 접근할 때에 사용자는 주차 검색 안내를 활성화도록 프롬프트될 것이다. 사용자가 주차 검색 안내를 활성화하면, 적합한 주차 루트가 그래서 결정되어 출력으로서 제공될 수 있다.

다른 실시예들에서, 상기 목적지 위치는 차량의 현재 위치일 수 있다. 예를 들면, 미리 정해진 루트 및 목적지가 없을 때에 (예를 들면, 자유 운전 모드에서 작동할 때에), 사용자는 운행 가능 네트워크 내 자신의 현재 위치 근방 주위에서 빈 주차 공간을 찾기 위해 적절한 주차 루트를 결정하기 위해서 어느 때에나 주차 검색 안내를 활성화하도록 선택할 수 있다.

일반적으로, 주차 루트들이 생성되는 목적지 위치는 운행 가능 네트워크 내 임의 위치일 수 있다. 예를 들면, 사용자는 소망된 목적지 위치를 선택할 수 있으며 그리고 그 목적지 위치를 위한 적절한 주차 루트들이 그에 따라서 생성될 수 있다.

상기 결정된 주차 루트는 빈 주차 공간을 찾을 가능성을 증가시키도록 (그리고/또는 빈 주차 공간을 찾기 위한 예상 시간을 줄이도록) 의도된 것이라는 것이 인정될 것이다. 예를 들면, 그리고 일반적으로, 주어진 운행 가능 네트워크 내 운행 가능 요소들 중 적어도 일부는, 예를 들면, 특히 상기 운행 가능 네트워크가 도시의 또는 시외의 지리적인 영역을 나타내는 경우, 연관된 적어도 하나의 주차 공간을 가질 것이다. 빈 주차 공간을 찾는 가능성을 증가시키기 위해서, 일반적으로 상기 주차 루트는 빈 주차 공간이 존재할 높은 가능성이 존재하는 세그먼트들을 따라 사용자를 안내해야 한다. 본원에서 사용되듯이, "주차 공간"은 (예를 들면, 주차장 내 "도로 외 (off-street)" 주차라기보다는) "노상 (on-street)" 주차를 언급하는 것으로 이해될 것이다. 즉, 본 발명은 주차 루트를 따라 노상 주차할 곳을 찾는 높은 확률을 가져오는 주차 루트들을 생성하는 것에 일반적으로 관련된다.

연관된 주차 공간을 구비한 세그먼트들은 적어도 그 요소 상에 빈 주차 공간이 존재하는, 즉, 운전자가 그 세그먼트 상에서 성공적으로 주차할 수 있는 확률을 나타내는 연관된 확률 속성을 또한 가진다 (그래서, 예컨대, 세그먼트와 연관된 어떤 주차 공간들도 존재하지 않는 경우에 그 세그먼트는 확률 0을 가질 수 있다). 그래서 상기 방법은 연관된 주차 공간을 가진 세그먼트들에 대해 적어도 주차 확률들을 획득하는 단계를 포함할 수 있다. 상기 세그먼트들에 대한 주차 확률들은 어떤 적합한 그리고 소망된 방식으로도 획득될 수 있다. 예를 들어, (서브-)네트워크의 세그먼트들에 대한 주차 확률들은 서버로부터 획득될 수 있다. 세그먼트들과 연관된 주차 확률들이 상기 전자 지도 내에 저장될 수 있다는 것이 또한 예측된다. WO 2010/081546 A1, WO 2011/157296 A1 및 PCT/EP2017/074855에서 설명된 방법들처럼, 세그먼트의 주차 확률을 결정하기 위한 다양한 적합한 방법들이 알려져 있다; 상기 출원들 모두의 내용은 본원에 참조로서 편입된다.

세그먼트는 복수의 연관된 주차 확률 속성들을 가질 수 있으며, 실시예들에서는 가진다는 것이 인정될 것이며, 예를 들면, 연관된 주차 확률 값들로, 각 값은 상이한 시간 주기에 관한 것이다. 즉, 세그먼트들에 대한 (그리고 예를 들면 아래에서 설명되는 것처럼 주차 루트의 비용을 결정하기 위해 사용되는) 확률 값들은 각 도로를 차량이 통과한 시각에 기반하여 선택될 수 있다. 상기 주차 확률 값은 문제의 도로와 연관된 이력적인 시간-종속적인 주차 프로파일로부터 취해질 수 있으며, 또는 잠재적인 라이브 (live) 확률 값이, 예를 들면, WO 2011/157296 A1에서 설명된 것처럼, 상기 이력적인 값을 대신하여 일시적으로 사용될 수 있을 것이다.

상기 전자 지도의 세그먼트들 중 반드시 모두는 아닌 적어도 일부는 연관된 다른 주차 관련 파라미터들을, 예를 들면, 이력적인 데이터에 기반한 그 세그먼트에 대한 예상된 또는 평균의 주차 검색 시간 등을 또한 구비할 수 있다. 본원에서 사용된 용어 "예상 주차 검색 시간"은 세그먼트 상에 주차하는 것을 목표로 그 세그먼트에 도착한 이후에 근방에 있는 주차 공간을 찾기 위한 예상 시간을 언급하는 것이다. 본원에서 사용된 세그먼트에 대한 "주차 확률"의 용어는 그 세그먼트 상에서 주차 공간을 찾을 가능성을 언급하는 것이다. 주차 관련 파라미터의 값, 예를 들면, 주차 확률 값 또는 예상된 추가 검색 시간 값은 각자의 세그먼트에 의해 표현된 또는 각자의 세그먼트 근방에 있는 요소 상에서의 전형적인 주차 상황들을 적절하게 반영한 측정치이다. 상기 주차 관련 파라미터, 예를 들면, 이력적인 데이터 분석에 기반하여 주차 공간을 찾기 위한 예상 시간이나 운행 가능 요소 상에서 주차 공간을 찾을 가능성의 값은 그래서 상기 파라미터의 예상 값을 대표하는 이력적인 측정치이다. 상기 주차 관련 파라미터가 주차 확률인 바람직한 실시예들에서, 주차 확률 파라미터 값이 더 높아지면 상기 세그먼트에 의해 표현된 운행 가능 요소 상에서 성공적으로 주차할 가능성이 더 커진다. 주차 확률 파라미터 값이 더 낮을수록 상기 세그먼트에 의해 표현된 운행 가능 요소 상에서 성공적으로 주차할 가능성이 더 커지도록 상기 주차 확률 파라미터 값이 한정될 수 있다는 것이 인정될 것이다.

몇몇 실시예들에서, 그리고 아래에서 더 상세하게 설명될 것처럼, 예를 들면, 주차 검색 안내 모드 동안에 이 주차 관련 파라미터들은 시각화되어 주차 루트와 함께 사용자에게 디스플레이될 수 있다.

상기 세그먼트들 각각은 상기 세그먼트에 의해 표현된 도로 (또는 그 도로의 일부)의 길이를 표시하며, 그래서 그 세그먼트에 대한 운행 시간이나 거리가 결정되는 것을 가능하게 하는 연관된 길이 속성을 추가로 구비한다. 예를 들면, 세그먼트를 따른 운행에 대한 운행 거리는 상기 세그먼트에 의해 표현된 도로 (또는 그 도로의 일부)의 길이에 일반적으로 대응할 것이다. 세그먼트에 대한 운행 시간은 그래서 일정한 운전 속도 (예를 들면, 12 km/h로, 이는 주차 검색 동안의 전형적인 순항 속도일 수 있다)를 가정함으로써 상기 세그먼트로부터 결정될 수 있다. 그러나, 세그먼트에 대한 운행 시간 결정은 그 세그먼트의 트래픽 상태들 및/또는 다른 속성들을 고려할 수 있다. 예를 들면, 그리고 특히 주차가 가능하지 않은 (그래서 상기 가정된 일정한 운전 속도는 운전자의 행동을 정확하게 반영할 수 없음) 세그먼트들 상에서, 상기 운행 시간은 그 세그먼트에 대한 미리 정해진 시간-종속 속도 프로파일을 사용하여, 예를 들면, WO 2009/053411 A1 및 WO 2017/129586 A1에서 설명된 것처럼 결정될 수 있다; 상기 출원들의 전체 내용은 본원에 참조로서 편입된다. 다른 말로 하면, 상기 서브-네트워크의 각 세그먼트는 그 세그먼트를 따른 운행에 대한 운행 (예를 들면, 운전) 시간이나 거리를 표시하는 데이터를 자신과 또한 연관시킨다.

상기 방법은, 지리적인 영역 내 목적지 위치의 미리 정해진 보행 시간이나 거리 내에 있는 전자 지도의 세그먼트들의 서브세트를 포함하는 상기 지리적인 영역의 일부 내 운행 가능 (도로) 네트워크의 서브-네트워크를 결정하는 단계를 수반한다. 바람직하게는 상기 서브-네트워크의 결정 동안에 계산된 상기 세그먼트로부터 목적지 위치까지의 보행 시간이나 거리를 표시하는 데이터는 그래서 그 서브-네트워크의 세그먼트들 중 적어도 일부와 연관된다. 보행 시간이나 거리는 상기 서브-네트워크의 세그먼트들 각각과 연관될 수 있다. 그러나, 차량이 다른 세그먼트들 상에 (합법적으로) 주차하고 목적지 위치로 걸어갈 확률이 존재하지 않기 때문에, 보행 시간이나 거리는 주차가 가능한 세그먼트들, 즉, 적어도 하나의 주차 공간을 구비한 그런 세그먼트들에 대해서만 결정될 필요가 있다는 것이 (그리고 실시예들에서는 그 세그먼트들에 대해서만 결정된다는 것이) 인정될 것이다. 그러므로 상기 방법은 적어도 하나의 연관된 주차 공간을 구비한 운행 가능 요소들을 나타내는 상기 서브-네트워크의 세그먼트들에 대해 적어도, 그 세그먼트로부터 목적지까지의 보행 시간이나 거리를 표시하는 데이터를 연관시키거나 획득하는 단계를 포함한다. 예를 들면, 적합한 일정한 보행 속도 (예를 들면, 5 km/h, 물론 이것은 사용자의 선호도에 종속하여 원하는 대로 바뀔 수 있음)를 고려함으로써 상기 거리로부터 보행 시간이 결정될 수 있다.

실시예들에서, 상기 서브-네트워크 결정은 (예를 들면, WO 2014/001565 A1 설명된 것처럼) 도달 가능 (reachability) 영역을 한정하기 위해 목적지 위치로부터의 검색, 바람직하게는 후방 (backwards) 검색을 수반할 수 있다 (상기 출원의 전체 내용은 본원에 참조로서 편입된다). 즉, 상기 서브-네트워크를 결정하는 단계는 상기 목적지 위치로부터의, 예를 들면, 후방 도달 가능 검색을 수행하는 단계를 포함할 수 있다. 그러나, 예를 들면, 각 도로 세그먼트 및 상기 목적지 위치 사이의 직선 거리에 기반한 더 단순화된 방법이 사용될 수 있을 것이라는 것이 또한 예측된다. 상기 미리 정해진 보행 시간이나 거리, 그리고 그로 인한 상기 서브-네트워크의 크기는 원하는대로, 예를 들면, 사용자의 선호도들에 종속하여 선택되거나 변경될 수 있다. 예를 들면, 비록 다른 값들이 적합하게 사용될 수 있지만, 적합한 보행 거리는 (5 km/h의 일정한 보행 속도를 가정하면 4.8 분의 보행 시간에 대응하는) 약 400 m 일 수 있다는 것이 발견되었다.

도달 가능 영역이 한정된 실시예들에서, 상기 영역은 출발 노드에 대한 도달 가능한 영역을 결정하기 위해서 목적지 위치를 나타내는 출발 노드로부터의 세그먼트들을 조사하기 위해 루트 계획 알고리즘을 사용하여 전자 지도의 세그먼트들을 (후방) 검색함으로써 바람직하게 결정되며, 상기 검색하는 것은: 상기 루트 계획 알고리즘과 연관된 비용 함수를 사용하여 각 조사된 세그먼트에 대한 제1 비용을 결정하는 단계; 그리고 목적 함수 (objective function)를 사용하여 각 조사된 세그먼트에 대한 제2 비용 함수를 결정하여 상기 루트 계획 알고리즘에 의해 도달된 각 노드가 제1의 축적된 비용 및 제2의 축적된 비용을 가지도록 하는 단계를 포함하며, 여기에서 상기 제1의 축적된 비용은 상기 출발 노드로부터 상기 노드로의 루트를 형성하는 세그먼트들에 대한 제1 비용들의 최소의 축적 (accumulation)이며, 여기에서 상기 제2의 축적된 비용은 상기 출발 노드로부터 상기 노드로의 루트를 형성하는 상기 세그먼트들에 대한 제2 비용들의 축적이며, 그리고 여기에서 상기 도달 가능 영역은 미리 정해진 제2의 축적된 비용 값에 기반하며, 그래서 노드에 대한 상기 제2의 축적된 비용이 상기 미리 정해진 제2의 축적된 비용 값을 초과할 때에 그 노드는 도달 가능하지 않은 것으로 식별되도록 한다. 상기 루트 계획 알고리즘의 비용 함수는 상기 출발 노드로의 최단 루트들이나 가장 빠른 루트들을 결정하기 위해 바람직하게 선택된다. 상기 목적 함수를 이용하여 결정된 각 조사된 세그먼트에 대한 제2 비용은 운행 거리 및 운행 거리 중 하나이며, 그래서 상기 미리 정해진 제2의 축적된 비용 값이 최대 운행 시간이나 최대 운행 거리에 각자 대응하도록 한다.

몇몇 경우에, 사용자가 차량 내에 있을 때에 주차 검색 동안에 운행 가능한 세그먼트들은 사용자가 주차하고 목적지 위치로 걷고 있을 때에 운행 가능한 세그먼트들과는 상이할 수 있다. 예를 들어, 상기 서브-네트워크가 도로 세그먼트들만을, 즉, 차량이 (그리고 잠재적으로는 사람에 의해서도) 통과할 수 있는 세그먼트들만을 포함할 것이지만, 세그먼트에 대한 더욱 정확한 보행 시간이나 거리를 제공하기 위해 상기 서브-네트워크 결정은 전자 지도의 보행자 세그먼트들, 즉, 사람만이 통과할 수 있는 세그먼트들을 또한 고려할 수 있다. 실시예에서, 예를 들면, 상기 서브-네트워크를 결정하기 위해 바람직하게 사용된 상기 (후방) 검색은 보행자 세그먼트들을 고려할 수 있다.

그래서 상기의 말단 결과는 목적지의 특정 보행 시간이나 거리 내의 운행 가능 요소들 (도로들)을 나타내는 전자 지도의 서브-네트워크를 결정하는 것이며, 상기 서브-네트워크의 적어도 일부는 적어도 하나의 주차 공간을 가진다.

상기 서브-네트워크의 세그먼트들은 복수의 가능한 (후보) 주차 루트들을 식별하기 위해서, 상기 서브-네트워크에 의해 표현된 지리적 영역의 일부 내 원래 위치로부터 적합한 검색 알고리즘을 사용하여 조사될 수 있다. 그래서 상기 방법은 상기 서브-네트워크 내 복수의 후보 주차 루트들을 식별하는 단계를 포함할 수 있다. 각 주차 루트는 상기 네트워크 내 원래 위치로부터 확장하는 서브-네트워크의 연결된 세그먼트들의 경로를 포함한다. 상기 원래 위치는, 예를 들면 상황에 종속하는, 상기 서브-네트워크 내의 어떤 적합한 세그먼트일 수 있다. 예를 들면, 상기 원래 위치는 차량의 현재 위치일 수 있으며, 통상적으로 이는 사용자가 미리 정해진 경로를 따르지 않고 주차 루트 계산을 수동으로 트리거하도록 결정하는 경우일 수 있다 (이 경우에 생성된 주차 루트가 비롯된 원래 위치 및 서브-네트워크를 한정하기 위해 사용된 현재 위치 둘 모두가 차량의 현재 위치일 수 있다는 것이 인정될 것이다). 대안으로, 몇몇 경우에, 특히 알려진 위치로의 미리 정해진 루트를 사용자가 따르는 경우, 상기 원래 위치는 상기 미리 정해진 루트를 따른 상기 서브-네트워크의 첫 번째 세그먼트일 수 있으며, 또는, 예를 들어, 사용자가 주차 루트의 계산을 수동으로 트리거하거나 트리거하기 위한 자동적인 제안을 확인한 이후에 차량이 도착한 서브-네트워크의 첫 번째 세그먼트일 수 있다. 상기 주차 루트는 상기 목적지 위치를 포함할 필요는 없으며, 그리고 종종 포함하지 않을 것이라는 것에 주목해야 한다. 즉, 상기 주차 루트는 상기 목적지 위치에서 끝나는 루트를 생성하는 것을 목표로 하는 것이 아니라 그 목적지 위치의 근방 내의 (즉, 바라는 보행 거리나 시간 내의) 주차 공간을 찾는 상대적으로 높은 가능성을 가지는 루트를 생성하는 것을 목표로 한다.

상기 서브-네트워크의 세그먼트들을 조사하기 위해 그리고 후보 주차 루트들을 식별하기 위해 필요에 따라 다양한 적합한 검색 알고리즘들이 사용될 수 있다. 실시예들에서, 분기한정 (branch-and-bound) 알고리즘과 같은 너비 우선 (breadth-first) 검색 알고리즘이 사용될 수 있으며, 여기에서 원래 위치로부터 상기 서브-네트워크를 통한 경로들의 세트 (즉, 후보 주차 루트들)가 유지되며 그리고 상기 경로들을 한 세그먼트만큼 확장하는 모든 확률들이 생성된다. 상기 경로들은 최대 길이에 도달할 때까지 이 방식으로 확장될 수 있으며, 그리고 '최선의' 기록된 경로나 경로들이 그 후에 리턴될 수 있다. 그래서, 실시예들에서, 상기 검색 알고리즘의 전반적인 실행 시간을 한정하기 위해서, 상기 방법은 세그먼트들의 최대 개수를, 상기 검색 알고리즘에 의해 식별되고 있는 후보 주차 루트들 내에 포함시키기 위해 세팅하는 단계를 포함할 수 있다. 유사하게, 상기 방법은 상기 검색 알고리즘에 의해 유지된 후보 주차 루트들의 최대 개수를 상기 서브-네트워크의 세그먼트들을 조사하는 단계 동안에 세팅하는 단계를 또한 또는 대안으로 포함할 수 있다. 세그먼트들/후보 주차 루트들의 최대 개수는 타당한 실행 시간을 제공하기 위해, 예를 들면, 관련 프로세싱 회로에 종속하여 희망하는대로 세팅될 수 있다.

몇몇 경로들 (즉, 후보 주차 루트들)에 대해, 상기 경로는 최적 경로로 확장될 수 없거나, 또는 상기 경로를 확장하는 것이 단지 무시할 수 있을 정도의 개선들만을 생기게 할 것이라는 것이 입증될 수 있다. 이 경우에, 경로가 최적 경로로 확장될 수 없다고, 또는 경로를 확정하는 것이 단지 무시할 수 있을 정도의 개선들만을 생기게 할 것이라는 것이라고 판별될 때에, 그런 경로들은 제거될 수 있으며 더 처리되지 않을 수 있다.

종종 양호한 솔루션이 상대적으로 빠르게 발견될 수 있다. 통상적으로, 실질적인 개선들이 없는 추가의 솔루션들을 찾기 위해 많은 시간이 낭비될 수 있을 것이다. 그래서, 실시예들에서, 이 경우가 탐지되어, 충분하게 높은 확률을 가진 후보 주차 루트가 식별될 때에, 예를 들면, 후보 주차 루트가 그 후보 주차 루트에 대해 주차 루트 상의 주차 공간을 차량이 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 임계를 초과하는 것으로 식별될 때에 상기 검색 알고리즘이 조기에 종결될 수 있도록 한다. 예를 들면, 상기 소망된 임계를 넘는 주차 성공 확률을 구비한 주차 루트가 발견되고 그 후에 특정 회수의 사이클들에 대해 어떤 개선도 없을 때에, 상기 검색 알고리즘은 조기에 종료될 수 있다. 대안으로, 상기 소망된 임계를 넘는 주차 성공 확률을 구비한 주차 루트가 발견될 때에, 상기 결정된 비용에 기반한 출력을 위한 하나 이상의 후보 주차 루트들이 선택될 수 있으며, 이때에 상기 서브-네트워크의 세그먼트들은 여전히 조사되고 있다.

예를 들면, 상기 후보 주차 루트들이 순위가 정해지거나 또는 그렇지 않다면 비교되는 것을 가능하게 하여 최선의 또는 최적의 후보 주차 루트(들)가 출력될 수 있도록 하기 위해서, 상기 식별된 후보 주차 루트들 각각에 대해 비용이 결정될 수 있다. 주어진 후보 주차 루트에 대한 비용은 비용 함수를 이용하여 결정된다. 상기 후보 주차 루트들에 대한 비용들을 결정하는 단계는 원칙적으로 후보 주차 루트들의 세트가 식별된 이후에 수행될 수 있다. 그러나, 더 전형적으로는, 상기 후보 주차 루트들을 식별하기 위해 사용된 검색 알고리즘은 연관된 비용 함수를 포함하여, 상기 후보 주차 루트들에 대한 비용들이 상기 서브-네트워크의 세그먼트들을 조사하는 상기 단계의 일부로서 결정될 수 있도록 한다. 예컨대, 이 방식에서, 가장 낮은 비용을 가진 최선의 후보 주차 루트들만이 유지될 필요가 있으며 다른 후보 주차 루트들은, 예를 들면, 위에서 설명된 것처럼 적합하게 제거될 수 있다.

주어진 주차 루트에 대한 비용은, 비록 배타적이지는 않지만, 아래에서 더 설명될 것처럼, 그 주차 루트 상의 주차 공간을 차량이 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간이나 거리에 기반하는 것이 일반적일 수 있다. 즉, 비용 함수는 주차 루트를 통과할 때에 주차 공간을 성공적으로 찾는 차랑의 확률을 대표하는 제1 변수 (p^s) 그리고 상기 주차 루트를 통과할 때에 빈 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 상기 주차 루트를 따른 예상 누적 운행 시간이나 거리 및 보행 시간을 대표하는 제2 변수 (t^s)를 포함하는 다변 함수인 것이 일반적이다.

어떤 루트에 대한 주차 성공 확률 (p^s)은 상기 주차 루트를 따른 세그먼트들 각각에 대한 주차 확률들을 적절하게 고려함으로써 결정될 수 있다.

유사하게, 상기 예상 누적 운행 및 보행 시간이나 거리 (t^s)는 상기 주차 루트를 따른 세그먼들 각각과 연관된 운행 시간들이나 거리들 및 보행 시간들이나 거리들을 적절하게 고려함으로써 결정될 수 있다. 그래서 상기 "예상" 누적 운행 및 보행 시간이나 거리는, 그 루트 상에서 성공적으로 주차하며 - 주차 공간을 찾기 위해 상기 루트를 따라 운행하기 위해 취해진 시간 (또는 포함된 거리)을 포함한다 - 그리고 그 후에 주차 공간으로부터 목적지 위치까지 보행하는 것과 연관된 전체 시간 (또는 거리)를 나타내는 측정치이다. 그래서 상기 예상 누적 운행 및 보행 시간 (거리)은 상기 루트를 따른 세그먼트들 각각에 대한 운행 및 보행 시간들 (거리들)의 적합하게 가중된 평균일 수 있다. 예를 들어, 어떤 세그먼트에 대한 누적 운행 및 보행 시간이나 거리는 그 세그먼트에 도달하기 위한 운행 시간이나 거리 그리고 그 후에 그 세그먼트로부터 목적지 위치에 도달하기 위한 보행 시간이나 거리를 합하여 일반적으로 결정될 수 있다.

실시예들에서, 상기 누적 운행 및 보행 시간이나 거리는, 주차하는 곳이 세그먼트 상에서 발견될 때에 그 주차하는 곳이 상기 세그먼트의 중간에서 발견되는 것으로 가정함으로써 계산된다. 이것은, 예를 들면, 주차 공간들은 세그먼트들을 따라 더 잘 또는 덜 고르게 분배된다는 가정에 기반하여 적어도 평균적으로 더욱 사실적인 비용 값을 부여할 것으로 예상될 수 있다고 알려진다. 그래서, 상기 세그먼트 길이의 반을 나타내는 추가의 항목이 세그먼트에 대한 누적 운행 및 보행 시간이나 거리를 결정하기 위해 상기 합에 포함될 수 있다. (대조적으로 Arndt 등에서 설명된 방법들에서 그런 항목은 포함되지 않는다)

그러면 주차 루트에 대한 예상 누적 운행 및 보행 시간이나 거리는 상기 주차 루트를 따른 세그먼트들 각각에 대한 누적 운행 및 보행 시간들이나 거리들의 평균으로서 결정될 수 있으며, 바람직하게는 (상기 루트를 따른 이전의 세그먼트 상에서 주차할 곳을 찾지 않으며 그리고 그 후에 그 세그먼트 상에서 주차할 곳을 찾는 것의 조합인) 각 세그먼트 상에 성공적으로 주차하는 확률로 가중치가 부여된다.

그래서, 상기 방법은 보행 시간들이나 거리들을 표시하는 데이터를 사용하는 것은 물론이며 비용 함수에 기반하여 그리고 상기 주차 루트의 복수의 세그먼트들 각각에 대한 길이 속성 및 확률 속성을 사용하여 상기 복수의 후보 주차 검색 루트들 각각에 대해 비용을 결정하는 단계를 포함할 수 있다.

본 발명의 실시예들에 따라 주차 루트들을 계산하기 위해 사용된 알고리즘들은 Arndt 등의 논문에서 설명된 것들과 대체적으로 유사할 수 있다는 것이 인정될 것이다. 예를 들어, 비용이 각 세그먼트에 대해 (즉, 상기 세그먼트의 속성들에만 기반하여) 개별적으로 결정될 수 있으며, 그래서 루트에 대한 비용이 개별 세그먼트 비용들의 단순한 합이도록 하는 경우인 많은 이전의 애플리케이션들과는 대조적으로, 실시예들에서, 루트를 형성하는 세그먼트들 각각에 대해 속성들을 사용하여 각 잠재적인 루트에 대해 (전체적으로) 비용이 결정된다

Arndt 등에서 설명된 방법들에서, 비용 함수는 후보 주차 루트에 대해 정의되며, 주차 공간을 통과할 때에 성공적으로 차량이 주차 공간을 찾는 확률이 충분하게 높은 한 (즉, 선택된 임계 위로, 그래서 p^s > 1 - ε 이도록 하며, 여기에서 ε의 값은 보통은 상대적으로 작도록 선택된다), 주차 루트를 통과할 때에 차량이 주차 공간을 성공적으로 찾는 확률에 상기 주차 루트를 따른 예상 누적 운행 시간 및 상기 주차 루트를 통과할 때에 빈 주차 공간이 발견되어야 하는 목적지 위치까지의 보행 시간을 곱한 것을 나타내는 제1 항목 (즉. p^st^s) 그리고 주차 루트를 통과할 때에 차량이 주차 공간을 성공적으로 찾지 않는 확률에 상기 주차 루트를 통과하기 위해 취해진 전체 시간 (t_n)을 곱한 것을 나타내는 제2 항목 (즉, (1-p^s)t_n)의 합으로 주어진다. 주차 루트를 통과할 때에 차량이 주차 공간을 성공적으로 찾는 확률이 충분하게 높지 않은 (즉, p^s > 1 - ε 상태가 충족되지 않음) 임의 주차 루트들에 대해, 비용 함수는 무한대로 단순하게 설정되어, 상기 후보 주차 루트가 본질적으로 무시되도록 한다.

Arndt 등에서 사용된 비용 함수는 (시간 t_n 이후에) 주차 루트의 끝에 도달했을 때에 주차가 즉시인 것으로 발견될 것이며 목적지까지 보행 시간이 0일 것이라는 가정에 대응하는 것으로 볼 수 있다. Arndt 등에서의 상기 가정은 ε의 값이 충분하게 작아서, 차량이 주차 루트 상에 성공적으로 주차할 가능성이 매우 크도록 하며, 차량이 주차 루트의 끝에 도달할 것 같지 않도록 하며, 그러므로 이 가정은 크게 중요하지 않도록 한다는 것이다. 그러나, 본 출원인은 알고리즘적인 그리고 도메인 모델링 관점들 둘 모두로부터, 이런 접근 방식에 연관된 다양한 문제들이 존재할 수 있다는 것을 인식했다. 예를 들면, Arndt 등에서 설명된 접근 방식을 사용하면, 동일한 시간 예상을 가진 그러나 상이한 주차 확률 (아래에서 임계 1 - ε)을 가진 경로는 동일한 (즉, 무한대의) 비용이 주어질 것이다. 이것은 더욱 유망한 경로들을 향하여 최적화 프로세스를 안내하는 것을 더 어렵게 만들 수 있다. 또한, 임계에 대해 (즉, ε에 대해) 보편적으로 '양호한' 값은 존재하지 않는다. 예를 들어, 보행 및 전체 시간에 대해 강제 사항들이 주어지면, 임계가 너무 높게 세팅된 경우 어떤 적합한 주차 루트들도 생성될 수 없다. 반면에, 임계가 너무 낮게 세팅되면, 비록 사용자를 위해 더 높은 주차 확률을 가지는 주차 경로가 분명하게 더 양호하더라도, 동일한 시간 예상을 구비하지만 상이한 주차 확률을 가진 주차 루트는 동일한 비용을 가질 것이다.

그래서, 실시예들에서, 개선된 모델이 사용되며, 여기에서 비용 함수는 더욱 실질적인, 실제 세계의 솔루션을 제안하기 위해 변경된다. 특히, (모든 주차 루트들에 대한) 비용 함수는, 주차 루트를 통과할 때에 차량이 주차 공간을 성공적으로 찾을 확률에 상기 주차 루트를 따른 예상 누적 운행 시간이나 거리 및 상기 주차 루트를 통과할 때에 빈 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 보행 시간이나 거리로 가중치 부여된 (비록 다른 적합한 가중치들이 잠재적으로 사용될 수 있다고 하더라도, 예를 들면, 곱해진) 것을 나타내는 제1 항목 (예를 들면, p^st^s) 그리고 주차 루트를 통과할 때에 차량이 성공적으로 주차 공간을 찾지 못하는 확률에 페널티에 의해 가중치 부여된 (예를 들면, 곱해진) 것을 나타내는 제2 항목의 합을 포함할 수 있다. 상기 페널티는 주차 루트를 통과하기 위한 전체 시간이나 거리 (예를 들면. t_n)을 포함할 수 있으며, 이는 Arndt 등에서와 유사하다. 그러나, 바람직하게는, 상기 페널티는 주차 루트의 끝으로부터 목적지 위치로 운전하기 위한 시간이나 거리 (t^e)를 추가로 포함한다. 옵션으로, 상기 페널티는 사용사의 선호에 종속하여 원하는대로 세팅될 수 있는 일정한 페널티 (t^b)를 또한 포함한다. 즉, 실시예들에서, 상기 제2 항목은 (1-p_s)(t_n + t^e + t^b)에 대체적으로 비례할 수 있다. 상기 루트의 끝으로부터 상기 목적지로 운전하기 위해 취해진 추가의 시간이나 거리를 상기 비용 결정에 (즉, 상기 비용 함수에) 포함시킴으로써, 상기 비용 값은 주차할 곳이 발견되지 않을 때인 상황의 실체를 더욱 정확하게 반영할 수 있다. 또한, 모든 주차 루트들에 대해 동일한 비용 함수가 사용될 수 있기 때문에 (즉, Arndt 등에서 사용된 것과 유사한 임계 기준이 바람직하게도 존재하지 않는다), 비용 값들은 고려되고 있는 서브-네트워크 내 모든 후보 주차 루트들에 대해 결정될 수 있다. 최적의 일정한 페널티는 대안의 계획 (예를 들면, 집으로 가거나, 도로 외 주차를 위한 지불)을 구현하는 것에 반하여 주차 루트를 따르기 위한 사용자의 오차 허용도를 반영하도록 의도된 모든 후보 주차 루트들에 대해 추가될 수 있는 "일정한" 값이다.

그래서, 실시예들에서, 주어진 주차 루트에 대해 상기 결정된 비용은 다음의 합을 포함한다: 주차 루트를 통과할 때에 차량이 주차 공간을 성공적으로 찾을 확률에 상기 주차 루트를 따른 예상 누적 운행 시간이나 거리 및 상기 주차 루트를 통과할 때에 빈 주차 공간이 발견되어야 하는 목적지 위치까지의 보행 시간이나 거리로 가중치 부여된 (예를 들면, 곱해진) 것을 나타내는 제1 항목; 그리고 상기 주차 루트의 끝까지 운행하는 것 및 주차 공간을 발견하지 못하는 것과 연관된 페널티에 상기 주차 루트 상에서 주차 공간을 찾지 못하는 확률로 가중치 부여된 (예를 들면, 곱해진) 것을 포함하는 제2 항목.

실시예들에서, 주어진 주차 루트에 대해 결정된 비용은, 주차 공간이 발견되지 않는 이벤트에서 주차 루트의 끝으로부터 목적지 위치까지 운행하는 것과 연관된 페널티에 주차 루트 상에서 주차 공간을 찾지 못하는 확률로 가중치 부여된 (예를 들면, 곱해진) 것을 (또한) 포함한다.

실시예들에서, 주어진 주차 루트에 대해 정해진 비용은 일정한 페널티에, 주차 루트 상에서 주차 공간을 찾지 못하는 확률로 가중치 부여된 것을 포함하며, 옵션으로는 상기 일정한 페널티의 값은 사용자 선호들에 기반하여 세팅되거나 선택될 수 있다.

상기 비용들/상기 비용 함수의 페널티들은 시간 또는 거리 중 어느 하나의 면에서 일반적으로 공식화될 수 있다는 것이 인정될 것이다. 그래서, 본원에서 사용된 운행이나 보행 시간 또는 시간 페널티에 대한 참조는 운행이나 보행 거리 또는 거리 페널티에도 동등하게 적용될 수 있으며, 그 반대도 마찬가지이다. 거리를 사용하는 것은 몇몇 경우에 더욱 정밀할 수 있다. 그러나, 연관된 시간의 면에서 사용자에게 비용들이 제시되는 것이 더욱 직관적일 수 있으며, 그리고 바람직하게는 상기 비용들은 시간의 면에서 공식화된다. 본원의 다른 곳에서 설명된 것처럼, 운행 또는 보행 시간은, 예를 들면, 일정한 운행 또는 보행 속도를 가정함으로써 또는 예상 속도 프로파일 등을 또한 잠재적으로 고려함으로써, 대응하는 거리로부터 일반적으로 결정될 수 있다.

상기 비용 함수는 추가의 항목들을 원한다면 포함할 수 있다는 것이 또한 인정될 것이다. 예를 들면, 실시예들에서, 주어진 주차 루트에 대해 결정된 비용은 상기 주차 루트를 따라 포함된 세그먼트들의 개수에 관련된 페널티를 포함할 수 있다. 즉, 주차 루트를 따른 세그먼트들의 개수에 비례하는 추가의 (시간 또는 거리) 페널티가 추가될 수 있다. 다른 말로 하면, 예를 들면, 시각화하기가 더 쉬울 수 있는 상대적으로 더 짧은 주차 루트들에 호의를 보이기 위해 세그먼트 당 추가의 페널티가 상기 비용 함수에 추가될 수 있다. 다른 예로서, U-턴들 또는 그렇지 않다면 바람직하지 않은 루트 특성들을 포함하는 주차 루트들을 저지하기 위해 추가의 패널티들이 포함될 수 있다. 예컨대, 주차 루트를 따른 각 U-턴에 대해 페널티가 도입될 수 있다. 또한, 상기 제1 항목 및 제2 (또는 추가의) 항목은 합산에서 적절하게 가중치가 부여될 수 있으며 그리고/또는 상기 비용 값들을 크기 조절하기 위해 다양한 변환 팩터들이 사용될 수 있다.

상기 방법은 상기 결정된 비용들에 기반하여 출력을 위해 하나 이상의 주차 루트(들)를 선택하는 단계를 더 포함한다. 예를 들면, 후보 주차 루트들은 상기 결정된 비용들을 기초로 하여 순위가 정해지거나 그렇지 않고 비교될 수 있다. 최적의 비용을 구비한 후보 주차 루트(들)는 주차 루트로서 사용자에게로의 출력을 위해 그 후에 선택될 수 있다 (그리고 사용자에게 출력된다). 본 발명의 모습들이나 실시예들 중 어느 하나에서 본 발명에 따라 생성된 주차 루트(들)는 어떤 원하는 그리고 적합한 방식으로도 출력 및/또는 사용될 수 있다. 그래서 상기 방법은 본 발명의 모습들 중 어느 하나에서 본 발명에 따라 획득되어 결정된 주차 루트(들)를 출력 및/또는 사용하는 것으로 확장된다. 예를 들면, 실시예들에서 상기 방법은 결정된 주차 루트를 표시하는 정보를 사용자에게 제공하는 단계를 더 포함한다. 이것은 상기 루트나 그 루트를 표시하는 정보를 사용자에게 출력하는 단계를 수반할 수 있다. 상기 정보는 어떤 방식으로건 상기 루트를 표시할 수 있으며, 예를 들면, 청각적인, 시각적인, 그리고/또는 촉각적일 수 있는 명령어들의 세트일 수 있지만, 바람직하게는 상기 루트의 시각적인 표현이다.

실시예들에서, 그래서 상기 방법은 상기 주차 루트를, 예를 들면, 사용자의 내비게이션 디바이스의 디스플레이 상으로 사용자에게 디스플레이하는 단계를 포함한다. 상기 루트를 디스플레이하는 단계는 상기 루트를 상기 전자 지도 상에 겹쳐놓는 단계를 포함할 수 있다. 상기 주차 루트는 어떤 적합하며 소망된 방식으로 내비게이션 안내 뷰를 제공하기 위해 상기 운행가능 네트워크 상에 디스플레이될 수 있다. 예컨대, 일반적으로 알려진 것처럼, 상기 내비게이션 안내는 2D 또는 3D 뷰의 어느 하나로 제공될 수 있다. 다른 출력 모습들이 사용될 수 있다. 예를 들면 상기 방법은 적어도 하나의 루트를 표시하는 인쇄 정보를 대안으로 또는 추가로 포함할 수 있다. 그래서, 상기 루트를 표시하는 정보는 내비게이션 디바이스를 경유하여 사용자에게 바람직하게 출력되지만, 다른 실시예들에서 상기 정보는 어떤 적합한 프로세싱 디바이스에 의해, 예를 들면, 루트 생성 능력을 구비하지만 내비게이션 능력 등을 반드시 구비하지 않은 컴퓨터 장치에 의해 디스플레이되어 출력될 수 있다. 이것은 상기 루트가 서버에 의해 생성되는 경우에 관련될 수 있다.

실시예들에서, 상기 서브-네트워크는 (2D 및 3D 안내 뷰들 모두에서) 주차 검색 안내 동안에 상기 주차 루트와 함께 또한 시각화될 수 있다. 그래서, 실시예들에서, 상기 방법은 상기 선택된 주차 루트(들)와 함께 출력하기 위해 상기 서브-네트워크를 표시하는 데이터를 제공하여, 예를 들면, 상기 서브-네트워크가 상기 주차 루트(들)와 함께 디스플레이될 수 있도록 하는 단계를 포함할 수 있다. 상기 서브-네트워크의 세그먼트들은 자신들의 현재의 주차 확률에 기반하여 그리고/또는 현재의 평균 검색 시간에 기반하여 채색되거나 그렇지 않다면 시각화될 수 있다. 예를 들면, 임계값들이 세팅될 수 있으며 세그먼트들은 상이하게 시각화될 수 있으며, 예를 들면, 그래서 상대적으로 짧은 평균 검색 시간 (또는 높은 주차 확률)을 가진 세그먼트들이 제1 방식으로 시각화되도록 하며 (예를 들면, "녹색"으로 채색된다), 반면에 상대적으로 더 긴 평균 검색 시간 (또는 낮은 주차 확률)을 가진 세그먼트들은 제2 방식으로 시각화되도록 한다 (예를 들면, "황색"이나 "적색"으로 채색된다). 이에 관해서 생각하기 위한 다른 방식은 주차 공간들 사이의 예상된 거리에 관한 것이며, 예를 들면, 주차 공간들 사이의 예상 거리가 제1 거리 미만인 경우, 상기 세그먼트들은 "녹색"으로 채색될 수 있다; 제2 거리 미만이면 "황색"으로 채색되며; 그리고 나머지는 "적색"으로 채색된다.

본 발명의 상기 방법은 따라서 내비게이션 동작의 환경에서 구현될 수 있다. 그래서, 위에서 언급된 것처럼, 상기 방법은 내비게이션 기능성을 구비한 시스템이나 디바이스에 의해 적어도 부분적으로 수행될 수 있다. 그러나, 상기 방법들은 루트 생성 능력은 구비하지만 내비게이션 기능성을 반드시 구비하지는 않는 임의의 적합한 시스템이나 디바이스에 의해 또한 수행될 수 있다는 것이 인정될 것이다. 예를 들면, 상기 방법들은 내비게이션 기능성을 가지지 않은 컴퓨터 시스템, 예를 들면, 데스크탑이나 랩탑 시스템에 의해 구현될 수 있다. 사용자에게는 생성된 루트가 제시될 수 있으며, 그 생성된 루트는 그 후에 인쇄되거나 그렇지 않고 후속의 시간에 루트 선택을 돕기 위해 사용될 수 있으며, 또는 상기 루트는 미래의 사용을 위해, 예를 들면, 내비게이션 디바이스로의 다운로드를 위해 저장될 수 있다.

몇몇 실시예들에서, 주차 루트를 생성하는 단계는 서버 상에서 수행된다. 다른 실시예들에서, 세그먼트들에 대한 주차 확률 데이터는 (서버로부터) 내비게이션 디바이스로 송신되며 그리고 상기 주차 루트들은 상기 내비게이션 디바이스에 의해 생성된다. 그래서, 위에서 설명된 것처럼, 상기 방법은 내비게이션 디바이스를 이용하여 적어도 부분적으로 수행될 수 있다. 상기 내비게이션 디바이스는 PND일 수 있으며 또는 통합된, 예를 들면, 차량 내에 통합된 디바이스일 수 있다. 상기 내비게이션 디바이스는 전자 지도를 사용자에게 디스플레이하기 위한 디스플레이, 디지털 지도 데이터에 액세스하고 전자 지도가 상기 디스플레이를 경유하여 사용자에게 디스플레이되게 하도록 구성된 하나 이상의 프로세서들의 세트, 그리고 사용자가 상기 디바이스와 상호작용 (interact)하는 것을 가능하게 하기 위해 상기 사용자에 의해 작동 가능한 사용자 인터페이스를 포함할 수 있다.

본 발명에 따른 상기 방법들 중 어느 하나는 소프트웨어, 예를 들면, 컴퓨터 프로그램들을 사용하여 적어도 부분적으로 구현될 수 있다. 그래서 본 발명은, 본 발명의 모습들이나 실시예들 중 어느 하나에 따른 방법을 수행하기 위해 또는 내비게이션 디바이스 및/또는 서버로 하여금 상기 방법들 수행하도록 하기 위해 실행 가능한 컴퓨터 판독가능 명령어들을 포함하는 컴퓨터 프로그램으로 또한 확장된다.

본 발명은 그런 소프트웨어를 포함하는 컴퓨터 소프트웨어 캐리어로 상응하여 확장되며, 그 소프트웨어는 데이터 프로세싱 수단을 포함하는 시스템이나 장치를 작동시키기 위해 사용될 때에 상기 데이터 프로세싱 수단과 함께 상기 장치나 시스템으로 하여금 본 발명의 상기 방법들의 단계들을 수행하도록 한다. 그런 컴퓨터 소프트웨어 캐리어는 ROM 칩, CD ROM 또는 디스크와 같은 비-일시적 물리적 저장 매체일 수 있으며, 또는 와이어를 통한 전자 신호, 광학 신호 또는 위성 등으로의 라디오 신호와 같은 신호일 수 있다. 본 발명은, 기계에 의해 판독될 때에 상기 기계로 하여금 본 발명의 모습들이나 실시예들 중 어느 하나의 방법에 따라 작동하도록 하는 명령어들을 담고 있는 기계 판독 가능 매체를 제공한다.

구현에 무관하게, 본 발명에 따라 사용되는 내비게이션 장치는 프로세서, 메모리, 및 상기 메모리 내에 저장된 디지털 지도 데이터를 포함할 수 있다. 상기 프로세서 및 메모리는 협응하여, 소프트웨어 운영 시스템이 확립될 수 있는 실행 환경을 제공할 수 있다. 하나 이상의 추가적인 소프트웨어 프로그램들이 제공되어 상기 장치의 기능성이 제어되는 것을 가능하게 하며, 그리고 다양한 다른 기능들을 제공할 수 있다. 본 발명의 내비게이션 장치는 내비게이션 위성, 예를 들면, GPS (Global Positioning System) 또는 GLONASS 신호 수신 및 프로세싱 기능성을 바람직하게 포함할 수 있다. 상기 장치는 하나 이상의 출력 인터페이스들을 포함할 수 있으며, 그 출력 인터페이스들에 의해 정보가 사용자에게 중계될 수 있다. 상기 출력 인터페이스(들)는 시각적인 디스플레이에 추가로 청각적인 출력을 위한 스피커를 포함할 수 있다. 상기 장치는, 상기 장치의 온/오프 동작이나 다른 기능들을 제어하기 위해 하나 이상의 물리적인 버튼들을 포함하는 입력 인터페이스들을 포함할 수 있다.

다른 실시예들에서, 상기 내비게이션 장치는 특정 내비게이션 디바이스의 일부를 형성하지 않는 프로세싱 디바이스의 애플리케이션에 의해 적어도 부분적으로 구현될 수 있다. 예를 들면 본 발명은 내비게이션 소프트웨어를 실행하도록 배열된 적합한 컴퓨터 시스템을 사용하여 구현될 수 있다. 상기 시스템은 모바일 또는 휴대용 컴퓨터 시스템, 예를 들면, 모바일 전화기 또는 랩탑일 수 있으며, 또는 데스크탑 시스템일 수 있다.

명시적으로 선언되지 않는 경우에, 본 발명의 모습들 중 어느 하나에서의 본 발명은 본 발명의 다른 모습들이나 실시예들에 관하여 설명된 특징들 중 어느 하나 또는 모두를, 그 특징들이 상호 배타적이 아닌 한은 포함할 수 있다는 것이 인정될 것이다. 특히, 동작들의 다양한 실시예들이 상기 방법에서 그리고 상기 장치에 의해 수행될 수 있는 것으로 설명되었지만, 이 동작들 중 하나 이상 또는 모두는 상기 방법에서 그리고 상기 장치에 의해 어떤 조합으로건 원하는대로 그리고 적절하게 수행될 수 있다는 것이 인정될 것이다.

주차 확률이나 주차 확률 값, 또는 주차 루트에 대한 언급들은 본원에서는 맥락 상 다르게 요청되지 않는다면 이 팩터들을 표시하는 데이터를 언급하는 것으로 이해되어야 한다는 것에 유의해야 한다. 상기 데이터는 관련 특징을 어떤 방식으로건 표시할 수 있으며, 그리고 그 관련 특징을 직접적으로 또는 간접적으로 표시할 수 있다. 그래서 주차 확률에 대한 참조는 그 주차 확률을 표시하는 데이터, 즉, 주차 확률 데이터를 참조함으로써 대체될 수 있다. 하나 이상의 세그먼트들에 관련하여 "연관된"의 문구는 데이터 저장 위치들에 관한 어떤 특별한 제한들을 필요로 하는 것으로 해석되지 않아야 한다는 것에 또한 유의해야 한다. 상기 문구는 상기 특징들이 세그먼트에 관련하여 식별 가능하게 관련되며, 예를 들면, 그래서 이 값들이 본원에서 설명된 상기 방법들에 따라 사용될 수 있도록 한다는 것만을 필요로 한다.

이 실시예들의 이점들이 지금부터 제시되며, 그리고 이 실시예들 각각의 추가의 상세 내용들 및 특징들은 동반하는 종속의 청구항들 및 다음의 상세한 설명 내 다른 곳에서 한정된다.

본 발명의 효과는 본 명세서의 해당되는 부분들에 개별적으로 명시되어 있다.

본 발명의 교시들의 다양한 모습들 및 그 교시들을 구현한 설비들은 동반 도면들을 참조하여 예시에 의해 이하에서 설명될 것이다.
도 1은 목적지를 향하여 미리 정해진 루트를 따라 운행하는 사용자에게 주차 루트 정보가 실시예들에서 어떻게 디스플레이될 수 있는가를 예시한다.
도 2는 사용자가 주차 루트를 따라 안내받고 있을 때의 디스플레이의 예를 도시한다.
도 3은 주차 검색 모드를 입력할 것을 디스플레이가 사용자에게 어떻게 프롬프트할 수 있는가를 보여준다.
도 4는 사용자가 주차 안내를 활성화한 것에 기반하여 주차 루트 정보가 실시예들에서 어떻게 디스플레이될 수 있는가를 예시한다.
도 5는 본 발명의 실시예에 따른 방법을 도시한 흐름도이다.
도 6은 주차 루트 안내 정보가 어떻게 2D 내비게이션 뷰를 사용하여 디스플레이될 수 있는가를 예시한다.
도 7은 주차 루트 안대 정보가 어떻게 3D 내비게이션 뷰를 사용하여 디스플레이될 수 있는가를 예시한다.

PND를 특별하게 참조하여 본 발명의 바람직한 실시예들이 이제 설명될 것이다. 그러나, 본 발명의 교시들은 PND들로 한정되지 않으며 루트 계획 및 내비게이션 기능을 제공하기 위해서 내비게이션 소프트웨어를 실행하도록 구성된 임의 유형의 프로세싱 디바이스에게 범용적으로 대신에 적용 가능하다는 것을 기억해야 한다. 그러므로 본원의 환경에서, 내비게이션 디바이스는 그 디바이스가 PND, 차량 내에 구축된 내비게이션 디바이스, 또는 루트 계획 및 내비게이션 소프트웨어를 실행하는 (데스크탑이나 휴대용 개인용 컴퓨터 (PC)와 같은) 컴퓨팅 자원, 모바일 전화기 또는 휴대용 디지털 보조기 (PDA)인가의 여부에 무관하게 임의 유형의 루트 계획 및 내비게이션 디바이스를 (제한없이) 포함하는 것으로 의도된 것이다.

본 발명의 실시예들은 주차 공간을 찾을 때에 운전자를 돕는데 있어서 사용하기 위한 주차 루트들을 생성하는 것에 관련된다. 예를 들면, 운전자가 특히 혼잡한 도심 영역 내 목적지로 향하여 운행하고 있을 때에, 그 운전자는 이용 가능한 노상 (on-street) 주차 공간들을 찾는 것을 시작할 수 있다. 이것은 시간을 소비하는 과정일 수 있으며 그리고 운전자가 그 목적지 주위에서 빙빙 돌게 하는 결과를 종종 가져온다. 그래서, 운전자가 주차 공간을 찾고 있을 때에, 본 발명의 실시예들에 따라, 주차 루트는 빈 주차 공간을 포함하는 높은 확률을 가지면서 생성되며, 그래서 운전자는 그 주차 루트를 따라 시도하여 주차 공간을 찾는데 소비된 시간의 양을 줄일 수 있다.

도 1은 그런 주차 루트 정보가 알려진 목적지를 향하여 미리 정해진 루트를 따라 운행하는 사용자에게 실시예들에서, 예를 들면, PND 상에서 어떻게 디스플레이될 수 있는가를 예시한다. 도 1의 왼쪽 패널에 도시된 것처럼, 사용자는 처음에 목적지 (10)를 선택하며 (여기에서는, "Tre Galli, Via Sant' Agostino, Torino"), 그러면 PND는 그 목적지 (10)로의 루트를 계산하며, 예를 들면, 중간 패널에서 보이는 것처럼 내비게이션 안내를 제공하는 것을 시작한다. 통상적으로 그러듯이, 목적지로의 루트는, 내비게이션 명령들 및 추정된 도착 시각 및 속도 정보와 같은 다른 루트 특성들, 그리고 차량의 현재 위치를 나타내는 아이콘 (11)과 함께 전자 지도의 제일 위에 디스플레이된다. 적어도 사용자가 그 목적지로부터 특정 거리 내에 있을 때에 (그리고 바람직하게는 항상), 주차 아이콘 (12)이 PND 상에 디스플레이된다. 그러면 사용자는 그 주차 아이콘 (12)을 탭하여 (또는 그렇지 않고 상호작용하여) 주차 루트를 생성하게 하며 PND로 하여금 주차 루트 안내 모드로 진입하도록 할 수 있다. 그래서, 도 1의 우측 패널에서 보이듯이, 사용자가 주차 아이콘 (12)에 탭한 것에 응답하여, 보행 시간이나 거리에 면에서 목적지의 특정 도달 가능 범위 내 도로 세그먼트들의 서브-네트워크 (14)가 생성되며 그리고 그 서브-네트워크를 통한 주차 루트 (16)가 결정되어 사용자에게 디스플레이된다. 도 1에서 보이듯이, 목적지 근방의 서브-네트워크 (14) 내 도로 세그먼트들은, 그 세그먼트들에 연관된 주차 확률 및/또는 예상되는 주차 시간의 시각적인 표시를 제공하기 위해서 적절하게 채색되거나 그렇지 않다면 적절하게 디스플레이될 수 있다. 상기 디스플레이는, 예를 들면, 노상 주차가 이용 가능하지 않는 경우에 운전자가 대안으로 찾아보기를 원할 수 있을 구역 내 도로 밖 주차 공간들 (예를 들면, 주차장들)의 개수를 또한 보여준다. 사용자는 상기 주차 루트 안내에서 나와서 통상적인 내비게이션 안내로 돌아가기 위해 어느 때에나 주차 아이콘 (12)을 다시 탭할 수 있다.

도 2는 사용자가 주차 루트 (16)를 따라 안내받고 있을 때의 디스플레이의 예를 도시한다. 운전자가 성공적으로 주차한 것이 일단 탐지되면, 주차 안내는 중단되며 그 주차 공간의 위치 (18)는 도 2의 중간 패널에 보이는 것처럼 일시적으로 저장된다. 목적지 (10)까지의 보행 루트 (20)가 도 2의 오른쪽 패널에서 보이는 것처럼 그 후에 디스플레이될 수 있다.

도 1에서, 위에서 설명된 것처럼, 주차 검색 안내는 차량이 미리 정해진 루트의 끝 부분에서 알려진 목적지에 접근하고 있을 때에 사용자 선택에 의해 활성화된다. 실시예들에서, 디스플레이는 알려진 목적지에 접근할 때에 주차 검색 모드로 진입할 것을 사용자에게 프롬프트할 수 있다. 예를 들면, 도 3에서 보이는 경우에, 예컨대, 주차 확률들 및/또는 그 목적지 근방 내의 라이브 프로브 데이터 (live probe data)를 이용하여, 사용 가능한 노상 주차가 제한되거나 제한되는 것으로 예상된다고 판별된다 (또는 알려진다). 그래서, 목적지에 접근할 때에, 디스플레이는 사용자에게 노상 주차는 그 목적지에서 제한된다고 통보하며 그리고 주차를 추가할 것을 그 사용자에게 프롬프트한다. 일단 사용자가 주차를 추가할 것을 선택하면, 예를 들면, 도 2에서 보이는 것처럼, 주차 루트가 그래서 생성되며 주차 안내가 제공될 수 있다. 그러나, 운전자가 알려진 목적지에 접근하고 있을 때에 주차 검색 안내가 자동적으로 제공될 수 있다는 것이 또한 계획된다. 다른 경우들에서 상기 주차 루트는 여정의 시작 시에 계산될 수 있다.

자유-운전 모드 동안에, 예를 들면, 어떤 알려진 목적지가 없는 경우에 주차 안내가 또한 제공될 수 있다는 것이 인정될 것이다. 예를 들어, 심지어 사용자가 목적지를 향한 미리 정해진 루트를 따라지 않고 있을 때에, 주차 안내를 제공하여 운전자가 자신의 현재 근방 내에서 주차 공간을 급하게 찾을 수 있도록 할 수 있도록 하는 것이 여전히 소망될 수 있다. 도 4는 사용자가 주차 안내를 활성화한 것에 기초하여 차량의 현재 위치 근방 내의 주차 루트 정보가 디스플레이되는 경우의 예를 보여준다. 그래서, (도 4의 오른쪽 패널에서 보이는) 주차 안내 모드로 진입하기 위해서 주차 아이콘 (12)은 디스플레이 상에 영구적으로 디스플레이되며 항상 활성화될 수 있다.

주차 안내의 다른 예들은 도 6 및 도 7에 도시된다.

본 발명의 실시예에 따른 방법이 도 5에 대체적으로 표시된다. 보이는 것처럼, 상기 방법은 목적지 위치의 미리 정해진 보행 시간이나 거리 내에 있는 전자 지도의 도로 세그먼트들의 서브-네트워크를 결정함으로써 시작한다 (단계 501). 이 도착지 위치는 다음과 같을 수 있다: (운전자가 선택하거나 시스템에 예측한) 미리 정해진 루트의 목적지; 차량의 현재 위치 (예를 들면, 어떤 루트도 존재하지 않을 때에 또는 운전자가 가능한 빨리 주차하기를 원하는 경우); 또는 운전자가 선택한 새로운 위치. (비록 더욱 단순한 방법이 각 도로 세그먼트 및 목적지 위치 사이의 직선 거리에 기초하여 사용될 수 있을 것이지만, 예를 들면, WO 2014/001565 A1에서 설명된 것처럼) 상기 서브-네트워크 결정은 도달 가능 영역을 효과적으로 한정하기 위해 목적지 위치로부터의 (예를 들면, 후방) 검색을 수반하는 것이 바람직하다. 비록 사용자가 원하는대로 쉽게 선택되거나 변경될 수 있지만, 사용자 탐색은 보행 거리가 400 m이어야 한다고 결정한다. 상기 서브-네트워크가 도로 세그먼트들만을, 즉, 차량이 통과할 수 있는 (그리고 잠재적으로는 사람도 통과할 수 있는) 세그먼트들만을 포함할 것이지만, 서브-네트워크를 결정하기 위해 바람직하게 사용되는 검색은 보행자 세그먼트들, 즉, 사람만이 통과할 수 있는 세그먼트들을 또한 고려하여, 세그먼트에 대한 더욱 정밀한 보행 시간이나 거리를 제시할 수 있다.

단계 501의 종료 결과는 상기 목적지의 특정 보행 시간이나 거리 내 도로들을 나타내는 전자 지도의 서브-네트워크이며, 여기에서 상기 도로들 중 적어도 몇몇은 적어도 하나의 주차 공간을 가지며, 그리고 상기 세그먼트들 각각은 (또는 적어도 주차가 가능한 세그먼트들은) 자신을 목적지 까지의 보행 시간에 연관시킨다 (예를 들면, 일정한 보행 속도, 예컨대, 5 km/h의 일정한 보행 속도를 가정한다). 상기 서브-네트워크의 각 세그먼트는 또한 어떤 길이를 가지며, 이는 그 세그먼트에 대한 운전 시간이 결정도록 하는 것을 가능하게 한다. 예컨대, 주차를 위해 검색할 때의 운전 시간은 예를 들면 12 km/h의 일정한 운전 속도를 가정하여 결정된다. 주차가 가능하지 않은 세그먼트들에 대해, 운전 시간은 (예를 들면, WO 2009/053411 A1 및 WO 2017/129586 A1에서 설명된 것처럼)시간-종속적 속도 프로파일을 이용하여 통상의 방식으로 바람직하게 결정된다. 다른 말로 하면, 상기 서브-네트워크의 각 세그먼트는 운전 시간을 나타내는 데이터를 자신과 또한 연관시킨다.

주차 확률 및 검색 시간을 최적화하기 위해 효과적으로 시도하는 주차 루트를 생성하기 위해서 비용 함수를 사용하여 네트워크를 조사함으로써 상기 서브-네트워크 상의 원래 위치로부터 복수의 주차 루트들이 그 후에 결정된다. 그래서, 서브-네트워크의 세그먼트들은 복수의 후보 주차 루트들을 식별하기 위해 검색 알고리즘을 사용하여 조사될 수 있으며 그리고 상기 복수의 후보 주차 루트들 각각에 대한 비용은 상기 검색 알고리즘의 연관된 비용 함수를 사용하여 결정될 수 있다 (단계 502). 예를 들어, 사용자가 미리 정해진 루트를 따르고 있지 않다면 (그리고 주차 루트의 계산을 수동으로 트리거하도록 결정한다면) 상기 원래 위치는 차량의 현재 위치일 수 있다. 대안으로, 알려진 목적지에 대해 루트가 미리 결정되었다면, 상기 원래 위치는 상기 미리 정해진 루트 상의 상기 서브 네트워크의 첫 번째 세그먼트일 수 있으며, 또는, 예를 들어, 주차 루트의 계산을 사용자가 수동으로 트리거하거나, 또는 트리거하기 위한 자동적인 제안을 확인한 이후의 상기 서브-네트워크의 첫 번째 세그먼트일 수 있다.

최적 비용을 가진 후보 주차 루트는 그래서 주차 루트로서의 출력을 위해, 예를 들면, 사용자에게로의 디스플레이를 위해 선택될 수 있다 (단계 503). 상기 출력은 주차 루트이며, 이 경우 목적지까지의 보행 시간이나 거리는 소망된 임계 (예를 들면, 400 m) 미만이며 그리고 상기 주차 루트는 특정된 양의 예상 누적 운전 및 보행 시간 (예를 들면, 20 분)을 구비한다.

본 발명의 실시예들에 따라 주차 루트를 생성하기 위해 다양한 적합한 알고리즘들이 사용될 수 있다. 바람직한 주차 루트의 예가 이제 설명될 것이다.

주차 루트 알고리즘을 위한 입력은 다른 변수들 중에서도 특히 다음의 것들 중 어느 하나 또는 모두를 적합하게 포함할 수 있다:

- 도로 네트워크를 나타내는 관리된 그래프;

- 상기 그래프 내 정점 (vertex)로서의 목적지 위치;

- (목적지에 가까운) 상기 그래프 내 정점으로서의 현재 위치;

- 각 세그먼트 a에 대해, 빈 주차 공간이 존재하는 확률 p(a);

- 각 세그먼트 a에 대해, 그 세그먼트를 통해 운전하기 위한 시간 t(a);

- 각 세그먼트 a에 대해, 우리가 이 호 (arc)에 주차한다면, 그 호의 중간으로부터 목적지까지 걷기 위한 시간 w(a); 그리고

- 각 세그먼트 a에 대해, 동일 도로의 반대편 방향을 기술하는 세그먼트 o(a) (어떤 도로를 통해 한 방향으로 운전하는 것은 양 방향들에 대한 확률을 0으로 세팅한다고 가정한다. 즉, 운전자는 도로의 양 측면들을 스캔하며 그리고 자유 주차 공간들은 절대로 다시 나타나지 않을 것이라고 가정한다).

주차 루트는 서브-네트워크 내 세그먼트들 (a₁, ..., a_n)의 연결된 세트에 의해 대체적으로 한정된다고 인정될 수 있다. 주어진 주차 루트 (r = a₁, ..., a_n)에 대해, 상기의 입력(들)으로부터 다양한 관련 특성들을 계산하는 것이 그래서 가능하다. 상기 다양한 관련 특성들은 다음의 것들을 포함하지만, 그것들로 한정되지는 않는다:

- 사용자가 세그먼트를 이전에 볼 수 있었다는 것을 고려한 그 세그먼트 a_i 에 대한 수정된 주차 확률 p_i 는 다음과 같다:

- 이 루트를 따를 때에 주차할 곳을 찾는 것의 성공 확률 p^s 는 다음과 같다:

- 이 루트를 따를 때에 특별한 세그먼트 a_i 상에 주차할 확률 s_i (이것은 이미 이전에 주차할 곳을 찾지 못하고 그 후에 a_i 상에서 주차할 곳을 찾는 것의 조합임)는 다음과 같다:

- 세그먼트 a₁ 내지 세그먼트 a_i를 통한 운전을 위한 시간은 다음과 같다:

- 운전 및 보행을 위한 예상 누적 시간으로, 주차할 곳을 찾지 못한다고 가정한다 (세그먼트 a_i 상에서 주차할 곳을 찾지 못할 때에, 상기 예상 시간은 (Arndt 등에서처럼) i 까지 바로 합산하기보다는 상기 호의 중간에 대해, 그래서 추가의 항 t(a_i)/2에 대해 결정된다. 이것은 더욱 현실적인 결과들을 제공하는 것으로 믿어진다):

이 항목은 단순하게 호 (arc) 당 가중치의 합은 아니라는 것이 인정될 것이다. 그러나, 이것은 여전히 증가하여 계산될 수 있다. 즉, 일부 루트 r = a₁, ..., a_n 에 대해 p^s 및 t^s 가 주어지면, 추가된 다른 세그먼트 a_{n+ 1} 로부터 상기 루트까지의 결과인 t^s _{n +1} 를 계산하는 것이 가능하며, 스크래치로부터 t^s _{n +1} 를 계산하는 것을 빠르게 하는 결과를 가져온다. 이를 위해, a_n+1 상에 주차하는 확률이 먼저 계산되며, 주차할 곳이 발견되었다고 가정한다:

그리고 그 후에:

본 발명의 실시예들에 따른 알고리즘들은 Arndt 등에서 설명된 것들과 일부 유사성들을 가질 수 있다는 것이 인정될 것이다. 그러나, 본 발명의 실시예들에서 사용된 방법은 모델의 면 (최적화 목표) 및 서브-네트워크를 조사하기 위해 사용된 검색 알고리즘의 면 두 가지 모두에서 상이할 수 있다.

예를 들어, Arndt 등에서, 비용 함수는 다음과 같이 주어진다:

이것은 주차 루트의 끝 부분에 도달할 때에 주차할 곳을 바로 찾을 것이며 목적지까지의 보행 시간은 0 이라는 가정에 대응한다. 이 가정은, ε가 작으면 (예컨대, 1 %), 이 경우는 무시할 수 있으며 상기 가정은 크게 중요하지 않다는 것이다.

본 출원인은 이 접근 방식에 다양한 문제점들이, 알고리즘적으로 그리고 도메인 모델링 전망에서도 존재할 수 있다는 것을 인식했다. 예를 들면, Arndt 등에서 설명된 비용 함수를 사용하면, 동일한 예상 시간을 가지지만, 예를 들어, 20% 대 40%의 주차 확률을 가지는 경로는 동일한 비용을 가질 것이다 (즉, 무한대 비용). 이것은 더 유망한 경로들을 향하여 최적 프로세스를 안내하는 것을 어렵게 만든다. 또한, ε 를 위한 어떤 보편적인 '양호한' 값도 존재하지 않는다. 예컨대, 보행 및 전체 시간 상에 강제가 주어지면, 몇몇 상황들에서는 어떤 루트도 전혀 얻지 못할 수 있을 것이다. 이것은 ε가 너무 낮게 세팅되지 않아야 한다는 것을 의미한다. 그러나, 그 경우에, 예를 들어, ε = 0.2 이면, 동일한 예상 시간을 가지지만, 예를 들면, 80% 대 99%의 주차 확률을 가지는 경로는 동일한 비용을 가질 것이며, 이때에 운전자에 대해서 상기 두 번째 것이 분명하게 더 낫다.

그래서, 본 발명의 실시예들에서, 모든 부호 주차 루트들에 대해, 다음의 비용 함수가 유리하게도 사용될 수 있다:

.

여기에서, t^e 는 루트의 끝에서부터 목적지 위치까지의 운전에 대한 시간이며, 그리고 t^b 는 일정한 시간 페널티, 예를 들면, 약 20 분의 시간 페널티이다. 이 시간 페널티는 운전자의 선호도에 의해 설명될 수 있다. 예컨대, 운전자는 노상 주차할 곳을 찾을 수 없을 때에 해야 할 대안의 계획, 예를 들면, 도로 밖 주차할 곳을 구입하거나, 포기하고 집으로 운전자하거나, 또는 불법 주차하기 위한 대안의 계획을 가져야 한다. 그래서, 운전자가 어떤 노상 주차 검색 지속시간에 대해 동의하거나 대안의 계획으로 갈 것을 요청받으면, 운전자가 오히려 대안의 계획으로 가는 경우인 몇몇 임계 상황이 존재할 것으로 예상된다. 이것은 비용 t^b 에 의해 대표된다. 운전자가 주차 루트의 끝에 도달하며 (비용 t_n) 노상 주차를 포기할 때에, 먼저 목적지로 운전하고 (비용 t^e) 그 후에 계획 B를 실행 (비용 t^b)할 것을 필요로 한다; 이것은 확률 1-p^s 로 발생한다.

이 비용 함수는 그러므로 Arndt 등에서 설명된 것보다 현실적인 상황의 더욱 실제적인 표현을 제공할 수 있다는 것이 인정될 것이다.

비록 상기 비용 함수가 시간 값들에 관련하여 위에서 설명되었지만, 상기 비용 함수는 거리의 면에서 동등하게 공식화될 수 있다는 것이 인정될 것이다. 즉, 운행이나 보행 시간, 또는 시간 페널티를 고려하는 것 대신에, 후보 주차 루트를 위한 비용을 결정할 때에, 상기 비용 함수는 대신에 운행이나 보행 거리들, 및 거리 페널티들의 면에서 공식화될 수 있다. 그래서, 위에서 시간 값에 대한 참조는 실시예들에서 대응하는 거리 값으로 대체될 수 있다.

후보 주차 루트들을 생성하기 위해서 세그먼트들을 조사하기 위해 Arndt 등에서 사용된 검색 알고리즘은 표준의 분기한정 (branch-and-bound) 알고리즘이다. 실시예들에서, Arndt 등에서 설명된 동일한 기본적인 너비 우선 검색 (breadth-first-search) 전략을 따르는 알고리즘이 사용되며, 여기에서 경로들의 세트 (즉, 후보 주차 루트들)가 유지되며 그 경로들을 한 호 (arc)만큼 확장하는 모든 확률들이 최대 길이에 도달할 때까지 생성되며, 그리고 이제까지 기록된 최선의 경로가 리턴된다. 그러나, 이 지수-시간 접근 방식을 실행 시간에 대한 솔루션 품질을 트레이드 오프함으로써 실행할 수 있게 만드는 여러 개선책들이 예상된다. 동시에, 이것은 실질적으로 더 양호한 결과들이 Arndt 등에서의 알고리즘보다 더 빠른 것을 가능하게 한다.

예를 들면, 실시예들에서, 검색 알고리즘의 전체적인 실행 시간은 경로 내 세그먼트들의 개수를 세트함으로써 (예를 들면, 50개 세그먼트라고 가정) 그리고/또는 경로 길이 당 경로들의 개수를 임계 밑으로, 즉, 최선 비용들을 가진 경로들로 유지함으로써 (예를 들면, 경로 길이 당 최대 250개 경로들을 유지함으로써) 경계가 정해질 수 있다. 동시에, 이 접근 방식들은 실행 시간의 상단 경계를 부여할 수 있다 (이 실행 시간이 관련된 디바이스들 상에서 적당하도록 상수들이 선택된다). 원칙적으로, 검색 시간 및 보행 거리 한계 내에 유한의 많은 경로들만이 존재하지만, 이것이 상대적으로 큰 검색 공간일 수 있기 때문에, 실행 시간은 이미 경계가 정해져 있다.

또한, 경로들은 적합하게 제거될 수 있다. 예를 들면, 몇몇 경로들에 대해, 그 경로들은 최적 경로까지 확장될 수 없다는 것이, 또는 무시할 수 있는 향상만을 생기게 할 것이라는 것이 증명될 수 있다. 경로의 최선의 가능한 확장은 목적지까지 운전하고 그곳에서 주차할 곳을 바로 찾는다는 것이다. 이것은 경로의 임의 확장의 비용에 관한 하단 경계 LB를 부여한다. LB가 현재의 알려진 최선 비용보다 더 나쁘면, 상기 경로는 제거될 수 있다. 또한, 상기 경로가 중간에서 0이 아닌 주차 확률을 잡지 않으면서 두 차례 동일한 정점 (vertex)을 방문한다면, 상기 사이클은 제거될 수 있을 것이며 상기 경로는 제거될 수 있다 (이 경우에, 최단 루트가 회전 제한들을 어기지 않는다는 것이 보장될 필요가 있다). 예를 들어, 1 - (LB / (운전에 대한 예상 시간 더하기 보행에 대한 예상 시간)) < 0.01 이면, 상기 경로를 확장시킴으로써 솔루션을 많아야 1% 만큼 향상시킬 수 있으며, 그리고 상기 경로는 제거될 수 있다.

종종 양호한 솔루션을 상대적으로 빠르게 찾을 수 있으며, 그러면 어떤 실질적인 향상을 하지 않으면서 다른 솔루션들을 찾기 위한 시간이 낭비될 수 있다. 실시예들에서, 이것이 탐지될 수 있으며 그리고 주차 검색 알고리즘은 조기에 종료될 수 있다. 예를 들면, 적합한 임계를 넘는 상대적으로 높은 확률 (예를 들면, 99%)을 가진 경로가 발견되며, 그리고 그 후에 특정 회수 (예를 들면, 10회)의 사이클 동안 어떤 향상도 존재하지 않는다면, 상기 주차 검색 알고리즘은 조기에 종료될 수 있다. 어떤 경우에, 예를 들어, 25회 동안 어떤 향상도 존재하지 않는다면, 상기 알고리즘은 종결될 수 있다.

다른 실시예에서, 주차 루트 상에서 차량이 주차 공간을 성공적으로 찾을 확률이 미리 정해진 주차 성공 확률 임계를 초과하는 후보 주차 루트가 식별될 때에 상기 검색 알고리즘은 서브-네트워크의 세그먼트들을 계속해서 조사하며 그리고 출력을 위한 하나 이상의 후보 주차 루트들이 상기 결정된 비용에 기초하여 선택된다.

상기 모델 (비용 함수) 및 알고지름에 대한 다양한 다른 조절들이 또한 기대될 수 있다. 예컨대, 실시예들에서, 시각화하기에 더 어려운 필요 없이 긴 루트들을 억제하기 위해 세그먼트 당 비용 페널티가 부가될 수 있다. 예를 들면, 0.5초의 페널티가 세그먼트마다 비용 함수에 부가될 수 있다. 유사하게, 예를 들면, U-턴들이나 다른 바람직하지 않은 루트 특성들을 억제하기 위해 비용 페널티들이 부가될 수 있다. 예컨대, 120초의 페널티가 U-턴에 부가될 수 있다.

본 발명의 다양한 모습들 및 실시예들이 지금까지 설명되었지만, 본 발명의 범위는 여기에서 제시된 특별한 설비들에 한정되지 않으며, 첨부된 청구항들의 범위 내에 속한 모든 설비들, 그리고 그 설비들에 대한 수정 사항들 및 대안들을 포함하기 위해 대신에 확장된다는 것이 인정될 것이다.

동반 청구항들이 여기에서 설명된 특징들의 특별한 조합들을 제시하지만, 본 발명의 범위는 지금부터 청구되는 특별한 조합들에 한정되지 않으며, 그 특별한 조합들이 동반 청구항들에서 특히 열거되었거나 열거되지 않은 것에 무관하게 본원에서의 특징들이나 실시예들의 임의 조합들을 포함하도록 대신에 확장된다는 것에 또한 유의해야 한다.

Claims (26)

1. 지리적 영역 내에서 도로 네트워크 상으로 운행하는 차량을 위한 주차 루트를 시스템에 의해 결정하는 방법으로서,
   상기 도로 네트워크 중 적어도 일부 도로들은 연관된 적어도 하나의 주차 공간을 가지며, 상기 도로 네트워크는 그 도로 네트워크의 도로들을 나타내는 복수의 세그먼트들을 포함하는 전자 지도에 의해 표현되어 있으며, 각 세그먼트는 그 세그먼트의 길이를 표시하는 길이 속성을 포함하는 연관된 하나 이상의 속성들을 가지며, 그리고 적어도 하나의 주차 공간을 가진 도로들을 나타내는 적어도 상기 세그먼트들은 그 세그먼트 상에 빈 주차 공간이 존재하는 확률을 표시하는 확률 속성을 가지며, 상기 방법은:
   상기 지리적 영역 내 목적지 위치를 획득하는 단계;
   상기 목적지 위치의 미리 정해진 보행 시간이나 거리 내의 도로들을 나타내는 상기 전자 지도의 세그먼트들의 서브세트를 포함하는 서브-네트워크를 결정하는 단계;
   적어도 하나의 연관된 주차 공간을 가진 도로들을 나타내는 상기 서브-네트워크의 세그먼트들에 대해 적어도, 상기 세그먼트로부터의 보행 시간이나 거리를 표시하는 데이터를 상기 목적지 위치에 연관시키는 단계;
   연관된 비용 함수를 구비한 검색 알고리즘을 이용하여, 복수의 후보 주차 루트들을 식별하기 위해 상기 서브-네트워크의 세그먼트들을 원래 위치로부터 조사하는 단계로, 각 후보 주차 루트는 상기 서브-네트워크의 연결된 세그먼트들의 경로를 포함하며, 상기 조사하는 것은 상기 주차 루트의 세그먼트들 각각의 길이 속성 및 확률 속성을 이용하여 상기 비용 함수에 따라 복수의 후보 주차 루트들 각각에 대한 비용을 결정하는 것을 포함하며, 주어진 주차 루트에 대한 비용은 차량이 그 주차 루트 상의 주차 공간을 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간이나 거리에 기반하는, 조사 단계; 그리고
   상기 결정된 비용들에 기반하여 출력을 위한 후보 주차 루트들 중 하나 이상을 선택하는 단계를 포함하며,
   상기 예상 누적 운행 및 보행 시간이나 거리는, 각 세그먼트 상에 성공적으로 주차하는 가능성으로 가중치가 부여된 주차 루트를 따른 세그먼트들 각각에 대한 누적 운행 및 보행 시간이나 거리의 평균이며,
   세그먼트에 대한 누적 운행 및 보행 시간이나 거리는 그 세그먼트에 도달하기 위한 운행 시간이나 거리와 그 후에 그 세그먼트로부터 상기 목적지 위치에 도달하기 위한 보행 시간이나 거리의 합을 포함하는, 방법.
2. 제1항에 있어서,
   차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 기준을 초과하는 후보 주차 루트가 식별될 때에 상기 검색 알고리즘은 조기에 종결되는, 방법.
3. 제1항 또는 제2항에 있어서,
   차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 기준을 초과하며 그리고 그 후에 특정 개수의 사이클들에 대해 어떤 향상도 없는 후보 주차 루트가 식별될 때에 상기 검색 알고리즘은 조기에 종결되는, 방법.
4. 제1항 또는 제2항에 있어서,
   상기 서브-네트워크의 세그먼트들은 여전히 조사되고 있으면서, 차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 기준을 초과하는 후보 주차 루트가 식별될 때에, 출력을 위한 하나 이상의 후보 주차 루트들이 상기 결정된 비용에 기반하여 선택되는, 방법.
5. 제1항 또는 제2항에 있어서,
   주어진 주차 루트에 대해 상기 정해진 비용은:
   주차 루트를 통과할 때에 차량이 주차 공간을 성공적으로 찾을 확률에, 주차 루트를 통과할 때에 빈 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 보행 시간이나 거리 그리고 주차 루트를 따른 예상 누적 운행시간이나 거리로 가중치 부여된 것을 나타내는 제1 항목; 그리고
   주차 루트의 끝까지의 운행 및 주차 공간을 찾지 못하는 것과 연관된 페널티에, 주차 루트 상의 주차 공간을 찾지 못하는 확률로 가중치 부여된 것을 포함하는 제2 항목의 합을 포함하는, 방법.
6. 제1항 또는 제2항에 있어서,
   주어진 주차 루트에 대해 상기 정해진 비용은,
   주차 공간이 발견되지 않는 이벤트 시에 주차 루트의 끝으로부터 목적지 위치로 운행하는 것과 연관된 페널티에 주차 루트 상에서 주차 공간을 찾지 못하는 확률로 가중치 부여된 것을 포함하는, 방법.
7. 제1항 또는 제2항에 있어서,
   주어진 주차 루트에 대해 상기 정해진 비용은,
   주차 루트 상에서 주차 공간을 찾지 못하는 확률로 가중치 부여된 일정한 페널티를 포함하며, 옵션으로는 상기 일정한 페널티의 값은 사용자 선호들에 기반하여 세팅되거나 선택되는, 방법.
8. 제1항 또는 제2항에 있어서,
   주어진 주차 루트에 대해 상기 정해진 비용은 주차 경로를 따라 포함된 세그먼트들의 개수에 관련된 페널티를 포함하는, 방법.
9. 제1항 또는 제2항에 있어서,
   상기 검색 알고리즘은 분기한정 (branch-and-bound) 알고리즘을 포함하는, 방법.
10. 제1항 또는 제2항에 있어서,
    상기 검색 알고리즘을 사용하여 식별되고 있는 후보 주차 루트들 내에 포함하기 위한 세그먼트들의 최대 개수를 세팅하는 단계를 포함하는, 방법.
11. 제1항 또는 제2항에 있어서,
    서브-네트워크의 세그먼트들을 조사하는 상기 단계 동안에 상기 검색 알고리즘에 의해 유지된 후보 주차 루트들의 최대 개수를 세팅하는 단계를 포함하는, 방법.
12. 제1항 또는 제2항에 있어서,
    상기 서브-네트워크를 결정하는 단계는 목적지 위치로부터의 도달가능성 검색을 수행하는 단계를 포함하는, 방법.
13. 제1항 또는 제2항에 있어서,
    상기 목적지 위치는 운행가능 네트워크 내 미리 정해진 알려진 위치인, 방법.
14. 제1항 또는 제2항에 있어서,
    상기 목적지 위치는 상기 차량의 현재 위치인, 방법.
15. 제1항 또는 제2항에 있어서,
    상기 선택된 하나 이상의 주차 루트와 함께 출력하기 위해 상기 서브-네트워크를 나타내는 데이터를 제공하여 상기 하나 이상의 주차 루트들과 함께 상기 서브-네트워크가 디스플레이될 수 있도록 하는 단계를 포함하는, 방법.
16. 제12항에 있어서,
    상기 도달가능성 검색은 상기 목적지 위치의 미리 정해진 보행 시간이나 거리에 기반하여 도달가능성 영역을 한정하도록 수행되며, 상기 결정된 서브-네트워크는 차량이 통과할 수 있는 도로들을 나타내는 세그먼트들만을 포함하지만, 상기 서브-네트워크 결정을 위해 사용된 도달가능성 검색은 도로 세그먼트 및 보행자 세그먼트 둘 모두를 포함하는 보행자가 통과할 수 있는 세그먼트들을 고려하는, 방법.
17. 제1항 또는 제2항에 있어서,
    상기 주차 경로를 생성하는 방법은 상기 차량이 상기 목적지 위치의 미리 정해진 임계 거리 내에 있을 때에 트리거되거나 프롬프트되는, 방법.
18. 제1항 또는 제2항에 있어서,
    상기 누적 운행 및 보행 시간이나 거리는 상기 빈 주차 공간까지의 운행 시간이나 거리 그리고 상기 빈 주차 공간으로부터 상기 목적지 위치까지의 보행 시간이나 거리의 합을 포함하는, 방법.
19. 지리적 영역 내에서 도로 네트워크 상으로 운행하는 차량을 위한 주차 루트를 결정하는 시스템으로서,
    상기 도로 네트워크 중 적어도 일부 도로들은 연관된 적어도 하나의 주차 공간을 가지며, 상기 도로 네트워크는 그 도로 네트워크의 도로들을 나타내는 복수의 세그먼트들을 포함하는 전자 지도에 의해 표현되어 있으며, 각 세그먼트는 그 세그먼트의 길이를 표시하는 길이 속성을 포함하는 연관된 하나 이상의 속성들을 가지며, 그리고 적어도 하나의 주차 공간을 가진 도로들을 나타내는 적어도 상기 세그먼트들은 그 세그먼트 상에 빈 주차 공간이 존재하는 확률을 표시하는 확률 속성을 가지며, 상기 시스템은:
    상기 지리적 영역 내 목적지 위치를 획득하는 수단;
    상기 목적지 위치의 미리 정해진 보행 시간이나 거리 내의 도로들을 나타내는 상기 전자 지도의 세그먼트들의 서브세트를 포함하는 서브-네트워크를 결정하는 수단;
    적어도 하나의 연관된 주차 공간을 가진 도로들을 나타내는 상기 서브-네트워크의 세그먼트들에 대해 적어도, 상기 세그먼트로부터의 보행 시간이나 거리를 표시하는 데이터를 상기 목적지 위치에 연관시키는 수단;
    연관된 비용 함수를 구비한 검색 알고리즘을 이용하여, 복수의 후보 주차 루트들을 식별하기 위해 상기 서브-네트워크의 세그먼트들을 원래 위치로부터 조사하는 수단으로, 각 후보 주차 루트는 상기 서브-네트워크의 연결된 세그먼트들의 경로를 포함하며, 상기 조사하는 것은 상기 주차 루트의 세그먼트들 각각의 길이 속성 및 확률 속성을 이용하여 상기 비용 함수에 따라 복수의 후보 주차 루트들 각각에 대한 비용을 결정하는 것을 포함하며, 주어진 주차 루트에 대한 비용은 차량이 그 주차 루트 상의 주차 공간을 성공적으로 찾는 확률 그리고 상기 주차 루트를 따라 주차 공간이 발견되어야 하는 상기 목적지 위치까지의 예상 누적 운행 및 보행 시간이나 거리에 기반하는, 조사 수단; 그리고
    상기 결정된 비용들에 기반하여 출력을 위한 후보 주차 루트들 중 하나 이상을 선택하는 수단을 포함하며,
    상기 예상 누적 운행 및 보행 시간이나 거리는, 각 세그먼트 상에 성공적으로 주차하는 가능성으로 가중치가 부여된 주차 루트를 따른 세그먼트들 각각에 대한 누적 운행 및 보행 시간이나 거리의 평균이며,
    세그먼트에 대한 누적 운행 및 보행 시간이나 거리는 그 세그먼트에 도달하기 위한 운행 시간이나 거리와 그 후에 그 세그먼트로부터 상기 목적지 위치에 도달하기 위한 보행 시간이나 거리의 합을 포함하는, 시스템.
20. 제19항에 있어서,
    차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 기준을 초과하는 후보 주차 루트가 식별될 때에 상기 검색 알고리즘은 조기에 종결되는, 시스템.
21. 제19항 또는 제20항에 있어서,
    차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 기준을 초과하며 그리고 그 후에 특정 개수의 사이클들에 대해 어떤 향상도 없는 후보 주차 루트가 식별될 때에 상기 검색 알고리즘은 조기에 종결되는, 시스템.
22. 제19항 또는 제20항에 있어서,
    출력을 위한 후보 주차 루트들 중 하나 이상을 선택하는 상기 수단은, 상기 서브-네트워크의 세그먼트들을 조사하기 위한 상기 수단이 여전히 사용되고 있으면서, 차량이 상기 주차 루트 상의 주차 공간을 성공적으로 찾는 확률이 미리 정해진 주차 성공 확률 기준을 초과하는 후보 주차 루트가 식별될 때에, 출력을 위한 하나 이상의 후보 주차 루트들을 선택하도록 구성된, 시스템.
23. 제19항 또는 제20항에 있어서,
    상기 서브-네트워크를 결정하는 것은 상기 목적지 위치의 미리 정해진 보행 시간이나 거리에 기반하여 도달가능성 영역을 한정하기 위해 상기 목적지 위치로부터의 도달가능성 검색을 포함하며, 상기 결정된 서브-네트워크는 차량이 통과할 수 있는 도로들을 나타내는 세그먼트들만을 포함하지만, 상기 서브-네트워크 결정을 위해 사용된 도달가능성 검색은 도로 세그먼트 및 보행자 세그먼트 둘 모두를 포함하는 보행자가 통과할 수 있는 세그먼트들을 고려하는, 시스템.
24. 제19항 또는 제20항에 있어서,
    상기 누적 운행 및 보행 시간이나 거리는 상기 빈 주차 공간까지의 운행 시간이나 거리 그리고 상기 빈 주차 공간으로부터 상기 목적지 위치까지의 보행 시간이나 거리의 합을 포함하는, 시스템.
25. 내비게이션 디바이스의 하나 이상의 프로세서들에 의해 실행될 때에 상기 내비게이션 디바이스로 하여금 제1항 또는 제2항에 따른 방법을 수행하도록 하는 명령어들을 포함하는, 비-일시적 컴퓨터 판독가능 물리적 저장 매체에 저장된 컴퓨터 프로그램.
26. 저장된 제25항의 컴퓨터 프로그램을 구비한 비-일시적 컴퓨터 판독가능 물리적 저장 매체.