On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment with future requests

Patent metadata

Field	Value
Publication number	US-11619951-B2
Application number	US-201815941449-A
Country	US
Kind code	B2
Filing date	Mar 30, 2018
Priority date	Jan 23, 2017
Publication date	Apr 4, 2023
Grant date	Apr 4, 2023

Abstract

Described is a method and system for vehicle routing and request assignment which incorporates a prediction of future demand. The method seamlessly integrates sampled future requests into request assignments and vehicle routing.

First claim

The invention claimed is:

1. A system for controlling and continuously rerouting a fleet of vehicles based up on real-time requests, the system comprising:
(a) means for receiving current requests for rides within a window and for receiving a prediction of future demand;
(b) means for generating a pairwise request-vehicle shareability graph (RV-graph) which takes into account the prediction of future demand, a current state of the fleet of vehicles, and the current requests for rides;
(c) means for generating a request-trip-vehicle graph (RTV-graph) of trips and one or more vehicles within the fleet of vehicles that can serve the trips which takes into account the prediction of future demand, wherein each of the trips corresponds to a group of one or more of the current requests for rides and has a trip size corresponding to a number of the current requests for rides, wherein generating the RT/Fadey S. Jabr/V-graph includes finding feasible trips incrementally in trip size for each vehicle using the RV-graph;
(d) means for solving an integer linear program (ILP) to determine an assignment of vehicles to trips while taking into account the prediction of future demand; and
(e) means for assigning specific vehicles from the fleet of vehicles to specific trips while taking into account the prediction of future demand.

2. The system of claim 1 further comprising means for determining a feasibility of trips in the RTV-graph.

3. The system of claim 1 further comprising means for rebalancing idle vehicles to areas with high demand.

4. The system of claim 1 wherein the fleet of vehicles is a fleet of autonomous vehicles.

5. The system of claim 1 , comprising: means for determining a probability distribution of origin-destination requests for fixed intervals of time, wherein the means for generating a pairwise request-vehicle shareability graph takes into account the prediction of future demand using the probability distribution.

6. The system of claim 5 , wherein using the probability distribution comprises sampling future requests from the probability distribution to anticipate demand.

7. The system of claim 1 , wherein finding the feasible trips incremental in trip size for a vehicle includes finding trips where all the corresponding current requests for rides can be picked up and dropped off by the vehicle while satisfying one or more constraints.

8. The system of claim 1 wherein: the fleet of vehicles comprises one or more autonomous vehicles; and the means for assigning specific vehicles from the fleet of vehicles to specific trips comprises: a communication network; and a mobility-on-demand (MoD) fleet controller configured to communicate with the one or more autonomous vehicles over the communication network to control the one or more autonomous vehicles.

Assignees

• Massachusetts Inst Technology

Inventors

• Alonso-Mora Javier
• Rus Daniela L
• Wallar Alexander J

Classifications

• G06N5/04

  Inference or reasoning models · CPC title

• G06Q10/06311 Primary

  Scheduling, planning or task assignment for a person or group · CPC title

• G08G1/202

  Dispatching vehicles on the basis of a location, e.g. taxi dispatching · CPC title

• G05D1/0291 Primary

  Fleet control (monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127) · CPC title

• G05D1/0088

  characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00) · CPC title