Purposefully selecting longer routes to improve user satisfaction

• US 10,168,167 B2
• Filed: 03/07/2018
• Issued: 01/01/2019
• Est. Priority Date: 01/25/2017
• Status: Active Grant

• Current Assignee: Via Transportation Inc.
• Original Assignee: Via Transportation Inc.
• Inventors: Rakah, Yaron, Shoval, Oren, Ramot, Daniel, Marcovitch, Shmulik
• Primary Examiner(s): Hilgendorf, Dale W
• Application Number:
  US15/914,821
• Publication Number:
  US 20180209804A1
• Time in Patent Office: 300 Days
• CPC Class Codes: B60N 2/002 Seats provided with an occupancy detection means mounted therein or thereon detection means responsive to presence or absence of children B60N2/266
• CPC Class Codes: B60W 60/00253 Taxi operations
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• 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: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• 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: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G06V 20/593 Recognising seat occupancy
• CPC Class Codes: G08G 1/005 including pedestrian guidance indicator
• CPC Class Codes: G08G 1/012 from other sources than vehicle or roadside beacons, e.g. mobile networks
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/096822 where the segments of the route are transmitted to the vehicle at different locations and times
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/123 indicating the position of vehicles, e.g. scheduled vehicles; Managing passenger vehicles circulating according to a fixed timetable, e.g. buses, trains, tramstransmission of navigation instructions to vehicles G08G1/0968
• CPC Class Codes: G08G 1/127 to a central station ; Indicators in a central station
• CPC Class Codes: G08G 1/148 : Management of a network of parking areas
• CPC Class Codes: G08G 1/20 : Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• CPC Class Codes: G08G 1/202 : Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• CPC Class Codes: H04W 4/40 : for vehicles, e.g. vehicle-to-pedestrians [V2P]

Abstract

An automated ridesharing dispatch system includes a communications interface configured to receive ride requests from a plurality of users and to receive from a plurality of communication devices associated with a plurality of ridesharing vehicles, indications of current locations of the plurality of ridesharing vehicles. The system also includes a memory configured to store a plurality of rules including a rule to select a fastest route for guiding a ridesharing vehicle, and a rule for reducing backtracking, even in instances where backtracking would result in shorter travel time. The system also includes at least one processor configured to assign the plurality of users to a common ridesharing vehicle, use the stored plurality of rules to determine a route for the ridesharing vehicle other than the fastest route, and in order to reduce backtracking, direct the ridesharing vehicle along the determined route other than the fastest route.

Claims

1. An automated ridesharing dispatch system, comprising:

a communications interface configured to;

receive ride requests from a plurality of users, wherein each ride request includes a starting point and a desired destination;

receive from a plurality of communication devices associated with a plurality of ridesharing vehicles, indications of current locations of the plurality of ridesharing vehicles;

memory configured to store a plurality of rules including a rule to select a fastest route for guiding a ridesharing vehicle, and a rule for reducing backtracking, even in instances where backtracking would result in shorter travel time; and

at least one processor configured to;

assign the plurality of users to a common ridesharing vehicle;

use the stored plurality of rules to determine a route for the ridesharing vehicle other than the fastest route, the determined route is selected to account for the rule for reducing backtracking and includes a plurality of pick-up and drop-off locations associated with the starting points and desired destinations of the plurality of users;

in order to reduce backtracking, direct the ridesharing vehicle along the determined route other than the fastest route; and

receive real time traffic data and calculate an expected travel-time change associated with users currently riding in the ridesharing vehicle when the ridesharing vehicle is directed along a route with backtracking as compared to a route with reduced backtracking.

2. The system of claim 1, wherein the at least one processor is configured to apply the rule for reducing backtracking by routing the ridesharing vehicle in a manner avoiding a trajectory opposite to an average direction of the plurality of users'"'"' desired destinations.

3. The system of claim 1, wherein the at least one processor is configured to apply the rule for reducing backtracking by routing the ridesharing vehicle in a manner avoiding three consecutive left turns.

4. The system of claim 1, wherein the at least one processor is configured to apply the rule for reducing backtracking by routing the ridesharing vehicle in a manner avoiding three consecutive right turns.

5. The system of claim 1, wherein the at least one processor is configured to apply the rule for reducing backtracking by routing the ridesharing vehicle in a manner reducing U-turns.

6. The system of claim 1, wherein the at least one processor is further configured to override the backtracking rule when the received traffic data is indicative of at least one of street blockages and atypical congestion.

7. The system of claim 1, wherein the at least one processor is further configured to override the backtracking rule in response to a received indication of imminent high demand for rides.

8. The system of claim 1, wherein the at least one processor is further configured to override the backtracking rule when an expected travel-time change is higher than a backtracking threshold.

9. The system of claim 8, wherein a value of the backtracking threshold is dynamic and is determined based on at least one of a time of day and a type of user currently riding the ridesharing vehicle.

10. The system of claim 1, wherein the expected travel-time change is calculated separately for each of the users currently riding the ridesharing vehicle.

11. The system of claim 1, wherein the expected travel-time change is calculated collectively for the users currently riding the ridesharing vehicle.

12. The system of claim 1, wherein the at least one processor is further configured to override the backtracking rule, determine an updated route along which to direct the ridesharing vehicle, and to change at least one drop-off location of the plurality of users after determining the updated route.

13. The system of claim 1, wherein the at least one processor is further configured to override the backtracking rule, determine an updated route along which to direct the ridesharing vehicle, and to reassign a user scheduled to be picked up by the ridesharing vehicle to another ridesharing vehicle.

14. The system of claim 1, wherein the memory is further configured to store additional rules for determining the route for the ridesharing vehicle.

15. The system of claim 1, wherein the at least one processor is further configured to receive at least one additional ride request from at least one additional user and change the determined route to pick-up at the least one additional user.

16. A non-transitory computer-readable storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to perform a method for managing a fleet of ridesharing vehicles, the method comprising:

receiving ride requests from a plurality of users, wherein each ride request includes a starting point and a desired destination;

receiving from a plurality of communication devices associated with a plurality of ridesharing vehicles, indications of current locations of the plurality of ridesharing vehicles;

accessing memory configured to store a plurality of rules including a rule to select a fastest route for guiding a ridesharing vehicle and a rule for reducing backtracking, even in instances where backtracking would result in shorter travel time;

assigning the plurality of users to a common ridesharing vehicle;

using the stored plurality of rules to determine a route for the ridesharing vehicle other than the fastest route, the determined route is selected to account for the rule for reducing backtracking and includes a plurality of pick-up and drop-off locations associated with the starting points and desired destinations of the plurality of users;

in order to reduce backtracking, directing the ridesharing vehicle along the determined route other than the fastest route; and

receiving real time traffic data and calculating an expected travel-time change associated with users currently riding in the ridesharing vehicle when the ridesharing vehicle is directed along a route with backtracking as compared to a route with reduced backtracking.

17. The non-transitory computer-readable storage medium according to claim 16, wherein the rule for reducing backtracking includes at least one of:

avoiding routes that include a trajectory away from a user'"'"'s desired destination, avoiding routes that include three consecutive left turns, avoiding routes that include three consecutive right turns, and avoiding routes that include U-turns.

18. The non-transitory computer-readable storage medium according to claim 16, wherein the method further comprises:

overriding the backtracking rule when the expected travel-time change for each of the users currently riding the ridesharing vehicle is higher than a backtracking threshold.

19. The non-transitory computer-readable storage medium according to claim 16, wherein the method further comprises:

receiving real time traffic data; and

overriding the backtracking rule when the received traffic data is indicative of atypical congestion.