Penalizing difficult immediate maneuvers in routing cost functions

Patent metadata

Field	Value
Publication number	US-2023103058-A1
Application number	US-202117487350-A
Country	US
Kind code	A1
Filing date	Sep 28, 2021
Priority date	Sep 28, 2021
Publication date	Mar 30, 2023
Grant date	—

Abstract

A transportation management system generates routing guidance from an origin location to a destination location by modifying edge weights in a graph of a geographic location to penalize difficult immediate maneuvers. Responsive to receiving a routing request, the system identifies a position of a provider device in a base map having edges representing road segments and nodes representing intersections between road segments. A sub-graph is generated for the edges in the base graph located up to a threshold distance from the origin location, and the system modifies the weight of one or more edges in the sub-graph corresponding to a difficult immediate maneuver. When applying a routing algorithm to generate the routing guidance, the system uses the edge weights of the generated sub-graph for a first portion of the routing guidance and the original edge weights of the base graph for a second portion of the routing guidance.

First claim

1 . A computer-implemented method for generating routing guidance for a vehicle, the method comprising:
receiving, at a transportation management system from a provider device associated with the vehicle, a request for routing guidance from an origin location to a destination location; identifying a position of the origin location within a base graph of a geographic area, the base graph including edges representing road segments in the geographic area and nodes representing intersections between the road segments, each edge having an associated edge weight; generating a sub-graph of a portion of the base graph from the origin location to a threshold distance from the origin location; modifying a weight of at least one edge in the sub-graph to a weight that is different from a weight of a corresponding edge in the base graph; and generating routing guidance from the origin location to the destination location using the modified edge weights of the sub-graph for the at least one edge and the edge weights of the base graph for remaining edges between the origin location and the destination location.

2 . The computer-implemented method of claim 1 , wherein before modifying a weight of at least one edge in the sub-graph, the method further comprises identifying, within the sub-graph, one or more edges for which to modify the weight of the corresponding edge in the base graph, the identified one or more edges corresponding to a maneuver from a first edge to a second edge.

3 . The computer-implemented method of claim 2 , wherein the maneuver comprises a maneuver occurring within a threshold distance or travel time from the origin location.

4 . The computer-implemented method of claim 2 , further comprising modifying the weight of the one or more identified edges by applying a multiplier to the weight of the corresponding edge in the base graph.

5 . The computer-implemented method of claim 4 , wherein the multiplier is a constant multiplier.

6 . The computer-implemented method of claim 4 , wherein the multiplier is a variable multiplier and wherein a maneuver occurring at a first distance from the origin location has a higher edge weight than a maneuver occurring at a second distance from the origin location.

7 . The computer-implemented method of claim 4 , wherein the multiplier is a variable multiplier and wherein a first type of maneuver has a higher edge weight than a second type of maneuver.

8 . The computer-implemented method of claim 1 , wherein the origin location is a pickup location for a transportation service provided by the vehicle to a destination location.

9 . The computer-implemented method of claim 1 , wherein generating the routing guidance from the origin location to the destination location comprises:
for a first portion of the routing guidance from the origin location to a radius of the sub-graph, applying a routing algorithm to the modified edge weights of the sub-graph; and for a second portion of the routing guidance from the radius of the sub-graph to the destination location, applying the routing algorithm to edge weights of the base graph.

10 . The computer-implemented method of claim 1 , wherein the edges in the sub-graph are temporary copies of the edges in the base graph and wherein the transportation management system generates a new sub-graph for each routing request based on an origin location for a corresponding routing request.

11 . A non-transitory computer-readable storage medium storing computer-executable instructions that, in response to executing, cause a device comprising a processor to perform operations comprising:
receiving, at a transportation management system from a provider device associated with the vehicle, a request for routing guidance from an origin location to a destination location; identifying a position of the origin location within a base graph of a geographic area, the base graph including edges representing road segments in the geographic area and nodes representing intersections between the road segments, each edge having an associated edge weight; generating a sub-graph of a portion of the base graph from the origin location to a threshold distance from the origin location; modifying a weight of at least one edge in the sub-graph to a weight that is different from a weight of a corresponding edge in the base graph; and generating routing guidance from the origin location to the destination location using the modified edge weights of the sub-graph for the at least one edge and the edge weights of the base graph for remaining edges between the origin location and the destination location.

12 . The non-transitory computer-readable storage medium of claim 11 , wherein before modifying a weight of at least one edge in the sub-graph, the method further comprises, identifying, within the sub-graph, one or more edges for which to modify the weight of the corresponding edge in the base graph, the identified one or more edges corresponding to a maneuver from a first edge to a second edge.

13 . The non-transitory computer-readable storage medium of claim 12 , wherein the maneuver comprises a maneuver occurring within a threshold distance or travel time from the origin location.

14 . The non-transitory computer-readable storage medium of claim 12 , wherein the operations further comprise modifying the weight of the one or more identified edges by applying a multiplier to the weight of the corresponding edge in the base graph.

15 . The non-transitory computer-readable storage medium of claim 14 , wherein the multiplier is a constant multiplier.

16 . The non-transitory computer-readable storage medium of claim 14 , wherein the multiplier is a variable multiplier and wherein a maneuver occurring at a first distance from the origin location has a higher edge weight than a maneuver occurring at a second distance from the origin location.

17 . The non-transitory computer-readable storage medium of claim 14 , wherein the multiplier is a variable multiplier and wherein a first type of maneuver has a higher edge weight than a second type of maneuver.

18 . The non-transitory computer-readable storage medium of claim 11 , wherein the origin location is a pickup location for a transportation service provided by the vehicle to a destination location.

19 . The non-transitory computer-readable storage medium of claim 11 , wherein generating the routing guidance comprises:
for a first portion of the routing guidance from the origin location to a radius of the sub-graph, applying a routing algorithm to the modified edge weights of the sub-graph; and for a second portion of the routing guidance from the radius of the sub-graph to the destination location, applying the routing algorithm to edge weights of the base graph.

20 . The non-transitory computer-readable storage medium of claim 11 , wherein the edges in the sub-graph are temporary copies of the edges in the base graph and wherein the transportation management system generates a new sub-graph for each routing request based on an origin location for a corresponding routing request.

Assignees

• Uber Technologies Inc

Inventors

• Berk Rifat
• Barker Joseph Kelly
• Agrawal Pranav Deepak
• Khosla Vineet
• Mohan Nishanth

Classifications

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G06Q10/02

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

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G06Q10/0283

  for travel seating · CPC title

• G01C21/3461 Primary

  Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries · CPC title