Generating transport routes using public and private modes

• US 8,909,475 B2
• Filed: 03/08/2013
• Issued: 12/09/2014
• Est. Priority Date: 03/08/2013
• Status: Active Grant

• Current Assignee: Zzzoom LLC
• Original Assignee: Zzzoom LLC
• Inventors: Gishen, Kayle
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): Lee, Tyler J
• Application Number:
  US13/790,467
• Publication Number:
  US 20140257697A1
• Time in Patent Office: 641 Days
• Field of Search: 705/14.58, 707/999.004, 709/204, 701/300, 701/302, 701/410, 701/467, 701/526, 701/527, 701/532, 701/533, 701537-541
• US Class Current: 701/537
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G06Q 30/00 Commerce

Abstract

A system for planning transportation for a passenger along a route from an origin to a destination includes software which stores information pertaining to the passenger'"'"'s desired route, one or more public transportation options, and one or more drivers willing to transport the passenger, using a private vehicle, along at least a portion of the route. Drivers bids for transporting the passenger are obtained using crowd-sourcing. The public transportation information and driver information are used to calculate one or more combinations of private legs and public legs using a graph search algorithm and the heuristic formula w=nt_p(+*)(t_m)^x, where n and x are constant, x<1, and t_p, t_m are time waiting and time moving, respectively.

Claims

1. A system for planning transportation for a passenger along a route from an origin to a destination, comprising:

at least one computer executing software stored on non-transitory media, the software configured for—

storing information pertaining to the passenger, including a desired route;

storing information pertaining to one or more public transportation options which can be used by the passenger to travel along at least a portion of the route along one or more public legs, each public leg having a starting and ending location;

storing information pertaining to one or more crowdsourced drivers willing to transport the passenger, using a private vehicle, along at least a portion of the route along one or more private legs, each private leg having a starting and ending location;

using stored public transportation information and information from the crowdsourced drivers to calculate one or more combinations of private legs with public legs, the combination including at least one of (a) one or more private legs beginning at one or more public leg ending locations and (b) one or more private legs ending at one or more public leg starting locations;

communicating the calculated combinations to the passenger; and

communicating a location of the passenger to one of the one or more crowdsourced drivers.

2. The system of claim 1, wherein calculating one or more combinations uses the formula w=nt_p(+*)(t_m)^x where n and x are constant, x<

1, and t_p, t_m are time waiting and time moving, respectively.

3. The system of claim 1, wherein stored information pertaining to the passenger, and information pertaining to drivers, is input using at least one of a web browser and a smartphone application.

4. The system of claim 1, wherein information pertaining to one or more drivers is obtained using crowd-sourcing.

5. The system of claim 1, wherein calculating one or more combinations uses an A* style methodology and heuristics including the formula w=nt_p(+*)(t_m)^x.

6. The system of claim 1, wherein the information pertaining to public transportation options is filtered to select for options having at least one of a relatively shorter distance and a relatively shorter travel time than options not selected.

7. The system of claim 1, wherein calculating is performed using a graph methodology where an original edge, corresponding to a public or private leg, is replaceable, and where the graph remains monotonic, directed, and acyclic when new edges are inserted.

8. The system of claim 1, wherein calculating uses a graph search algorithm to select a first subset of optimal routes using least edges traversed, relative to all possible routes.

9. The system of claim 8, wherein a second subset is selected from the first subset using the graph search algorithm.

10. The system of claim 9, wherein when the second subset is rejected by the passenger, or is suboptimal in accordance with predetermined criteria, the first subset is recalculated using public transportation options not included when calculating the first subset.

17. The system of claim 1, wherein calculating one or more combinations uses an A* style methodology and heuristics including the formula w=nt_p(+*)(t_m)^x.

11. A method for planning transportation for a passenger along a route from an origin to a destination, comprising:

using at least one computer executing software stored on non-transitory media, the software configured for—

storing information pertaining to the passenger, including a desired route provided by the passenger;

storing information pertaining to one or more public transportation options which can be used by the passenger to travel along at least a portion of the route along one or more public legs, each public leg having a starting and ending location;

storing information pertaining to one or more crowdsourced drivers willing to transport the passenger, using a private vehicle, along at least a portion of the route along one or more private legs, each private leg having a starting and ending location;

using stored public transportation information and information from the crowdsourced drivers to calculate one or more combinations of private legs with public legs, the combination including at least one of (a) one or more private legs beginning at one or more public leg ending locations and (b) one or more private legs ending at one or more public leg starting locations; and

communicating the calculated combinations to the passenger.

12. The method of claim 11, wherein when storing information provided by the passenger, the software is further configured for:

accepting spoken words from the passenger, the spoken words provided using a natural language format; and

processing the natural language format information to determine the desired route, using a variable context compiler which parses L1 to LN grammars simultaneously, and which uses a sliding window filter and a cascade architecture.

13. The method of claim 12, where the variable context compiler separates the natural language route information into string groups separated by a keyword, and processes each string group separately.

14. The method of claim 12, wherein a rule set of the variable context compiler is configured to analyze a plurality of different grammatical contexts of natural language route information.

15. The method of claim 11, wherein calculating one or more combinations uses the formula w=nt_p(+*)(t_m)^x where n and x are constant, x<

1, and t_p, t_m are time waiting and time moving, respectively.

16. The method of claim 11, wherein stored information pertaining to the passenger, and information pertaining to drivers, is input using at least one of a web browser and a smartphone application.

18. A system for planning transportation for a passenger along a route from an origin to a destination, comprising:

at least one computer executing software stored on non-transitory media, the software configured for—

storing information pertaining to the passenger, including a desired route;

storing information pertaining to one or more public transportation options which can be used by the passenger to travel along at least a portion of the route along one or more public legs, each public leg having a starting and ending location;

storing information pertaining to one or more crowdsourced drivers willing to transport the passenger, using a private vehicle, along at least a portion of the route along one or more private legs, each private leg having a starting and ending location, the information obtained by crowd-sourcing;

using stored public transportation information, and information provided by the crowdsourced drivers, to calculate one or more combinations of private legs with public legs using a graph search algorithm and the heuristic formula w=nt_p(+*)(t_m)^x, where n and x are constant, x<

1, and t_p, t_m are time waiting and time moving, respectively, the combination including at least one of (a) one or more private legs beginning at one or more public leg ending locations and (b) one or more private legs ending at one or more public leg starting locations; and

communicating the calculated combinations to the passenger.

19. The system of claim 18, wherein crowd-sourcing includes the crowdsourced drivers submitting bids to transport the passenger along one or more of the private legs.

20. The system of claim 18, wherein passengers submit bids to obtain transportation along one or more private legs.