System and method for routing in a ride-share transportation network
A method includes storing representations of a passengers and fleet vehicles. The method includes generating a graph representation of a geographic map that includes requested pick-up locations and drop-off locations for the passengers and generating a state graph representation of the passengers and the fleet vehicles. The state graph representation includes a plurality of nodes connected by edges. Each of the plurality of nodes represents a candidate state of the passengers and the fleet vehicles. A respective edge of the state graph representation represents an action of a respective vehicle picking up or dropping off a passenger. The respective edge has a cost that is based at least in part on traversal of the graph representation of the geographic map. The method further includes using the state graph representation to generate a set of routes and route the fleet vehicles in accordance with the generated set of routes.
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;
storing representations of a plurality of fleet vehicles;
generating a graph representation of a geographic map that includes the requested pick-up locations and drop-off locations for the plurality of first passengers;
generating a state graph representation of the plurality of first passengers and the fleet vehicles, wherein:
the state graph representation of the plurality of first passengers and the fleet vehicles is different from the graph representation of the geographic map;
the state graph representation includes a plurality of nodes connected by edges;
each node of the plurality of nodes of the state graph representation represents a candidate state of the plurality of first passengers and the fleet vehicles;
a respective edge of the state graph representation represents an action of a respective vehicle picking up or dropping off a passenger, and
the respective edge has a respective cost that is based at least in part on traversal of the graph representation of the geographic map;
generating a set of routes for the fleet vehicles, including:
performing a graph search of the state graph representation by evaluating a cost model that includes the costs of the respective edges;
assigning each passenger of the plurality of first passengers to be picked up and dropped off by a respective vehicle of the fleet vehicles by selecting, based on the graph search, a subset of edges of the state graph representation, wherein the subset of edges is less than all edges; and
generating the set of routes based on the assignment of the plurality of first passengers to the respective vehicles of the fleet of vehicles; and
routing the fleet vehicles in accordance with the generated set of routes.
2. The method of claim 1 , wherein the fleet vehicles include 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 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 of the fleet vehicles 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 of the fleet vehicles 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 fleet vehicles.
7. The method of claim 1 , wherein generating the set of routes for the fleet vehicles includes:
assigning each passenger of the first plurality of passengers to one or more candidate pick-up locations based on the first passenger's requested pick-up location;
assigning each passenger of the first plurality of passengers to one or more candidate drop-off locations based on the first passenger's requested drop-off location;
clustering the first plurality of passengers according to their assigned candidate pick-up locations and drop-off locations;
assigning respective vehicles of the fleet vehicles to a plurality of clusters; and
parallelizing the routing of the fleet vehicles according the assigned plurality of clusters for the respective vehicles of the fleet vehicles.
8. The method of claim 7 , 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 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.
9. The method of claim 1 , wherein performing the graph search includes limiting a number of states explored in the state graph representation using a lowest-bound heuristic by forgoing subsequent exploration from any nodes in the state graph representation for which a lowest-bound of the cost function exceeds a cost of an already-determined set of routes for the fleet vehicles.
10. The method of claim 1 , wherein the cost model includes pick-up wait times for the first passengers.
11. The method of claim 1 , wherein the graph search is a bi-directional search.
12. 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;
storing representations of a plurality of fleet vehicles;
generating a graph representation of a geographic map that includes the requested pick-up locations and drop-off locations for the plurality of first passengers;
generating a state graph representation of the plurality of first passengers and the fleet vehicles, wherein:
the state graph representation of the plurality of first passengers and the fleet vehicles is different from the graph representation of the geographic map;
the state graph representation includes a plurality of nodes connected by edges;
each node of the plurality of nodes of the state graph representation represents a candidate state of the plurality of first passengers and the fleet vehicles;
a respective edge of the state graph representation represents an action of a respective vehicle picking up or dropping off a passenger, and
the respective edge has a respective cost that is based at least in part on traversal of the graph representation of the geographic map;
generating a set of routes for the fleet vehicles, including:
performing a graph search of the state graph representation by evaluating a cost model that includes the costs of the respective edges;
assigning each passenger of the plurality of first passengers to be picked up and dropped off by a respective vehicle of the fleet vehicles by selecting, based on the graph search, a subset of edges of the state graph representation, wherein the subset of edges is less than all edges; and
generating the set of routes based on the assignment of the plurality of first passengers to the respective vehicles of the fleet of vehicles; and
routing the fleet vehicles in accordance with the generated set of routes.
13. 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;
storing representations of a plurality of fleet vehicles;
generating a graph representation of a geographic map that includes the requested pick-up locations and drop-off locations for the plurality of first passengers;
generating a state graph representation of the plurality of first passengers and the fleet vehicles, wherein:
the state graph representation of the plurality of first passengers and the fleet vehicles is different from the graph representation of the geographic map;
the state graph representation includes a plurality of nodes connected by edges;
each node of the plurality of nodes of the state graph representation represents a candidate state of the plurality of first passengers and the fleet vehicles;
a respective edge of the state graph representation represents an action of a respective vehicle picking up or dropping off a passenger, and
the respective edge has a respective cost that is based at least in part on traversal of the graph representation of the geographic map;
generating a set of routes for the fleet vehicles, including:
performing a graph search of the state graph representation by evaluating a cost model that includes the costs of the respective edges;
assigning each passenger of the plurality of first passengers to be picked up and dropped off by a respective vehicle of the fleet vehicles by selecting, based on the graph search, a subset of edges of the state graph representation, wherein the subset of edges is less than all edges; and
generating the set of routes based on the assignment of the plurality of first passengers to the respective vehicles of the fleet of vehicles; and
routing the fleet vehicles in accordance with the generated set of routes.