Penalizing difficult immediate maneuvers in routing cost functions
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.
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 a 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 operations further comprise, 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.