Systems and methods for routing a fleet of vehicles
A method includes of routing an autonomous vehicle includes receiving information obtained from a camera on a second vehicle distinct from the autonomous vehicle. The method includes automatically identifying a road condition using image analysis of the information received from the camera on the second vehicle. The method includes receiving a request to route the autonomous vehicle from a first location to a second location; and in response to the request: generating a cost model for routing the autonomous vehicle, wherein the cost model includes a cost of the road condition automatically identified from the information received from the camera on the second vehicle; selecting a route from the first location to the second location in accordance with the cost model; and routing an autonomous vehicle in accordance with the selected route.
1. A routing method for a ride-share transportation network, comprising:
storing representations of a plurality of first passengers, wherein each of the representations of the plurality of first passengers includes a requested pick-up location and a requested drop-off location for a respective first passenger of the plurality of first passengers;
generating a set of routes for a plurality of fleet vehicles, including:
assigning each respective first passenger of the plurality of first passengers to:
a pick-up location based on the respective first passenger's requested pick-up location; and
a drop-off location based on the respective first passenger's requested drop-off location; and
clustering the pick-up locations and the drop-off locations for the plurality of first passengers into a plurality of clusters;
after clustering the pick-up locations and the drop-off locations, assigning each respective vehicle of the plurality of fleet vehicles to a pair of the plurality of clusters; and
parallelizing the routing of the plurality of fleet vehicles according the assigned pairs of the plurality of clusters for the respective vehicles of the plurality of fleet vehicles, including independently generating a route for each respective vehicle of the plurality of fleet vehicles using the assigned pair of the plurality of clusters; and
routing the plurality of fleet vehicles in accordance with the generated set of routes.
2. The method of claim 1 , wherein the plurality of fleet vehicles includes a plurality of autonomous vehicles.
3. The method of claim 1 , wherein the plurality of fleet vehicles is operated by a single operator.
4. The method of claim 1 , including,
receiving a ride request from a second passenger, distinct from the plurality of first passengers, wherein the request includes a requested pick-up location and a requested drop-off location for the second passenger; and
updating the route for a respective vehicle of the plurality of fleet vehicles, including assigning the second passenger to be picked up and dropped off by the respective vehicle, in accordance with one or more least-expensive-insertion criteria.
5. The method of claim 4 , wherein updating the route for the respective vehicle includes inserting a pick-up location and a drop-off location for the second passenger into an existing route for the respective vehicle without modifying pick-up and drop-off locations for passengers already assigned to the respective vehicle.
6. The method of claim 4 , wherein updating the route for the respective vehicle includes:
inserting a pick-up location and a drop-off location for the second passenger into an existing route for the respective vehicle; and
reassigning a passenger already assigned to the respective vehicle to a different vehicle of the plurality of fleet vehicles.
7. The method of claim 1 , including:
receiving a ride request from a second passenger, distinct from the plurality of first passengers, wherein the request includes a requested pick-up location and a requested drop-off location for the second passenger; and
updating the route for a respective vehicle of the plurality of fleet vehicles, including assigning the second passenger to be picked up and dropped off by the respective vehicle, by:
assigning the second passenger to an existing cluster; and
updating the route for the vehicle assigned to the existing cluster.
8. A computer system, comprising:
one or more processors; and
memory storing one or more programs, the one or more programs storing instructions that, when executed by the one or more processors, cause the computer system to perform a set of operations, including:
storing representations of a plurality of first passengers, wherein each of the representations of the plurality of first passengers includes a requested pick-up location and a requested drop-off location for a respective first passenger of the plurality of first passengers;
generating a set of routes for a plurality of fleet vehicles, including:
assigning each respective first passenger of the plurality of first passengers to:
a pick-up location based on the respective first passenger's requested pick-up location; and
a drop-off location based on the respective first passenger's requested drop-off location; and
clustering the pick-up locations and the drop-off locations for the plurality of first passengers into a plurality of clusters;
after clustering the pick-up locations and the drop-off locations, assigning each respective vehicle of the plurality of fleet vehicles to a pair of the plurality of clusters; and
parallelizing the routing of the plurality of fleet vehicles according the assigned pairs of the plurality of clusters for the respective vehicles of the plurality of fleet vehicles, including independently generating a route for each respective vehicle of the plurality of fleet vehicles using the assigned pair of the plurality of clusters; and
routing the plurality of fleet vehicles in accordance with the generated set of routes.
9. A non-transitory computer readable storage medium storing instructions that, when executed by a computer system having one or more processors, cause the computer system to perform a set of operations, including:
storing representations of a plurality of first passengers, wherein each of the representations of the plurality of first passengers includes a requested pick-up location and a requested drop-off location for a respective first passenger of the plurality of first passengers;
generating a set of routes for a plurality of fleet vehicles, including:
assigning each respective first passenger of the plurality of first passengers to:
a pick-up location based on the respective first passenger's requested pick-up location; and
a drop-off location based on the respective first passenger's requested drop-off location; and
clustering the pick-up locations and the drop-off locations for the plurality of first passengers into a plurality of clusters;
after clustering the pick-up locations and the drop-off locations, assigning each respective vehicle of the plurality of fleet vehicles to a pair of the plurality of clusters; and
parallelizing the routing of the plurality of fleet vehicles according the assigned pairs of the plurality of clusters for the respective vehicles of the plurality of fleet vehicles, including independently generating a route for each respective vehicle of the plurality of fleet vehicles using the assigned pair of the plurality of clusters; and
routing the plurality of fleet vehicles in accordance with the generated set of routes.
10. The method of claim 1 , wherein clustering the pick-up locations and the drop-off locations for the plurality of first passengers into the plurality of clusters includes minimizing the maximum distance between any two stops in a cluster.
11. The method of claim 1 , wherein the clustering is spatio-temporal clustering.
12. The method of claim 1 , wherein clustering the pick-up locations and the drop-off locations for the plurality of first passengers into the plurality of clusters includes selecting a predefined number of clusters based on a target latency for the clustering.
13. The computer system of claim 8 , wherein the plurality of fleet vehicles includes a plurality of autonomous vehicles.
14. The computer system of claim 8 , wherein the plurality of fleet vehicles is operated by a single operator.
15. The computer system of claim 8 , wherein the set of operations further includes,
receiving a ride request from a second passenger, distinct from the plurality of first passengers, wherein the request includes a requested pick-up location and a requested drop-off location for the second passenger; and
updating the route for a respective vehicle of the plurality of fleet vehicles, including assigning the second passenger to be picked up and dropped off by the respective vehicle, in accordance with one or more least-expensive-insertion criteria.
16. The computer system of claim 15 , wherein updating the route for the respective vehicle includes inserting a pick-up location and a drop-off location for the second passenger into an existing route for the respective vehicle without modifying pick-up and drop-off locations for passengers already assigned to the respective vehicle.
17. The computer system of claim 15 , wherein updating the route for the respective vehicle includes:
inserting a pick-up location and a drop-off location for the second passenger into an existing route for the respective vehicle; and
reassigning a passenger already assigned to the respective vehicle to a different vehicle of the plurality of fleet vehicles.
18. The computer system of claim 8 , wherein the set of operations further includes:
receiving a ride request from a second passenger, distinct from the plurality of first passengers, wherein the request includes a requested pick-up location and a requested drop-off location for the second passenger; and
updating the route for a respective vehicle of the plurality of fleet vehicles, including assigning the second passenger to be picked up and dropped off by the respective vehicle, by:
assigning the second passenger to an existing cluster; and
updating the route for the vehicle assigned to the existing cluster.
19. The computer system of claim 8 , wherein clustering the pick-up locations and the drop-off locations for the plurality of first passengers into the plurality of clusters includes minimizing the maximum distance between any two stops in a cluster.
20. The computer system of claim 8 , wherein the clustering is spatio-temporal clustering.
21. The computer system of claim 8 , wherein clustering the pick-up locations and the drop-off locations for the plurality of first passengers into the plurality of clusters includes selecting a predefined number of clusters based on a target latency for the clustering.