System and method for ride order dispatching

Abstract

A method for ride order dispatching comprises: obtaining a current location of a current vehicle from a computing device associated with the current vehicle; obtaining a current list of available orders nearby based on the current location; feeding the current location, the current list of available orders nearby, and a current time to a trained Markov Decision Process (MDP) model to obtain action information, the action information being repositioning the current vehicle to another current location or completing a current ride order by the current vehicle; and transmitting the generated action information to the computing device to cause the current vehicle to reposition to the another current location, stay at the current location, or accept the current ride order by proceeding to a pick-up location of the current ride order.

1 .- 20 . (canceled) 
     
     
         21 . A computer-implemented method for ride order dispatching, comprising:
 obtaining a current location of a current vehicle from a computing device associated with the current vehicle;   obtaining a current list of available orders based on the current location;   feeding the current location, the current list of available orders or a number of available orders in the current list, and a current time to a solved Markov Decision Process (MDP) model to obtain action information, the action information comprising: staying at the current location, repositioning the current vehicle to another current location, or completing a current ride order by the current vehicle; and   transmitting the action information to the computing device associated with the current vehicle, wherein the current vehicle is configured to stay or relocate based on the action information, wherein:
 the MDP model is solved based on a plurality of historical or simulated vehicle trips under a policy of maximizing a cumulative reward for a hypothetical vehicle completing the historical or simulated vehicle trips. 
   
     
     
         22 . The method of  claim 21 , further comprising solving the MDP model,
 wherein the solving comprising discretizing an activity area of the hypothetical vehicle into repeating zones and a time period into time slots.   
     
     
         23 . The method of  claim 22 , wherein:
 each state of the MDP model comprises:
 a time represented by a time slot index, 
 a location represented by a repeating zone index, and 
 a list of available orders represented by repeating zone indices of destinations of the available orders, and 
   each action of the MDP model comprises: completing one of the available orders from the list, repositioning to another location, or staying at the location.   
     
     
         24 . The method of  claim 23 , wherein the solving further comprises:
 if the hypothetical vehicle completes one of the available orders from the list, assigning the hypothetical vehicle a reward for completing the one available order, and updating the state of the MDP model with: a next time slot corresponding to completion of the one available order, a next location corresponding a destination of the one available order, and a next list of available orders corresponding the next location,   if the hypothetical vehicle repositions to the another location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: a next time corresponding to reaching the another location, the another location, and a next list of available orders corresponding the another location, and   if the hypothetical vehicle stays at the location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: the time slot, the location, and the list of available orders.   
     
     
         25 . The method of  claim 22 , wherein:
 each state of the MDP model comprises:
 a time represented by a time slot index, 
 a location represented by a repeating zone index, and 
 an integer representing the number of available orders, and 
   each action of the MDP model comprises: completing one of the available orders from the list, repositioning to another location, or staying at the location.   
     
     
         26 . The method of  claim 25 , wherein the solving further comprises:
 if the hypothetical vehicle completes one of the available orders from the list, assigning the hypothetical vehicle a reward for completing the one available order, and updating the state of the MDP model with: a next time slot corresponding to a completion of the one available order, a next location corresponding a destination of the one available order, and a next integer representing a quantity of available orders corresponding the next location,   if the hypothetical vehicle repositions to the another location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: a next time corresponding to reaching the another location, the another location, and another integer representing a quantity of available orders corresponding the another location, and   if the hypothetical vehicle stays at the location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: the time slot, the location, and the integer.   
     
     
         27 . The method of  claim 26 , wherein:
 the MDP model is solved by solving a stochastic formulation;   for solving the stochastic formulation, the location and pick-up locations of the available orders are in a same repeating zone; and   for application of the solved MDP model, a current location of a current vehicle and a pick-up location of the current ride order are within a same repeating zone.   
     
     
         28 . The method of  claim 27 , wherein:
 for solving the stochastic formula, all orders with pick-up locations in a repeating zone corresponding to the location are divided averagely and randomly among all vehicles in the repeating zone corresponding to the location to obtain the number of available orders nearby for the hypothetical vehicle; and   for application of the solved MDP model, all current orders with pick-up locations in a repeating zone corresponding to the current location are divided averagely and randomly among all current vehicles in the repeating zone corresponding to the current location to obtain the current number of available orders for the current vehicle.   
     
     
         29 . The method of  claim 27 , wherein:
 for solving the stochastic formula, the number of available orders for the hypothetical vehicle is a ceiling function of a division of the all orders with pick-up locations in the repeating zone corresponding to the location by the all vehicles in the repeating zone corresponding to the location; and   for application of the solved MDP model, the current number of available orders for the current vehicle is a ceiling function of a division of the all current orders with pick-up locations in the repeating zone corresponding to the current location by the all current vehicles in the repeating zone corresponding to the current location to obtain.   
     
     
         30 . The method of  claim 26 , wherein the MDP model is solved by applying acceleration and variance reduction algorithms to tabular implementation. 
     
     
         31 . The method of  claim 26 , further comprising solving the MDP model based on the plurality of historical or simulated vehicle trips, wherein the solving comprises:
 obtaining data for each of the historical vehicle trips, the data comprising: a historical pick-up time, a historical pick-up location, a historical drop-off time, and a historical drop-off location;   training a random forest classifier with the historical pick-up time, the historical drop-off time, and the historical drop-off location as training data and within the historical drop-off time minus the historical pick-up time as label to build a cruise time estimator, wherein: the cruise time estimator estimates a time to reach a destination based on the time, the location, and the destination of the one available order, or based on the time, the location, and the another location; and   applying the cruise time estimator in each state transition to determine the next time corresponding to a completion of the one available order nearby or to determine the next time corresponding to reaching the another location.   
     
     
         32 . The method of  claim 24 , wherein:
 the MDP model is solved by training an untrained MDP model;   for training the MDP model, all orders with pick-up locations in a repeating zone corresponding to the location are divided averagely and randomly among all vehicles in the repeating zone corresponding to the location to obtain the list of available orders for the hypothetical vehicle; and   for application of the trained MDP model, all current orders with pick-up locations in a repeating zone corresponding to the current location are divided averagely and randomly among all current vehicles in the repeating zone corresponding to the current location to obtain the current list of available orders for the current vehicle.   
     
     
         33 . The method of  claim 32 , wherein:
 for training the MDP model, the list of available orders for the hypothetical vehicle is a ceiling function of a division of the all orders with pick-up locations in the repeating zone corresponding to the location by the all vehicles in the repeating zone corresponding to the location; and   for application of the solved MDP model, the current list of available orders for the current vehicle is a ceiling function of a division of the all current orders with pick-up locations in the repeating zone corresponding to the current location by the all current vehicles in the repeating zone corresponding to the current location to obtain.   
     
     
         34 . A system comprising a processor and a non-transitory computer-readable storage medium storing instructions that, when executed by the processor, cause the system to perform operations comprising:
 obtaining a current location of a current vehicle from a computing device associated with the current vehicle;   obtaining a current list of available orders based on the current location;   feeding the current location, the current list of available orders or a number of available orders in the current list, and a current time to a solved Markov Decision Process (MDP) model to obtain action information, the action information comprising: staying at the current location, repositioning the current vehicle to another current location, or completing a current ride order by the current vehicle; and   transmitting the action information to the computing device associated with the current vehicle, wherein the current vehicle is configured to stay or relocate based on the action information, wherein:
 the MDP model is solved based on a plurality of historical or simulated vehicle trips under a policy of maximizing a cumulative reward for a hypothetical vehicle completing the historical or simulated vehicle trips. 
   
     
     
         35 . The system of  claim 34 , wherein the operations further comprise:
 solving the MDP model, wherein the solving comprising discretizing an activity area of the hypothetical vehicle into repeating zones and a time period into time slots.   
     
     
         36 . The system of  claim 35 , wherein:
 each state of the MDP model comprises:
 a time represented by a time slot index, 
 a location represented by a repeating zone index, and 
 a list of available orders represented by repeating zone indices of destinations of the available orders, and 
   each action of the MDP model comprises: completing one of the available orders from the list, repositioning to another location, or staying at the location.   
     
     
         37 . The system of  claim 36 , wherein the solving further comprises:
 if the hypothetical vehicle completes one of the available orders from the list, assigning the hypothetical vehicle a reward for completing the one available order, and updating the state of the MDP model with: a next time slot corresponding to a completion of the one available order, a next location corresponding a destination of the one available order, and a next list of available orders corresponding the next location,   if the hypothetical vehicle repositions to the another location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: a next time corresponding to reaching the another location, the another location, and a next list of available orders corresponding the another location, and   if the hypothetical vehicle stays at the location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: the time slot, the location, and the list of available orders.   
     
     
         38 . The system of  claim 35 , wherein:
 each state of the MDP model comprises:
 a time represented by a time slot index, 
 a location represented by a repeating zone index, and 
 an integer representing the number of available orders, and 
   each action of the MDP model comprises: completing one of the available orders from the list, repositioning to another location, or staying at the location.   
     
     
         39 . The system of  claim 38 , wherein the solving further comprises:
 if the hypothetical vehicle completes one of the available orders from the list, assigning the hypothetical vehicle a reward for completing the one available order, and updating the state of the MDP model with: a next time slot corresponding to a completion of the one available order, a next location corresponding a destination of the one available order, and a next integer representing a quantity of available orders corresponding the next location,   if the hypothetical vehicle repositions to the another location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: a next time corresponding to reaching the another location, the another location, and another integer representing a quantity of available orders corresponding the another location, and   if the hypothetical vehicle stays at the location, skipping assigning the hypothetical vehicle the reward, and updating the state of the MDP model with: the time slot, the location, and the integer.   
     
     
         40 . Non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
 obtaining a current location of a current vehicle from a computing device associated with the current vehicle;   obtaining a current list of available orders based on the current location;   feeding the current location, the current list of available orders or a number of available orders in the current list, and a current time to a solved Markov Decision Process (MDP) model to obtain action information, the action information comprising: staying at the current location, repositioning the current vehicle to another current location, or completing a current ride order by the current vehicle; and   transmitting the action information to the computing device associated with the current vehicle, wherein the current vehicle is configured to stay or relocate based on the action information, wherein:
 the MDP model is solved based on a plurality of historical or simulated vehicle trips under a policy of maximizing a cumulative reward for a hypothetical vehicle completing the historical or simulated vehicle trips.