Methodology and system for routing optimization in GPS-based Navigation, combining dynamic traffic data

• US 8,392,109 B2
• Filed: 12/10/2009
• Issued: 03/05/2013
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Fotios K. Liotopoulos, Paraskevi Karypidou
• Original Assignee: Fotios K. Liotopoulos, Paraskevi Karypidou
• Inventors: Liotopoulos, Fotios K., Karypidou, Paraskevi
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): Do, Truc M
• Application Number:
  US13/139,659
• Publication Number:
  US 20110251790A1
• Time in Patent Office: 1,181 Days
• Field of Search: 701/409, 701/430, 701/450, 701/451, 701/454, 701/462, 701/532
• US Class Current: 701/409
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

Abstract

Disclosed is a methodology for the collection, processing and distribution of traffic data and delivering more accurate routing in GPS-based Personal Navigation Assistants (PNAs). The methodology includes a) Data Collection Methodology (DCM), b) a Data Incorporation Methodology (DIM), and c) a Routing Methodology (RM). The DCM regards the collection of information related to the traffic flow in each road. The DIM includes a procedure executed at a central system (CS), outside the PNA, performing the incorporation of the “trace data” (i.e. user-submitted route-related information, including a list of periodically collected, time-stamped GPS samples, augmented with other parameter values defining the vehicle-type, weather-conditions, road-type, holiday-type), collected by the DCM. The RM determines, by means of suitable PNA software, the shortest route from a starting point to a final destination, through the combining the static data from existing maps residing inside the PNA, with the dynamic (time-variant) data derived by the DIM.

Claims

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

a) a Data Collection Methodology (DCM), which is characterized by a procedure for recording and processing by a PNA (with “

digital signature” and

“

digital digest”

, as defined in standard cryptology) 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 (uncharted) 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, and

ii) by the statistical incorporation and encoding of this data into a single “

global map”

(i.e. a map of the world) database, after 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”

(defined as conventional map data structures augmented with an extra layer of time-variant, traffic-related information, such as travel times per road segment for combinations of time-of-day, season-of-year, holiday-type, weather-conditions and vehicle-type), produced by the DIM, 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, and

ii) 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 three sub-methodologies (a)-(c) 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 travelled 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);

(where, a travelled road segment is identified by mapping a sequence of recorded GPS coordinates),

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 (i.e., well known cryptographic processes, also referred to as a “

mathematical summary”

of a given data set, which is generated by means of applying an irreversible hash function to the given input data, combined with asymmetric encryption), 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”

(i.e. user-submitted route-related information, consisting of a list of periodically collected, time-stamped GPS samples, augmented with other parameter values defining the vehicle-type, weather-conditions, road-type, holiday-type), 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 an encoded “

global map”

database;

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 derived by the DIM;

whereas, the RM is also characterized by the estimation of the fuel cost of a specific route and the subsequent determination, by 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 derived by the DIM;

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.

2. A methodology for the collection, processing and distribution of traffic data and delivering more accurate routing in GPS-based Personal Navigation Assistants (PNAs), the methodology comprising:

a) a Data Collection Methodology (DCM), which is characterized by a procedure for recording and processing by a PNA (with “

digital signature” and

“

digital digest”

, as defined in standard cryptology) of dynamic traffic data and vehicle parameters, which ensures the validity, authenticity, verifiability and uniqueness of the collected data;

this data including 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 (uncharted) 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, and

ii) by the statistical incorporation and encoding of this data into a single “

global map”

(i.e. a map of the world) database, after offline processing of the data performed by the CS,

c) a Routing Methodology (RM), which is characterized by the use of the encoded “

dynamic maps”

(defined as conventional map data structures augmented with an extra layer of time-variant, traffic-related information, such as travel times per road segment for combinations of time-of-day, season-of-year, holiday-type, weather-conditions and vehicle-type), produced by the DIM, 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, and

ii) decision criteria, such as, shortest travelling time, less fuel cost, or a combination thereof, as specified by the user/driver,

and the methodology being implemented with a Central System (CS) and one or more offline portable PNAs;

whereas, the three sub-methodologies (a)-(c) 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 travelled road segment, of a combination of information, including 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);

(where, a travelled road segment is identified by mapping a sequence of recorded GPS coordinates),

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 (i.e., well known cryptographic processes, also referred to as a “

mathematical summary”

of a given data set, which is generated by means of applying an irreversible hash function to the given input data, combined with asymmetric encryption), 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”

(i.e. user-submitted route-related information, including a list of periodically collected, time-stamped GPS samples, augmented with other parameter values defining the vehicle-type, weather-conditions, road-type, holiday-type), 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 an encoded “

global map”

database;

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 derived by the DIM;

whereas, the RM is also characterized by the estimation of the fuel cost of a specific route and the subsequent determination, by 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 derived by the DIM;

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.

3. A methodology for the collection, processing and distribution of traffic data and delivering more accurate routing in GPS-based Personal Navigation Assistants (PNAs), the methodology comprising:

a) a Data Collection Methodology (DCM), which is characterized by a procedure for recording and processing by a PNA of dynamic traffic data and vehicle parameters;

this data including 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 (uncharted) 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, and

ii) by the statistical incorporation and encoding of this data into a single “

global map”

(i.e. a map of the world) database, after offline processing of the data performed by the CS,

c) a Routing Methodology (RM), which is characterized by the use of the encoded “

dynamic maps”

(defined as conventional map data structures augmented with an extra layer of time-variant, traffic-related information, such as travel times per road segment for combinations of time-of-day, season-of-year, holiday-type, weather-conditions and vehicle-type), produced by the DIM, 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, and

ii) decision criteria, such as, shortest travelling time, less fuel cost, or a combination thereof, as specified by the user/driver;

whereas, the three sub-methodologies (a)-(c) 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 travelled road segment, of a combination of information, including 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);

(where, a travelled road segment is identified by mapping a sequence of recorded GPS coordinates),

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 DIM refers to a procedure which is executed at a central system (CS), outside the PNA, performing the incorporation of the “

trace data”

(i.e. user-submitted route-related information, including a list of periodically collected, time-stamped GPS samples, augmented with other parameter values defining the vehicle-type, weather-conditions, road-type, holiday-type), collected by the DCM, into the central maps and the central databases;

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 an encoded “

global map”

database;

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 derived by the DIM;

whereas, the RM is also characterized by the estimation of the fuel cost of a specific route and the subsequent determination, by 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 derived by the DIM;

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.