×

METHODOLOGY AND SYSTEM FOR ROUTING OPTIMIZATION IN GPS-BASED NAVIGATION, COMBINING DYNAMIC TRAFFIC DATA

  • US 20110251790A1
  • Filed: 12/10/2009
  • Published: 10/13/2011
  • Est. Priority Date: 12/22/2008
  • Status: Active Grant
0
Associated Cases
0
Associated Defendants
0
Product Citations
0
Petitions
52
Forward Citations
0
Assignments
First Claim
Patent Images

1. Methodology for the collection, processing and distribution of traffic data and delivering more accurate routing in GPS-based Personal Navigation Assistants (PNAs).The said methodology consisting of:

  • a) a Data Collection Methodology (DCM), which is characterized by a procedure for recording and proper processing by a PNA (with digital signature and digital digest) of dynamic traffic data and vehicle parameters, which ensures the validity, authenticity, verifiability and uniqueness of the collected data;

    this data consisting of a “

    timestamp”

    (i.e., date and time of recording), speed and duration of traveling through each road segment, state of the road, weather conditions, type of vehicle, working day or type of holiday;

    both for the already mapped, and for unmapped road network,b) a Data Incorporation Methodology (DIM), which is characterized by;

    i) the checking by the Central System (CS) of the integrity, authenticity, uniqueness and validity of the data submitted by a PNA to the CS, andii) by the statistical incorporation and proper encoding of this data into a single “

    global map”

    database, after suitable offline processing of the data performed by the CS,c) a Data Distribution Methodology (DDM), which is characterized by the selection of a “

    dynamic map”

    part from the single “

    global map”

    database of the CS, the ensuring of the integrity, authenticity and uniqueness of the data, and the re-encoded incorporation of the data in the available map system of a PNA,d) a Routing Methodology (RM), which is characterized by the use of the encoded “

    dynamic maps”

    in combination with the conventional (static) maps of a PNA, in order to obtain—

    using the PNA—

    an improved routing decision from a starting point to a final destination, with or without intermediate destinations, based on;

    i) dynamic (space/time-dependent) traffic data, i.e. the combination of time-of-the-day, day-of-the-week, season-of-the-year, type-of-vehicle, type-of-weather, road-conditions, and type-of-holiday, andii) decision criteria, such as, shortest travelling time, less fuel cost, or a combination thereof, as specified by the user/driver,and said methodology being implemented with a Central System (CS) and one or more offline portable PNAs;

    whereas, the said four sub-methodologies (a)-(d) are interdependent and compose in an integrated manner the overall methodology, which undividedly solves the technical problem of improving the routing decision accuracy of a PNA;

    whereas, the DCM regards the collection of information related to the traffic flow in each road segment (based on the traveling speed per type of vehicle and the state of the road in a given time period), by drivers that travel in the road network making use of their PNA;

    whereas, the DCM is characterized by the recording, for each road segment, of a combination of information, consisting of the traveling timestamp (time and date), the traveling duration and length of the segment, the weather conditions (or state of the road) (sun, fog, rain, snow), the type of the vehicle (low/medium/high speed, 2/4-wheel, truck, bus, motorcycle, pedestrian);

    whereas, the DCM is characterized by the data recorded also for non-registered road segments (i.e. those that are not included in the database of the map of a PNA), leading to the potential creation of new maps);

    whereas, the traffic data is recorded on a storage medium, at the PNA, in encrypted and compressed form, so that the privacy of the user'"'"'s personal data is ensured;

    whereas, along with the traffic data, additional information is also recorded in the PNA'"'"'s storage medium, such as a digital signature and a digital digest (e.g. MD5) of the data, so that the integrity and authenticity of the recorded information is ensured and proved to the central system, thus preventing or rejecting multiple submissions by the users;

    whereas, the DIM refers to a procedure which is executed at the central system (CS), outside the PNA, performing the incorporation of the trace data, collected by the DCM, into the central maps and the central databases;

    whereas, the DIM is characterized by the verification—

    with respect to the integrity, authenticity and uniqueness—

    of the trace data collected by the DCM;

    whereas, the DIM is also characterized by the temporary storage, at the central system, of the obtained data, until it is verified by means of comparing it with other similar trace data submitted by other users and corresponding to the same road segments, before this data is considered valid for distribution and become available to all other PNA users;

    whereas, the verification of the uploaded trace data is executed by statistical processing of a sufficient statistical sample (with averaging functions, exclusion of extreme values, normalization, and extrapolation), resulting in the creation of a properly encoded “

    global map”

    database;

    whereas, the DDM refers to a procedure, which is executed by the 50 Central System and performs the distribution of updated map data—

    as produced by the DIM—

    to PNA users;

    whereas, the DDM is characterized by the execution of a procedure for the distribution to a requesting PNA-user of a data subset of the “

    global map”

    residing inside the CS, with a combination of user input, including map area, available user credit and map data density;

    whereas, the DDM is also characterized by procedures delivering proper encoding, encryption, compression and storage of the requested (by a PNA user) of map data into a file, which is provided to the requesting user, thus ensuring and proving to the PNA the integrity and authenticity of the recorded information as well as effectively preventing multiple usages of the same map data by other PNA users;

    whereas, the DDM is also characterized by the verification, by means of a proper PNA software module, of the integrity and authenticity of the data provided to the requesting user by the DDM;

    whereas, the DDM is also characterized by the incorporation of the received data inside the PNA (by means of re-encoding it with data structures and techniques, such as sparse arrays, linked lists and hashing) and by the combined usage of the dynamic map data in parallel with existing static map data located within the user'"'"'s PNA, thus ensuring faster access and optimal exploitation of the map data by the PNA'"'"'s routing algorithm;

    whereas, the RM is characterized by the determining, by means of suitable PNA software, of the shortest route from a starting point to a final destination, with or without intermediate destinations, through the combining the static data from existing maps residing inside the PNA, with the dynamic (time-variant) data stored therein by the DDM;

    whereas, the RM is also characterized by the estimation of the fuel cost of a specific route and the subsequent determination, by suitable PNA software, of the most cost-effective route from a given starting point to a final destination, with or without intermediate destinations, through the combining the static data from existing maps residing inside the PNA, with the dynamic (time-variant) data stored therein by the DDM;

    whereas, the RM is also characterized by the capability to combine the aforementioned routing optimizations (i.e. shortest route and less costly route), based on criteria, selected interactively by the PNA user, for mapped or unmapped road network.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×