Route planning process

• US 20080172172A1
• Filed: 12/21/2007
• Published: 07/17/2008
• Est. Priority Date: 01/19/2005
• Status: Abandoned Application

• Current Assignee: Ping-Chung Ng
• Original Assignee: Ping-Chung Ng
• Inventors: NG, Ping-Chung
• Application Number:
  US12/004,516
• Publication Number:
  US 20080172172A1
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• 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

Abstract

In a process for determining a route from a predetermined starting point to a predetermined destination, firstly, weights are assigned to route segments interconnected at route nodes. At least a first weight relating to a first route segment is varied by querying at least a data source based on at least a second weight relating to a second route segment. The second route segment is prior to the first route segment in a consideration of the route from the starting point to the destination. Subsequently, the route is determined by using a route finding algorithm, the algorithm taking the weights into account.

Claims

1-2. -2. (canceled)

5. (canceled)

10. (canceled)

11. A process for determining an optimized route from a predetermined starting point to a predetermined destination using a route finding algorithm, the route including route segments and route nodes, the route segments interconnecting at route nodes, the route segments having weights assigned thereto, the process comprising the steps of:

(a) determining an initial optimized route based on the weights assigned to the route segments between the predetermined starting point and the predetermined destination; and

(b) predetermining the optimized route during execution of the algorithm during the initial optimized route, wherein at least one of the route segments is determined by the cumulative weights of the preceding route segments, and at least one of the route segments has a weight which is dynamically variable during the optimized route.

3. The process of claim 6, wherein the dynamic weights of the route segments are assigned as a function of weights of the previous route segments.

4. The process of claim 6, wherein the weights are defined in terms of at least one of a time, a distance, and a cost.

6. The process of claim 13, further comprising the steps of:

(c) classifying the route segments into a plurality of map layers;

(d) assigning known fixed weights to the static route segments in each map layer;

(e) assigning unknown dynamic weights to the dynamic route segments with a specific parameter in each map layer, wherein at least of the dynamic weights is unknown;

(f) combining a plurality of route segment graphs of all the layers into a single route segment graph;

(g) determining a preferred route using the route finding algorithm with the known fixed weights taken into account;

(h) querying the unknown dynamic weights from a data source based on the value of previous weights when the route finding algorithm comes into the consideration of dynamic route segments;

(i) assigning the values of the unknown dynamic weights obtained from the data source to the dynamic route segments; and

(j) resuming the route finding algorithm and repeating steps (h) and (i) until the optimized path from a starting node to a destination node is determined.

7. The method according to claim 6, wherein the map layers are separated according to a coverage of various means of transportation.

8. The method according to claim 7, wherein the coverage of various means of transportation is defined in terms of at least one a region, a district, an intra-city region and an inter-city region.

9. The process of claim 11, wherein the route finding algorithm is a Dijkstra algorithm.

12. The process as claimed in claim 11, wherein at least some of the route segments include static weights.

13. The process as claimed in claim 12, further comprising the step of:

(c) dynamically varying a weight of a route segment based on a result of a query to a data source.

14. The process as claimed in claim 13, wherein the data source is updated in real time.

15. A computerized system comprising:

a processor;

memory means for storing a program executable by the processor to perform the method as claimed in claim 11;

an input device;

an output device;

a database; and

a communication network communicably connecting the processor, the memory means, the input device, the output device, and the database.

16. A computerized system comprising:

a processor;

memory means for storing a program executable by the processor to perform the method as claimed in claim 13;

an input device;

an output device;

database means for storing the data source; and

a communication network communicably connecting the processor, the memory means, the input device, the output device, and the database.

17. The computerized system as claimed in claim 15, wherein the communication network includes a wireless communication network.

18. The computerized system as claimed in claim 15, wherein at least one of the input device and the output device includes a mobile terminal.

19. The computerized system as claimed in claim 18, wherein the mobile terminal includes at least one of a mobile telephone, a PDA, and a portable computer.

20. A computer-readable medium adapted for storing computer-readable instructions executable by a computerized system for carrying out the method as claimed in claim 11.