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-11803894-B2
Application number	US-202117202190-A
Country	US
Kind code	B2
Filing date	Mar 15, 2021
Priority date	Mar 15, 2021
Publication date	Oct 31, 2023
Grant date	Oct 31, 2023

Abstract

An online concierge system allows users to order items within discrete time intervals later than a time when an order was received. The online concierge system allocates a specified percentage of an estimated number of shoppers during a discrete time interval to fulfilling orders received before the discrete time interval. An order may include a flag authorizing flexible fulfillment of the order along with a discrete time interval, which allows the order to be fulfilled earlier than the identified discrete time interval. The online concierge system generates groups of multiple orders authorizing flexible fulfillment and determines a cost for fulfilling different groups of orders. The online concierge system identifies a group of orders authorizing flexible fulfillment having a minimum cost for fulfillment by a shopper, allowing for more allocation of shoppers by enabling grouping of orders identifying different discrete time intervals.

First claim

What is claimed is:

1. A method comprising:
maintaining, at an online concierge system, a plurality of discrete time intervals for fulfilling orders received by the online concierge system, the orders comprising (1) a first type of orders, each of which is to be delivered in a discrete time interval that is later than a discrete time interval in which the order is received, (2) a second type of orders, each of which is to be delivered in a same discrete time interval in which the order is received, and (3) a third type of orders, each of which is to be delivered in a discrete time interval, or any time before the discrete time interval;
applying a machine learning model to determine an estimated number of shoppers available to fulfill orders during each of the discrete time intervals by the online concierge system, wherein the machine learning model is trained using data including historical numbers of shoppers available to fulfill orders at different discrete time intervals;
for each time interval, allocating a specified percentage of estimated shoppers for a discrete time interval for fulfilling orders of the first type and allocating a remaining percentage of the estimated shoppers for the discrete time interval for fulfilling orders of the second type;
receiving an order of the third type from a user of the online concierge system;
responsive to the online concierge system determining one or more shoppers are available to fulfill orders during one or more discrete time intervals earlier than the discrete time interval identified by the order,
retrieving additional orders of the third type received by the online concierge system;
generating a set of candidate groups including one or more additional orders and the received order,
determining a cost of fulfilling each candidate group of the set, the cost of a candidate group based on locations identified in the received order and in the one or more additional orders of the candidate group and items included in the received order and in the one or more additional orders,
selecting a candidate group of the set having a minimum cost; and

identifying the selected candidate group of the set to the one or more shoppers available to fulfill orders during one or more discrete time intervals earlier than the discrete time interval identified by the order for selection.

2. The method of claim 1 , wherein
each order of the third type includes a flag authorizing delivery of items at any time prior to the discrete time interval identified by the additional order, and each order of the third type identifies a discrete time interval not later than the discrete time interval identified by the received order.

3. The method of claim 1 , wherein
each order of the third type includes a flag authorizing delivery of items at any time prior to the discrete time interval identified by the additional order, and each identifies a location within a threshold distance of a location identified by the received order.

4. The method of claim 1 , wherein
each order of the third type includes a flag authorizing delivery of items at any time prior to the discrete time interval identified by the additional order, and identifies a location within a common region maintained by the online concierge system as a location identified by the received order.

5. The method of claim 1 , wherein
each order of the third type includes a flag authorizing delivery of items at any time prior to the discrete time interval identified by the additional order, identifies a location within a common region maintained by the online concierge system as a location identified by the received order, and identifies a discrete time interval not later than the discrete time interval identified by the received order.

6. The method of claim 1 , wherein generating the set of candidate groups including one or more additional orders and the received order comprises:
generating the set of candidate groups so a total of one or more additional orders and the received order in each candidate group is less than a threshold number of orders.

7. The method of claim 1 , wherein generating the set of candidate groups including one or more additional orders and the received order comprises:
generating the set of candidate groups so a total of items included in one or more additional orders and items included in the received order in each candidate group is less than a maximum number of items.

8. The method of claim 1 , wherein generating the set of candidate groups including one or more additional orders and the received order comprises:
generating the set of candidate groups so a type of one or more additional orders and a type of the received order comprise a specific combination of types.

9. The method of claim 1 , wherein the cost of a candidate group accounts for an estimated distance for a shopper to travel to fulfill the received order and the one or more additional orders of the candidate group and an estimated amount of time for the shopper to retrieve items identified by the received order and the one or more additional orders of the candidate group from one or more warehouses.

10. The method of claim 9 , wherein the estimated distance accounts for an amount of time to travel to warehouses identified by the received order and the one or more additional orders of the candidate group and to deliver items to locations identified by the received order and the one or more additional orders of the candidate group.

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:
maintain, at an online concierge system, a plurality of discrete time intervals for fulfilling orders received by the online concierge system, the orders comprising (1) a first type of orders, each of which is to be delivered in a discrete time interval that is later than a discrete time interval in which the order is received, (2) a second type of orders, each of which is to be delivered in a same discrete time interval in which the order is received, and (3) a third type of orders, each of which is to be delivered in a discrete time interval, or any time before the discrete time interval;
apply a machine learning model to determine an estimated number of shoppers available to fulfill orders during each of the discrete time intervals by the online concierge system, wherein the machine learning model is trained using data including historical numbers of shoppers available to fulfill orders at different discrete time intervals;
for each time interval, allocate a specified percentage of estimated shoppers for a discrete time interval for fulfilling orders of the first type and allocating a remaining percentage of the estimated shoppers for the discrete time interval for fulfilling orders of the second type;
receive an order of the third type from a user of the online concierge system;
responsive to the online concierge system determining one or more shoppers are available to fulfill orders during one or more discrete time intervals earlier than the discrete time interval identified by the order,
retrieve additional orders of the third type received by the online concierge system;
generate a set of candidate groups including one or more additional orders and the received order,
determine a cost of fulfilling each candidate group of the set, the cost of a candidate group based on locations identified in the received order and in the one or more additional orders of the candidate group and items included in the received order and in the one or more additional orders,
select a candidate group of the set havin

Assignees

• Maplebear Inc

Inventors

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

Classifications

• G06Q30/0635 Primary

  replenishment orders; recurring orders · CPC title

• G06Q10/06313

  Resource planning in a project environment · CPC title

• G06Q10/06315 Primary

  Needs-based resource requirements planning or analysis · CPC title

• G06Q10/087

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

• G06Q30/0284

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