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-11875394-B2
Application number	US-202217591584-A
Country	US
Kind code	B2
Filing date	Feb 2, 2022
Priority date	Feb 2, 2022
Publication date	Jan 16, 2024
Grant date	Jan 16, 2024

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:
training, by one or more processors of an online concierge system, a machine learning model that outputs a predicted benefit from delaying identification of an order to shoppers for fulfillment, wherein training of the machine learning model comprises:
applying, by the one or more processors, the machine learning model to examples of batching training data, each example of the batching training data including a time interval for delaying an example order, one or more information describing the example order, and a benefit label applied to each example of the batching training data identifying a benefit to the online concierge system from delaying identification of the example order;
backpropagating, by the one or more processors, 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, by the one or more processors, one or more of the error terms based on a difference between the benefit label applied to an example of the batching training data and a predicted benefit to the online concierge system from delaying identification of the example order; and
stopping the backpropagation after the one or more loss functions satisfy one or more criteria;

receiving the order at the online concierge system;
determining, by the one or more processors, the predicted benefit to the online concierge system for delaying display of the order to one or more shoppers for each of a plurality of candidate time intervals;
selecting, based on the predicted benefit associated with each of the plurality of candidate time intervals, a time interval of the plurality of time intervals for delaying display of the order to the one or more shoppers until after the selected time interval;
evaluating one or more additional orders for inclusion of the one or more additional orders in a batch of orders that includes the order to be displayed until after the selected time interval; and
displaying the batch of orders to the one or more shoppers after the selected time interval lapses.

2. The method of claim 1 , wherein displaying the batch of orders to the one or more shoppers after the selected time interval lapses comprises:
displaying the order and at least one batch including the order and an additional order received after the order.

3. The method of claim 1 , wherein the predicted benefit from delaying identification of the order to shoppers for fulfillment for a candidate time interval comprises a probability of the order being included in at least one batch.

4. The method of claim 3 , wherein the selected time interval is selected based at least on the probability of the order being included in at least one batch equaling or exceeding a threshold.

5. The method of claim 1 , wherein the predicted benefit from delaying identification of the order to shoppers for fulfillment for a candidate time interval comprises an amount of time saved for fulfilling the order.

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

7. The method of claim 1 , wherein selecting the time interval of the plurality of candidate time intervals for delaying display of the order to the one or more shoppers 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;
determining a probability of the order being fulfilled later than the time identified by the order when the order is delayed from display to shoppers by the candidate time interval from the overall fulfillment time; and
selecting a time interval of the set based on the determine probabilities.

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

9. The method of claim 7 , wherein determining the predicted amount of time to fulfill the order from characteristics of the order comprises:
applying a fulfillment model to characteristics of the order, the fulfillment model trained by:
obtaining training data including a plurality of examples, each example including information describing a fulfilled order and having a label applied specifying a length of time from the online concierge system receiving a previously fulfilled order and the online concierge 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 an example of the training data and a predicted amount of time to fulfill an order corresponding to the example of the training data; and
stopping the backpropagation after the one or more loss functions satisfy one or more criteria.

10. A method comprising:
receiving an order at an online concierge system, the order identifying a time for fulfillment;
determining, by one or more processors of the online concierge system, a predicted amount of time to fulfill the order based on characteristics of the order;
determining, by one or more processors of the online concierge system, a predicted benefit to the online concierge system for delaying display of the order to one or more shoppers for each of a plurality of candidate time intervals, wherein determining the predicted benefit for a candidate time interval comprises:
determining, by one or more processors of the online concierge system, 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;
determining, by one or more processors of the online concierge system, a probability of the order being fulfilled later than the time identified by the order when the order is delayed from display to shoppers by the candidate time interval time by applying a late fulfillment machine learning model to determine the probability of the order being fulfilled later than the time identified by the order, wherein training of the late fulfillment machine learning model comprises:
obtaining, by one or more processors of the online concierge system, training data including a plurality of examples, each example including an example late fulfillment order, a fulfillment time for the example late fulfillment order, and a label applied to each example indicating whether the example late fulfillment order was fulfilled later than a time identified in the example late fulfillment order;
backpropagating, by one or more processors of the online concierge system, one or more error terms obtained from one or more loss functions associated with the late fulfillment machine learning model to update a set of parameters of the late fulfillment machine learning model, the backpropagating comprising updating, by the one or more processors, one or more of the error terms based on a difference between the label applied to an example of the training data and a predicted probability of the example late fulfillment order being fulfilled later than the time identified by the example late fulfillment order; and

stopping the backpropagation after the one or more loss functions satisfy one

Assignees

• Maplebear Inc

Inventors

• Faturechi Reza
• Wang Site
• Putrevu Jagannath

Classifications

• G06Q30/0635 Primary

  replenishment orders; recurring orders · CPC title

• G06N3/084

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

• G06Q10/0633 Primary

  Workflow analysis · CPC title

• G06Q10/02

  Reservations, e.g. for tickets, services or events · CPC title

• G06N3/045

  Combinations of networks · CPC title