Allocating shoppers and orders for fulfillment by an online concierge system to account for variable numbers of shoppers across different time windows

Patent metadata

Field	Value
Publication number	US-12198182-B2
Application number	US-202318473789-A
Country	US
Kind code	B2
Filing date	Sep 25, 2023
Priority date	Mar 15, 2021
Publication date	Jan 14, 2025
Grant date	Jan 14, 2025

Abstract

An online concierge system receives two types of orders, one of which requires fulfillment in a specific time interval, while the other can be fulfilled anytime up to a specific time interval. A machine learning model, trained on historical data about available shoppers in discrete time intervals, is used to predict how many shoppers will be available to fulfill orders in each time interval. For each time interval, the system retrieves the relevant orders of both types and creates candidate groups including orders of both types. For each group, the system determines a fulfillment cost based on items in the orders. The candidate group with the lowest cost is selected, and the orders in the selected group are sent to devices of available shoppers in that interval, prompting the shoppers to view and fulfill the orders.

First claim

What is claimed is:

1. A method comprising:
receiving, at an online concierge system, a plurality of orders, the plurality of orders comprising (1) a first type of orders, each of which is to be fulfilled in a specified discrete time interval among a plurality of discrete time intervals, and (2) a second type of orders, each of which is to be fulfilled in a specified discrete time interval, or any time before the specified discrete time interval, wherein a classification of an order in the plurality of orders as either the first type or the second type is based on a user selection at a time the order is placed;
applying a machine learning model to determine an estimated number of shoppers available to fulfill orders during each of the plurality of discrete time intervals, wherein the machine learning model is trained using data including historical numbers of shoppers available to fulfill orders at different discrete time intervals;
for a discrete time interval among the plurality of discrete time intervals,
retrieving a first set of orders of the first type received by the online concierge system, each of the first set of orders of the first type specifying the discrete time interval, such that each of the first set of orders is to be fulfilled during the discrete time interval;
retrieving a second set of orders of the second type received by the online concierge system, each of the second set of orders of the second type being fulfillable during the discrete time interval or a later time interval;
generating a set of candidate groups including one or more orders from the first set of orders and the second set of orders;
for each of the set of candidate groups, determining a cost of fulfilling based on items included in the orders of the corresponding candidate group;
selecting a candidate group of the set of candidate groups having a minimum cost; and
sending orders in the selected candidate group to client devices of one or more shoppers available during the discrete time interval causing the orders in the selected candidate group to be displayed at the client devices.

2. The method of claim 1 , wherein the first type of orders further includes a subtype of orders, each of which is received during a current time interval and required to be delivered during the current time interval, and determining the cost of fulfilling is further based on whether an order in a candidate group is the subtype of order.

3. The method of claim 1 , wherein retrieving each of the plurality of orders identifying a delivery location, and determining the cost of fulfilling is further based on the identified delivery locations in the orders of a corresponding candidate group.

4. The method of claim 3 , wherein the cost of the candidate group is determined based on an estimated distance for a shopper to travel to fulfill the orders of the candidate group and an estimated amount of time for the shopper to retrieve items identified by the orders of the candidate group from one or more warehouses.

5. The method of claim 4 , wherein the estimated distance is determined based on an amount of time to travel to warehouses identified by the orders of the candidate group and to deliver items to locations identified by the orders of the candidate group.

6. The method of claim 3 , wherein determining the cost of fulfilling is further based on a number of delivery locations in the orders of a corresponding candidate group within a common region.

7. The method of claim 1 , wherein generating the set of candidate groups comprises:
generating the set of candidate groups so a total number of orders in each candidate group is less than a threshold number of orders.

8. The method of claim 1 , wherein generating the set of candidate groups comprises:
generating the set of candidate groups so a total number of items included in orders in each candidate group is less than a maximum number of items.

9. The method of claim 1 , wherein generating the set of candidate groups comprises:
generating the set of candidate groups so orders in each candidate group comprise a specific combination of types of orders.

10. A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by one or more processors, cause the one or more processors to:
receive, at an online concierge system, a plurality of orders, the plurality of orders comprising (1) a first type of orders, each of which is to be fulfilled in a specified discrete time interval among a plurality of discrete time intervals, and (2) a second type of orders, each of which is to be fulfilled in a specified discrete time interval, or any time before the specified discrete time interval, wherein a classification of an order in the plurality of orders as either the first type or the second type is based on a user selection at a time the order is placed;
apply a machine learning model to determine an estimated number of shoppers available to fulfill orders during each of the plurality of discrete time intervals, wherein the machine learning model is trained using data including historical numbers of shoppers available to fulfill orders at different discrete time intervals;
for a discrete time interval among the plurality of discrete time intervals,
retrieve a first set of orders of the first type received by the online concierge system, each of the first set of orders of the first type specifying the discrete time interval, such that each of the first set of orders is to be fulfilled during the discrete time interval;
retrieve a second set of orders of the second type received by the online concierge system, each of the second set of orders of the second type being fulfillable during the discrete time interval or a later time interval; and
generate a set of candidate groups including one or more orders from the first set of orders and the second set of orders;

for each of the set of candidate groups, determine a cost of fulfilling based on locations identified in the orders of a corresponding candidate group and items included in the orders of the corresponding candidate group,
select a candidate group of the set of candidate groups having a minimum cost; and
send orders in the selected candidate group to client devices of one or more shoppers available during the discrete time interval causing the orders in the selected candidate group to be displayed at the client devices.

11. The computer program product of claim 10 , wherein the first type of orders further includes a subtype of orders, each of which is received during a current time interval and required to be delivered during the current time interval, and determining the cost of fulfilling is further based on whether an order in a candidate group is the subtype of order.

12. The computer program product of claim 10 , wherein retrieving each of the plurality of orders identifying a delivery location, and determining the cost of fulfilling is further based on the identified delivery locations in the orders of a corresponding candidate group.

13. The computer program product of claim 10 , wherein the cost of the candidate group is determined based on an estimated distance for a shopper to travel to fulfill the orders of the candidate group and an estimated amount of time for the shopper to retrieve items identified by the orders of the candidate group from one or more warehouses.

14. The computer program product of claim 13 , wherein the estimated distance is determined based on an amount of time to travel to warehouses identified by the orders of the candidate group and to deliver items t

Assignees

• Maplebear Inc

Inventors

• Putrevu Jagannath
• Wang Zi
• Wang Site
• Deng Houtao
• Chen Yijia
• Zhuang Mingzhe
• Chen Ji
• Tirumalasetty Deepak

Classifications

• G06Q10/06313

  Resource planning in a project environment · CPC title

• G06Q30/0284

  Time or distance, e.g. usage of parking meters or taximeters · CPC title

• G06Q10/087

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

• G06Q10/06315 Primary

  Needs-based resource requirements planning or analysis · CPC title

• G06Q30/0635 Primary

  replenishment orders; recurring orders · CPC title