Determining estimated delivery time of items obtained from a warehouse for users of an online concierge system to reduce probabilities of delivery after the estimated delivery time

Patent metadata

Field	Value
Publication number	US-11755987-B2
Application number	US-202117359486-A
Country	US
Kind code	B2
Filing date	Jun 25, 2021
Priority date	Jun 25, 2021
Publication date	Sep 12, 2023
Grant date	Sep 12, 2023

Abstract

An online concierge system displays an interface to a user identifying an estimated time of arrival for an order. To generate the estimated time of arrival for the order, the online concierge system trains a prediction engine to predict delivery time based on a predicted selection time for a shopper to select the order for fulfillment and predicted travel time for the shopper to deliver items of the order to a location identified by the order. The online concierge system generates a policy optimization model that computes an adjustment for the predicted delivery time. The adjustment is determined by solving a stochastic optimization problem with a constraint on a probability of the order being delivered after the estimated time of arrival. The predicted delivery time combined with the adjustment determines the estimated time of delivery displayed to the user to balance between minimizing late deliveries and wait times.

First claim

What is claimed is:

1. A method comprising:
receiving an order at an online concierge system from a user, the order including one or more items and identifying a location to which the one or more items are delivered, the order to be displayed to one or more shopper mobile applications for one or more shoppers to select whether to fulfill the order;
determining, by a first machine learning model, a predicted delivery time for the order, the predicted delivery time determined from the location identified by the order and historical rates at which shoppers decide to select orders within a geographic region that includes the location, the predicted delivery time including a predicted length of time that a particular shopper decides to accept the order for fulfillment;
determining a modification to the predicted delivery time by applying a second machine learning model to the predicted delivery time, the second machine learning model determining the modification to optimize a predicted time identified to the user for fulfillment of the order subject to a constraint that a probability of the order being fulfilled after a time identified by the online concierge system does not exceed a threshold probability, wherein training of the second machine learning model comprises:
setting a threshold probability of the order being fulfilled after the predicted delivery time determined by the first machine learning model,
subjecting the modification to a constraint that a probability of the order being fulfilled after the predicted delivery time determined by the first machine learning model does not exceed the threshold probability, and
solving a stochastic optimization problem with the constraint that involves the predicted delivery time determined by the first machine learning model;

generating a modified delivery time by combining the predicted delivery time and the modification;
generating an estimated time of arrival of the order to the user by combining the modified delivery time and a time when the online concierge system received the order; and
displaying the estimated time of arrival to the user in an interface in conjunction with information identifying the order.

2. The method of claim 1 , wherein the interface further displays an option for the user to select fulfillment of the order by the estimated time of arrival.

3. The method of claim 1 , wherein the predicted length of time that a particular shopper decides to accept the order for fulfillment is determined based on a rate at which the online concierge system receives orders including locations within the determined geographic region, a rate at which shoppers select orders including locations within the determined geographic region for fulfillment, and a number of orders including locations within the determined geographic region received by the online concierge system and not selected for fulfillment by shoppers.

4. The method of claim 3 , wherein the predicted length of time comprises an average selection time for the determined geographic region.

5. The method of claim 1 , wherein determining the predicted delivery time for the order further comprises:
identifying one or more characteristics of the order;
determining an adjustment for the predicted delivery time based on the one or more characteristics of the order; and
generating a delivery specific selection time for the order by combining the predicted delivery time and the adjustment.

6. The method of claim 5 , wherein the one or more characteristics of the order are selected from a group consisting of: a number of items in the order, a distance between a warehouse identified in the order and the location identified in the order, a value of the order, an amount of compensation the user provides a shopper for fulfilling the order, and any combination thereof.

7. The method of claim 5 , wherein generating the delivery specific selection time for the order by combining the predicted delivery time and the adjustment comprises:
determining a product of the adjustment and the predicted delivery time.

8. The method of claim 5 , wherein determining the predicted delivery time for the order further comprises:
determining a travel time for a shopper delivering items from a warehouse identified by the order to the location identified by the order based on characteristics of the order; and
determining the predicted delivery time as a combination of the travel time and the delivery specific selection time.

9. The method of claim 8 , wherein the characteristics of the order are selected from a group consisting of: a number of items in the order, a warehouse identified by the order, and a distance between the warehouse identified by the order and the location identified by the order.

10. The method of claim 1 , wherein the second machine learning model determines the modification as a function of the predicted delivery time so different predicted delivery times have different modifications.

11. A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:
receive an order at an online concierge system from a user, the order including one or more items and identifying a location to which the one or more items are delivered, the order to be displayed to one or more shopper mobile applications for one or more shoppers to select whether to fulfill the order;
determine, by a first machine learning model, a predicted delivery time for the order, the predicted delivery time determined from the location identified by the order and historical rates at which shoppers decide to select orders within a geographic region that includes the location, the predicted delivery time including a predicted length of time that a particular shopper decides to accept the order for fulfillment;
determine a modification to the predicted delivery time by applying a second machine learning model to the predicted delivery time, the second machine learning model determining the modification to optimize a predicted time identified to the user for fulfillment of the order subject to a constraint that a probability of the order being fulfilled after a time identified by the online concierge system does not exceed a threshold probability, wherein training of the second machine learning model comprises:
setting a threshold probability of the order being fulfilled after the predicted delivery time determined by the first machine learning model,
subjecting the modification to a constraint that a probability of the order being fulfilled after the predicted delivery time determined by the first machine learning model does not exceed the threshold probability, and
solving a stochastic optimization problem with the constraint that involves the predicted delivery time determined by the first machine learning model;

generate a modified delivery time by combining the predicted delivery time and the modification;
generate an estimated time of arrival of the order to the user by combining the modified delivery time and a time when the online concierge system received the order; and
display the estimated time of arrival to the user in an interface in conjunction with information identifying the order.

12. The computer program product of claim 11 , wherein the interface further displays an option for the user to select fulfillment of the order by the estimated time of arrival.

13. The computer program product of claim 11 , wherein the predicted length of time that a particular shopper decides to accept the order for fulfillment is determined based on a rate at which the

Assignees

• Maplebear Inc

Inventors

• Wang Zi
• Chen Ji
• Deng Houtao
• Zeliger Soren
• Chen Yijia

Classifications

• G06Q10/0833 Primary

  Tracking · CPC title

• G06Q10/087

  Inventory or stock management, e.g. order filling, procurement or balancing against orders · CPC title