Dynamically determining origin and destination locations for a network system

Patent metadata

Field	Value
Publication number	US-2019033084-A1
Application number	US-201715662407-A
Country	US
Kind code	A1
Filing date	Jul 28, 2017
Priority date	Jul 28, 2017
Publication date	Jan 31, 2019
Grant date	—

Abstract

A network system dynamically determines a route, including start and end points, for vehicles in a transportation network. The transportation network receives a service request from a user of the transportation network including an origin location for the trip and a destination location for the trip. The transportation network then generates a waypoint plan for one or more vehicles, which includes the requested origin and destination in addition to any previously requested origins and destinations included in the vehicles current route. The network system then determines a directionality for each of the waypoints in the waypoint plan and retrieves candidate start and end points that have an associated directionality within a threshold angle of the directionality of each waypoint and are proximate to the waypoint. The network system evaluates each combination of retrieved candidate points to select a route for the vehicle.

First claim

We claim:

1 . A computer-implemented method for selecting a route for a vehicle communicating with a network system, the method comprising:
receiving, by the network system, a service request for a user, the service request including a requested origin location and a requested destination location; generating, for an active vehicle traversing an active route and having one or more previously assigned waypoints, waypoint plans, each waypoint plan indicating an order of locations to be traversed by the active vehicle, wherein waypoints in each waypoint plan include the requested origin location, the requested destination location, and the previously assigned waypoints; for each waypoint plan:
determining a directionality component for each waypoint, wherein the directionality component of a waypoint is based on the location of a subsequent waypoint in the waypoint plan;
retrieving associated candidate points for each waypoint, wherein each candidate point is proximate to the waypoint and has a directionality within a directionality threshold associated with the directionality component of the waypoint;
generating candidate point combinations, each candidate point combination having one candidate point associated with each waypoint in the waypoint plan;
determining a route and associated route duration for each candidate point combination, wherein the route includes a walking route between each candidate point and the associated waypoint, and wherein the route passes through each candidate point in the candidate point combination in an order specified by the waypoint plan;
selecting a route, of the determined routes, for the active vehicle by evaluating the determined routes for each waypoint plan of the active vehicle, based on characteristics of the routes and the associated route durations of the routes; and transmitting, by the network system, the selected route to the active vehicle.

2 . The method of claim 1 , wherein generating, for the active vehicle, waypoint plans further comprises:
generating waypoint plans, wherein at least one origin location and destination location pair is interrupted by other waypoints and wherein an origin location and destination location pair are not placed consecutively at a beginning or end of the waypoint plan.

3 . The method of claim 1 , further comprising:
applying a haversine distance filter to the generated waypoint plans to create a set of filtered waypoint plans, wherein the haversine distance filter compares a sum of haversine distances between the waypoints in a waypoint plan in an order specified by the waypoint plan to a sum of haversine distances of individual trips within the waypoint plan.

4 . The method of claim 3 , wherein applying the haversine distance filter further comprises:
identifying origin location and destination location pairs in a waypoint plan, wherein each origin location and destination location pair is associated with a different service request; calculating an individual sum of haversine distances between each identified origin location and destination location pair; calculating a plan sum of haversine distances between waypoints in each waypoint plan in an order specified by the waypoint plan; calculating a plan ratio for each waypoint plan by dividing the plan sum for each plan by the individual sum; and for each waypoint plan, responsive to determining that the calculated plan ratio for the waypoint plan exceeds a predetermined threshold ratio, excluding that waypoint plan from the filtered waypoint plans.

5 . The method of claim 1 , wherein determining a directionality component for each waypoint further comprises:
responsive to determining that a waypoint is not last in the waypoint plan:
calculating a heading angle between the waypoint and the subsequent waypoint in the waypoint plan; and
setting the directionality component of the waypoint equal to the calculated heading angle.

6 . The method of claim 1 , wherein candidate points are locations corresponding to potential start and end locations to be included in a route, and wherein each candidate point is associated with a corner of an intersection of at least two roads.

7 . The method of claim 1 , wherein candidate points are locations corresponding to potential start and end locations to be included in a route, and wherein each candidate point is associated with an intersection of at least two roads.

8 . The method of claim 7 , further comprising, pruning the determined routes for each candidate point combination based on characteristics of the determined routes including the duration of each of the determined routes to create a pruned set of routes for the active vehicle.

9 . The method of claim 8 , further comprising, for each of the pruned set of routes:
retrieving a second set of candidate points, wherein the second set of candidate points are associated with a corner of an intersection associated with one of the previously retrieved candidate points; generating a second set of candidate point combinations, each candidate point combination including candidate points from the second set of candidate points for each waypoint in the waypoint plan; and determining a route and associated route duration for each of the second set of candidate point combinations, wherein the route includes a walking route between each candidate point and the waypoint, and wherein the route passes through each candidate point in the candidate point combination.

10 . The method of claim 1 , further comprising:
determining a fare for each of the determined routes; and selecting a route corresponding to each potential vehicle by evaluating the determined routes for each waypoint plan of the potential vehicle, based on characteristics of the routes, the associated route durations of the routes, and the determined fare for each of the routes.

11 . The method of claim 1 , further comprising:
periodically retrieving route information and vehicle information for the active and the selected route; reevaluating the selected route for the active vehicle by: retrieving a second set of candidate points for a waypoint plan including the waypoints remaining in the selected route; generating candidate point combinations for a reevaluated route using the retrieved second set of candidate points, each candidate point combination having one candidate point for each waypoint in the waypoint plan; determining a route and associated route duration for each of the candidate point combinations for a reevaluated route, wherein the route includes a walking route between each candidate point and an associated waypoint and wherein the route passes through each candidate point in the candidate point combination in the order specified by the waypoint plan; selecting a reevaluated route by evaluating the determined routes for the reevaluated route based on charactersitics of the routes and the associated route durations of the routes; and transmitting the reevaluated route to the active vehicle.

12 . A computer program product for selecting a route for a vehicle communicating with a network system, the computer program product stored on a non-transitory computer readable medium and including instructions configured to cause one or more processors to execute steps comprising:
receiving a service request for a user, the service request including a requested origin location and a requested destination location; generating, for an active vehicle traversing an active route and having one or more previously assigned way points, waypoint plans, each waypoint plan indicating an order of locations to be traversed by the active vehicle, wherein wa

Assignees

• Uber Technologies Inc

Inventors

• Chen Qi
• Lawler Casey
• Shi Linfeng
• Xu Qing
• Yu Miao

Classifications

• G06Q10/02

  Reservations, e.g. for tickets, services or events · CPC title

• G06Q10/06315

  Needs-based resource requirements planning or analysis · CPC title

• G01C21/362

  received from an external device or application, e.g. PDA, mobile phone or calendar application · CPC title

• G01C21/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 title

• G01C21/3438 Primary

  Rendezvous; Ride sharing · CPC title