NAVIGATION DEVICE USING MAP DATA WITH ROUTE SEARCH ACCELERATION DATA

Title:

NAVIGATION DEVICE USING MAP DATA WITH ROUTE SEARCH ACCELERATION DATA

Document Type and Number:

WIPO Patent Application WO/2011/004029

Kind Code:

A3

Abstract:

A method of creating map data including search acceleration data arranged to increase the speed at which a route can be planned across an electronic map comprising a plurality of navigable segments, each navigable segment representing a segment of a navigable route in the area covered by the map, wherein the method comprises: a) reducing the number of navigable segments to be considered in the creation of the search acceleration data by removing navigable segments to form a core network of navigable segments; b) dividing the electronic map into a set of hierarchical regions such that the or each navigable segment is categorized into at least one region in each level of the hierarchy; c) using a time varying function associated with at least some, and generally each, navigable segment of the core network to determine whether that navigable segment is part of minimum cost route to at least one of the regions and recording this determination in the search acceleration data.

More Like This:

WO/2008/073802	TRAVEL PLANNING SYSTEM THAT PRODUCES ANSWERS INVOLVING MULTIPLE SALES CHANNELS/PNRS/TICKETS PER ANSWER
JP5717476	Navigation device
WO/2013/171780	TRANSPORTATION ROUTE DISTRIBUTION RATIO CONTROL SYSTEM AND TRANSPORTATION ROUTE DISTRIBUTION CONTROL METHOD

Inventors:

SCHILLING HEIKO (GB)
GAWRILOW EWGENIJ (DE)
HILGER MORITZ (DE)
PROFOUS ANDREAS (DE)
WERBER JUERGEN (DE)

Application Number:

PCT/EP2010/059947

Publication Date:

March 24, 2011

Filing Date:

July 09, 2010

Export Citation:

Click for automatic bibliography generation Help

Assignee:

TOMTOM INT BV (NL)
SCHILLING HEIKO (GB)
GAWRILOW EWGENIJ (DE)
HILGER MORITZ (DE)
PROFOUS ANDREAS (DE)
WERBER JUERGEN (DE)

International Classes:

G01C21/34; G01C21/32; G06F17/30; G06Q10/00

Foreign References:

US6636800B1

2003-10-21

Other References:

DANIEL DELLING: "Engineering and Augmenting Route Planning Algorithms", PHD THESIS, 10 February 2009 (2009-02-10), Universität Karlsruhe (TH), Fakultät für Informatik, XP002612394, Retrieved from the Internet [retrieved on 20101202]
REINHARD BAUER, DANIEL DELLING: "SHARC: Fast and Robust Unidirectional Routing", ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS, vol. 14, 2.4, May 2009 (2009-05-01), pages 2.4.1 - 2.4.29, XP002612373
DANIEL DELLING ED - DAN HALPERIN ET AL: "Time-Dependent SHARC-Routing", 15 September 2008, ALGORITHMS - ESA 2008; [LECTURE NOTES IN COMPUTER SCIENCE], SPRINGER BERLIN HEIDELBERG, BERLIN, HEIDELBERG, PAGE(S) 332 - 343, ISBN: 978-3-540-87743-1, XP019107027
ROLF H. MÖHRING, HEIKO SCHILLING, BIRK SCHÜTZ, DOROTHEA WAGNER, THOMAS WILLHALM: "Partitioning graphs to speedup Dijkstra's algorithm", ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS, vol. 11, 2.8, 2007, pages 1 - 29, XP002612372, ISSN: 1084-6654, DOI: 1187436.1216585
DANIEL DELLING ET AL: "Engineering Route Planning Algorithms", 30 November 2008, ALGORITHMICS OF LARGE AND COMPLEX NETWORKS, SPRINGER BERLIN HEIDELBERG, BERLIN, HEIDELBERG, PAGE(S) 117 - 139, ISBN: 978-3-642-02093-3, XP019121077
JAKOBSSON M: "HUFFMAN CODING IN BIT-VECTOR COMPRESSION", INFORMATION PROCESSING LETTERS, AMSTERDAM, NL, vol. 7, no. 6, 1 October 1978 (1978-10-01), pages 304 - 307, XP000949386, ISSN: 0020-0190, DOI: DOI:10.1016/0020-0190(78)90023-6