US-12619946-B2 - Parallel processing candidate pairings of delivery agents with routes to fulfill delivery orders and asynchronous selecting optimal pairings from the candidates

Abstract

An online concierge system receives information describing orders from its customers and generates a route for each order based on this information. The routes are partitioned into multiple sets of routes and multiple candidate generation processes are executed in parallel. During execution of a candidate generation process, one or more routes included in each set of routes are paired with shoppers of the system based on a set of constraints, producing multiple route-shopper pairs. A cost associated with each route-shopper pair is determined based on attributes associated with each shopper and/or information associated with each route of the pair. During an optimization process, which is executed asynchronously with the candidate generation process, one or more route-shopper pairs are selected based on pairing-cost data identifying route-shopper pairs and their associated costs. One or more requests to fulfill orders are sent to one or more shoppers based on the selected route-shopper pair(s).

Inventors

• Xianlei Qiu
• Site Wang
• Deepak Tirumalasetty

Assignees

• MAPLEBEAR INC.

Dates

Publication Date

20260505

Application Date

20220429

Claims (18)

1. 1 . A method comprising: storing computer-executable instructions for a workflow in a non-transitory computer-readable medium, wherein the computer-executable instructions comprises instructions for a first part of the workflow and instructions for a second part of the workflow, wherein: the instructions for the first part of the workflow comprise computer-executable instructions that, when executed by a processor, cause the processor to execute a candidate generation process, and the instructions for the second part of the workflow comprise computer-executable instructions that, when executed by a processor, cause the processor to execute an optimization process; receiving order information for a plurality of orders from one or more devices associated with one or more customers of an online concierge system, wherein the order information describes, for each order, information identifying one or more ordered items, a warehouse location, and a customer location; passing each of the orders to one of a plurality of candidate generation processes; executing, in parallel by a first subset of a plurality of processors of the online concierge system, the plurality of candidate generation processes, wherein executing a candidate generation process in parallel comprises executing, by a processor of the first subset of processors, the computer-executable instructions for the first part of the workflow, wherein each candidate generation process is configured to perform a first part of a workflow for processing an order of the plurality of orders, wherein the first part of the workflow for processing an order comprises: selecting, by a processor of the first subset of the plurality of processors, a shopper of a set of shoppers that satisfies a set of constraints for fulfilling the order, predicting, by the processor of the first subset of the plurality of processors, a cost for fulfillment of the order by the selected shopper, the cost based on an attribute associated with the shopper or information about the order, and storing, by the processor of the first subset of the plurality of processors, a candidate route-shopper pair and the corresponding cost in a memory, wherein the candidate route-shopper pair corresponds to the selected shopper of the set of shoppers and a route associated with the order; executing, by a second subset of the plurality of processors of the online concierge system asynchronously with the candidate generation processes, a second part of the workflow for processing an order of the plurality of orders, wherein executing the second part of the workflow comprises executing, by a processor of the second subset of processors, the computer-executable instructions for the second part of the workflow, wherein the second part of the workflow comprises an optimization process comprising: iteratively accessing, from the memory, the candidate route-shopper pairs and corresponding costs as the candidate generation processes generate the candidate route-shopper and corresponding costs by performing the first part of the workflow for processing an order, selecting a candidate route-shopper pair of the generated candidate route-shopper pairs for each target order from the accessed candidate route-shopper pairs based on the corresponding costs by: applying a linear sum assignment algorithm to the generated candidate route-shopper pairs; and sending, for each selected route-shopper pair, a request to fulfill the order associated with the selected route-shopper pair to a device associated with the shopper corresponding to the selected route-shopper pair.
2. 2 . The method of claim 1 , wherein predicting a cost for fulfillment of the order comprises determining the cost based on at least one of: a travel time, a travel distance, and an amount of time required to collect the one or more items included in the order.
3. 3 . The method of claim 1 , wherein predicting a cost for fulfillment of the order comprises using a machine learning model to predict at least a component of the cost.
4. 4 . The method of claim 1 , wherein selecting a shopper that satisfies a set of constraints for fulfilling the order comprises applying a set of constraints that include one or more of: an age restriction associated with purchasing an item included in the set of orders, an age of a shopper of the plurality of shoppers associated with the online concierge system, a membership associated with a retailer, one or more memberships associated with the shopper, a minimum cargo capacity associated with one or more orders of the set of orders, a cargo capacity associated with the shopper, an availability of the shopper to fulfill each of the one or more orders, a shopper location associated with the shopper, the retail location of the warehouse associated with the retailer, the customer location associated with the customer, a threshold distance between the shopper location associated with the shopper and the retail location of the warehouse associated with the retailer, a threshold distance between the customer location associated with the customer and the shopper location associated with the shopper, a threshold amount of time required to travel a distance between the shopper location associated with the shopper and the retail location of the warehouse associated with the retailer, and a threshold amount of time required to travel a distance between the customer location associated with the customer and the shopper location associated with the shopper.
5. 5 . The method of claim 1 , wherein passing each of the orders to one of a plurality of candidate generation processes comprises partitioning the plurality of orders based at least in part on: an age restriction associated with purchasing an item included in the orders, a membership associated with a retailer, a minimum cargo capacity associated with the orders, the warehouse location associated with the orders, and the customer location associated with the orders.
6. 6 . The method of claim 1 , wherein passing each of the orders to one of a plurality of candidate generation processes comprises randomly partitioning the plurality of orders.
7. 7 . 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 perform the steps of: storing computer-executable instructions for a workflow in a non-transitory computer-readable medium, wherein the computer-executable instructions comprises instructions for a first part of the workflow and instructions for a second part of the workflow, wherein: the instructions for the first part of the workflow comprise computer-executable instructions that, when executed by a processor, cause the processor to execute a candidate generation process, and the instructions for the second part of the workflow comprise computer-executable instructions that, when executed by a processor, cause the processor to execute an optimization process; receiving order information for a plurality of orders from one or more devices associated with one or more customers of an online concierge system, wherein the order information describes, for each order, information identifying one or more ordered items, a warehouse location, and a customer location; passing each of the orders to one of a plurality of candidate generation processes; executing, in parallel by a first subset of a plurality of processors of the online concierge system, the plurality of candidate generation processes, wherein executing a candidate generation process in parallel comprises executing, by a processor of the first subset of processors, the computer-executable instructions for the first part of the workflow, wherein each candidate generation process is configured to perform a first part of a workflow for processing an order of the plurality of orders, wherein the first part of the workflow for processing an order comprises: selecting, by a processor of the first subset of the plurality of processors, a shopper of a set of shoppers that satisfies a set of constraints for fulfilling the order, predicting, by the processor of the first subset of the plurality of processors, a cost for fulfillment of the order by the selected shopper, the cost based on an attribute associated with the shopper or information about the order, and storing, by the processor of the first subset of the plurality of processors, a candidate route-shopper pair and the corresponding cost in a memory, wherein the candidate route-shopper pair corresponds to the selected shopper of the set of shoppers and a route associated with the order; executing, by a second subset of the plurality of processors of the online concierge system asynchronously with the candidate generation processes, a second part of the workflow for processing an order of the plurality of orders, wherein executing the second part of the workflow comprises executing, by a processor of the second subset of processors, the computer-executable instructions for the second part of the workflow, wherein the second part of the workflow comprises an optimization process comprising: iteratively accessing, from the memory, the candidate route-shopper pairs and corresponding costs as the candidate generation processes generate the candidate route-shopper and corresponding costs by performing the first part of the workflow for processing an order, selecting a candidate route-shopper pair of the generated candidate route-shopper pairs for each target order from the accessed candidate route-shopper pairs based on the corresponding costs by: applying a linear sum assignment algorithm to the generated candidate route-shopper pairs; and sending, for each selected route-shopper pair, a request to fulfill the order associated with the selected route-shopper pair to a device associated with the shopper corresponding to the selected route-shopper pair.
8. 8 . The computer program product of claim 7 , wherein predicting a cost for fulfillment of the order comprises determining the cost based on at least one of: a travel time, a travel distance, and an amount of time required to collect the one or more items included in the order.
9. 9 . The computer program product of claim 7 , wherein predicting a cost for fulfillment of the order comprises using a machine learning model to predict at least a component of the cost.
10. 10 . The computer program product of claim 7 , wherein selecting a shopper that satisfies a set of constraints for fulfilling the order comprises applying a set of constraints that include one or more of: an age restriction associated with purchasing an item included in the set of orders, an age of a shopper of the plurality of shoppers associated with the online concierge system, a membership associated with a retailer, one or more memberships associated with the shopper, a minimum cargo capacity associated with one or more orders of the set of orders, a cargo capacity associated with the shopper, an availability of the shopper to fulfill each of the one or more orders, a shopper location associated with the shopper, the retail location of the warehouse associated with the retailer, the customer location associated with the customer, a threshold distance between the shopper location associated with the shopper and the retail location of the warehouse associated with the retailer, a threshold distance between the customer location associated with the customer and the shopper location associated with the shopper, a threshold amount of time required to travel a distance between the shopper location associated with the shopper and the retail location of the warehouse associated with the retailer, and a threshold amount of time required to travel a distance between the customer location associated with the customer and the shopper location associated with the shopper.
11. 11 . The computer program product of claim 7 , wherein passing each of the orders to one of a plurality of candidate generation processes comprises partitioning the plurality of orders based at least in part on: an age restriction associated with purchasing an item included in the orders, a membership associated with a retailer, a minimum cargo capacity associated with the orders, the warehouse location associated with the orders, and the customer location associated with the orders.
12. 12 . The computer program product of claim 7 , wherein passing each of the orders to one of a plurality of candidate generation processes comprises randomly partitioning the plurality of orders.
13. 13 . A computer system comprising: a processor; a non-transitory computer readable storage medium storing instructions that, when executed by the processor, cause the processor to perform the steps of: storing computer-executable instructions for a workflow in a non-transitory computer-readable medium, wherein the computer-executable instructions comprises instructions for a first part of the workflow and instructions for a second part of the workflow, wherein: the instructions for the first part of the workflow comprise computer-executable instructions that, when executed by a processor, cause the processor to execute a candidate generation process, and the instructions for the second part of the workflow comprise computer-executable instructions that, when executed by a processor, cause the processor to execute an optimization process; receiving order information for a plurality of orders from one or more devices associated with one or more customers of an online concierge system, wherein the order information describes, for each order, information identifying one or more ordered items, a warehouse location, and a customer location; passing each of the orders to one of a plurality of candidate generation processes; executing, in parallel by a first subset of a plurality of processors of the online concierge system, the plurality of candidate generation processes, wherein executing a candidate generation process in parallel comprises executing, by a processor of the first subset of processors, the computer-executable instructions for the first part of the workflow, wherein each candidate generation process is configured to perform a first part of a workflow for processing an order of the plurality of orders, wherein the first part of the workflow for processing an order comprises: selecting, by a processor of the first subset of the plurality of processors, a shopper of a set of shoppers that satisfies a set of constraints for fulfilling the order, predicting, by the processor of the first subset of the plurality of processors, a cost for fulfillment of the order by the selected shopper, the cost based on an attribute associated with the shopper or information about the order, and storing, by the processor of the first subset of the plurality of processors, a candidate route-shopper pair and the corresponding cost in a memory, wherein the candidate route-shopper pair corresponds to the selected shopper of the set of shoppers and a route associated with the order; executing, by a second subset of the plurality of processors of the online concierge system asynchronously with the candidate generation processes, a second part of the workflow for processing an order of the plurality of orders, wherein executing the second part of the workflow comprises executing, by a processor of the second subset of processors, the computer-executable instructions for the second part of the workflow, wherein the second part of the workflow comprises an optimization process comprising: iteratively accessing, from the memory, the candidate route-shopper pairs and corresponding costs as the candidate generation processes generate the candidate route-shopper and corresponding costs by performing the first part of the workflow for processing an order, selecting a candidate route-shopper pair of the generated candidate route-shopper pairs for each target order from the accessed candidate route-shopper pairs based on the corresponding costs by: applying a linear sum assignment algorithm to the generated candidate route-shopper pairs; and sending, for each selected route-shopper pair, a request to fulfill the order associated with the selected route-shopper pair to a device associated with the shopper corresponding to the selected route-shopper pair.
14. 14 . The computer system of claim 13 , wherein predicting a cost for fulfillment of the order comprises determining the cost based on at least one of: a travel time, a travel distance, and an amount of time required to collect the one or more items included in the order.
15. 15 . The computer system of claim 14 , wherein predicting a cost for fulfillment of the order comprises using a machine learning model to predict at least a component of the cost.
16. 16 . The computer system of claim 13 , wherein selecting a shopper that satisfies a set of constraints for fulfilling the order comprises applying a set of constraints that include one or more of: an age restriction associated with purchasing an item included in the set of orders, an age of a shopper of the plurality of shoppers associated with the online concierge system, a membership associated with a retailer, one or more memberships associated with the shopper, a minimum cargo capacity associated with one or more orders of the set of orders, a cargo capacity associated with the shopper, an availability of the shopper to fulfill each of the one or more orders, a shopper location associated with the shopper, the retail location of the warehouse associated with the retailer, the customer location associated with the customer, a threshold distance between the shopper location associated with the shopper and the retail location of the warehouse associated with the retailer, a threshold distance between the customer location associated with the customer and the shopper location associated with the shopper, a threshold amount of time required to travel a distance between the shopper location associated with the shopper and the retail location of the warehouse associated with the retailer, and a threshold amount of time required to travel a distance between the customer location associated with the customer and the shopper location associated with the shopper.
17. 17 . The computer system of claim 13 , wherein passing each of the orders to one of a plurality of candidate generation processes comprises partitioning the plurality of orders based at least in part on: an age restriction associated with purchasing an item included in the orders, a membership associated with a retailer, a minimum cargo capacity associated with the orders, the warehouse location associated with the orders, and the customer location associated with the orders.
18. 18 . The computer system of claim 13 , wherein passing each of the orders to one of a plurality of candidate generation processes comprises randomly partitioning the plurality of orders.

Description

BACKGROUND This disclosure relates generally to selecting delivery agents to fulfill orders placed in an online concierge system, and more specifically to selecting optimal pairings of delivery agents to fulfill orders using a set of parallel processes to select a feasible space of candidate pairings and an asynchronous process to select optimal pairings from the candidates. Online concierge systems allow customers to place online delivery orders and match the orders with delivery agents (i.e., shoppers) to fulfill the orders at physical retailers on behalf of the customers. Shoppers may fulfill orders by performing different tasks involved in fulfilling each order. For example, tasks involved in fulfilling an order may include driving to a particular retail store, collecting one or more items included in the order, purchasing the items, and delivering the items to a customer. Online concierge systems typically select shoppers to fulfill orders in a way that minimizes cost while maximizing customer satisfaction. To do so, an online concierge system may select physical retail locations at which orders may be fulfilled, determine routes shoppers may take to fulfill the orders, and then select shoppers to fulfill the orders based on the routes while accounting for various factors that affect cost. Examples of such factors include travel time and distance, traffic conditions during different times of the day, whether multiple shoppers should be involved in fulfilling a single order, whether a single shopper should be involved in fulfilling a batch of orders, variations in the amount of time it may take shoppers to perform different tasks, etc. An online concierge system also may account for various factors that affect customer satisfaction, such as the availability of different items included in each order at different physical retail locations, whether a shopper is likely to make an error when collecting items included in an order, etc. Furthermore, an online concierge system may be required to observe various constraints, such as age restrictions associated with purchasing certain items (e.g., alcohol or tobacco) that may be included in orders, membership requirements associated with different retailers with which orders may be placed, availability of shoppers to fulfill orders to be delivered within delivery windows specified by customers, etc. However, the processes that online concierge systems might use to select shoppers to fulfill orders is often characterized by high latency and might not be scalable to meet increasing demand. Due to the large number of orders that may be received by online concierge systems, it may take an online concierge system an inordinate amount of time to consider different combinations of physical retail locations at which orders may be fulfilled to determine the routes shoppers may take to fulfill the orders. Once the routes have been determined, it may also take the online concierge system an excessive amount of time to consider different combinations of shoppers who may be involved in fulfilling its orders. Additionally, the factors and constraints described above only complicate this process and may further increase the amount of time required to select shoppers to fulfill orders. Moreover, the amount of time required to select shoppers to fulfill orders increases during peak hours (e.g., when physical retail locations open) and as online concierge systems increase in popularity. SUMMARY Online concierge systems allow customers to place online delivery orders and match the orders with shoppers to fulfill the orders at physical retailers on behalf of the customers. Online concierge systems typically will select shoppers to fulfill the orders in a way that minimizes cost while maximizing customer satisfaction. However, the processes that online concierge systems might use to do so is often characterized by high latency and might not be scalable due to the large number of orders that may be received by online concierge systems, the different combinations of physical retail locations at which orders may be fulfilled and shoppers who may be involved in fulfilling the orders, and various additional factors and constraints. These problems are further exacerbated during peak hours and as online concierge systems increase in popularity. To reduce latency, improve scalability, and address other technical challenges, an online concierge system selects optimal pairings of shoppers with routes to fulfill orders placed in the online concierge system using an asynchronous process, in accordance with one or more aspects of the disclosure. More specifically, the online concierge system receives information describing orders from customers of the online concierge system, in which the information describing each order identifies a retailer associated with the order, one or more items included in the order, a location associated with a customer associated with the order, and a delivery time wi