Machine learning model for determining a time interval to delay batching decision for an order received by an online concierge system to combine orders while minimizing probability of late fulfillment

Patent metadata

Field	Value
Publication number	US-12373880-B2
Application number	US-202318528738-A
Country	US
Kind code	B2
Filing date	Dec 4, 2023
Priority date	Feb 2, 2022
Publication date	Jul 29, 2025
Grant date	Jul 29, 2025

Abstract

An online concierge identifies orders to shoppers, allowing shoppers to select orders for fulfillment. The online concierge system may generate batches that include multiple orders, allowing a shopper to select a batch to fulfill multiple orders. As orders are continuously being received, delaying identification of orders to shoppers may allow greater batching of orders. To allow greater opportunities for batching, the online concierge system estimates a benefit for delaying identification of an order by different time intervals and predicts an amount of time to fulfill the order. The online concierge system then delays assigning orders for which there is a threshold benefit for delaying and selects a time interval for delaying identification of the order that does not result in greater than a threshold likelihood of a late fulfillment of the order.

First claim

What is claimed is:

1. A method comprising:
at an online system comprising one or more processors:
receiving an order at the online system;
determining a predicted benefit for delaying display of the order for fulfillment, wherein determining the predicted benefit comprises applying a machine learning model that outputs the predicted benefit from delaying identification of an order for fulfillment, wherein the machine learning model is trained by:
applying the machine learning model to training samples, each training sample including a time interval for delaying a historical order, one or more information describing the historical order, and a benefit label applied to each training sample identifying a benefit to the online system from delaying identification of the historical order;
backpropagating one or more error terms obtained from one or more loss functions associated with the machine learning model to update a set of parameters of the machine learning model, the backpropagating comprising updating one or more of the error terms based on a difference between the benefit label applied to a training sample and a predicted benefit generated by the machine learning model; and
stopping the backpropagation after the one or more loss functions satisfy one or more criteria;

selecting, based on the predicted benefit, a time interval for delaying display of the order for fulfillment;
evaluating one or more additional orders for inclusion of the one or more additional orders in a batch of orders that includes the order that is delayed for display for fulfillment; and
generating the batch of orders for fulfillment.

2. The method of claim 1 , further comprising displaying the batch of orders at the time interval, the batch of orders comprising the order and an additional order received after the order.

3. The method of claim 1 , wherein the predicted benefit for delaying display of the order for fulfillment comprises a probability of the order being fulfilled after a threshold interval.

4. The method of claim 1 , wherein the predicted benefit for delaying display of the order for fulfillment comprises an amount of time saved for fulfilling the order.

5. The method of claim 1 , wherein the time interval for delaying display of the order for fulfillment is selected based at least on an amount of time saved for fulfilling the order equaling or exceeding a threshold.

6. The method of claim 1 , wherein selecting the time interval for delaying display of the order for fulfillment comprises:
determining a predicted amount of time to fulfill the order from characteristics of the order;
for each of a set of candidate time intervals:
determining an overall fulfillment time for the order as a combination of the predicted amount of time to fulfill the order and the candidate time interval, and
determining a probability of the order being fulfilled later than a time identified by the order when the order is delayed from display by the candidate time interval from the overall fulfillment time; and

selecting a candidate time interval of the set based on the probabilities.

7. The method of claim 6 , wherein selecting the time interval of the set based on the probabilities comprises:
selecting a time interval having a minimum determined probability.

8. The method of claim 6 , wherein determining the predicted amount of time to fulfill the order from characteristics of the order comprises:
applying a machine learning model to characteristics of the order to generate the predicted amount of time.

9. The method of claim 8 , further comprising training the machine learning model, wherein training the machine learning model comprises:
obtaining training data including a plurality of training samples, each training sample including information describing a fulfilled order and having a label applied specifying a length of time from the online system receiving a previously fulfilled order and the online system receiving an indication that the fulfilled order was fulfilled;
backpropagating one or more error terms obtained from one or more loss functions to update a set of parameters of the fulfillment model, the backpropagating performed through a network comprising the fulfillment model and one or more of the error terms based on a difference between a label applied to a training sample of the training data and a predicted amount of time to fulfill an order corresponding to the training sample of the training data; and
stopping the backpropagation after the one or more loss functions satisfy one or more criteria.

10. An online system comprising:
one or more processors; and
memory configured to store code comprising instructions, the instructions, when executed by the one or more processors, cause the one or more processors to:
receive an order at the online system;
determine a predicted benefit for delaying display of the order for fulfillment, wherein determining the predicted benefit comprises applying a machine learning model that outputs the predicted benefit from delaying identification of an order for fulfillment, wherein the machine learning model is trained by:
applying the machine learning model to training samples, each training sample including a time interval for delaying a historical order, one or more information describing the historical order, and a benefit label applied to each training sample identifying a benefit to the online system from delaying identification of the historical order;
backpropagating one or more error terms obtained from one or more loss functions associated with the machine learning model to update a set of parameters of the machine learning model, the backpropagating comprising updating one or more of the error terms based on a difference between the benefit label applied to a training sample and a predicted benefit generated by the machine learning model; and
stopping the backpropagation after the one or more loss functions satisfy one or more criteria;

select, based on the predicted benefit, a time interval for delaying display of the order for fulfillment;
evaluate one or more additional orders for inclusion of the one or more additional orders in a batch of orders that includes the order that is delayed for display for fulfillment; and
generate the batch of orders for fulfillment.

11. The system of claim 10 , further comprising displaying the batch of orders at the time interval, the batch of orders comprising the order and an additional order received after the order.

12. The system of claim 10 , wherein the predicted benefit for delaying display of the order for fulfillment comprises a probability of the order being fulfilled after a threshold interval.

13. The system of claim 10 , wherein the predicted benefit for delaying display of the order for fulfillment comprises an amount of time saved for fulfilling the order.

14. The system of claim 10 , wherein the time interval for delaying display of the order for fulfillment is selected based at least on an amount of time saved for fulfilling the order equaling or exceeding a threshold.

15. The system of claim 10 , wherein selecting the time interval for delaying display of the order for fulfillment comprises:
determining a predicted amount of time to fulfill the order from characteristics of the order;
for each of a set of candidate time intervals:
determining an overall fulfillment time for the order as a combination of the predicted amount of time to fulfill the order and the candidate time interval, and
determining a probability of the order being fulfilled later than a time identified by the order when the or

Assignees

• Maplebear Inc

Inventors

• Faturechi Reza
• Wang Site
• Putrevu Jagannath

Classifications

• G06N3/084

  Backpropagation, e.g. using gradient descent · CPC title

• G06Q10/0633 Primary

  Workflow analysis · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06Q30/0202

  Market predictions or forecasting for commercial activities · CPC title

• G06N3/08

  Learning methods · CPC title