Optimizing task assignments in a delivery system

{
  "publication_number": "US12148305B2",
  "country": "US",
  "kind": "B2",
  "title": "Optimizing task assignments in a delivery system",
  "abstract": "An online shopping concierge system identifies a set of delivery orders and a set of delivery agents associated with a location. The system allocates the orders among the agents, each agent being allocated at least one order. The system obtains agent progress data describing travel progress of the agents to the location, and order preparation progress data describing progress of preparing the orders for delivery. The system periodically updates the allocation of the orders among the agents based on the agent progress data and the order preparation progress data. This involves re-allocating at least one order to a different delivery agent. When a first agent arrives at the location, the system assigns to the first agent the orders allocated to the first agent. The system then removes the first agent from the set of available delivery agents, and removes the assigned delivery orders from the set of delivery orders.",
  "claims": [
    "1. A method for optimizing delivery assignments, the method comprising: receiving, by an online system from customer devices, a plurality of delivery orders associated with a location, wherein the plurality of delivery orders are prepared at the location for delivery; responsive to receiving the plurality of delivery orders, identifying, by the online system, a plurality of delivery agents associated with the location; allocating, by the online system, the plurality of delivery orders among the plurality of delivery agents, each delivery agent being allocated at least one delivery order, each delivery agent being associated with a shopper device having a shopper mobile application installed thereon, the shopper mobile application including: a scanning module configured to identify an item of the at least one delivery order and obtain information describing the identified item from the online system, a basket manager configured to update a running record of items of the at least one delivery order based on the identified item, and generate order preparation progress data describing progress of preparing the at least one delivery order based on the running record of items of the at least one delivery order, and an interface configured to transmit the preparation progress data to the online system; obtaining, by the online system from the shopper devices, order preparation progress data describing progress of preparing the plurality of delivery orders for delivery; periodically updating, by the online system, the allocation of the plurality of delivery orders among the plurality of delivery agents based on the order preparation progress data by re-allocating at least one delivery order of the plurality of delivery orders to a different delivery agent of the plurality of delivery agents, wherein updating the allocation comprises preventing delivery orders allocated to a first delivery agent from being reallocated to a second delivery agent among the plurality of delivery agents in response to the first delivery agent arriving at the location.",
    "2. The method of claim 1, wherein allocating the plurality of delivery orders among the plurality of delivery agents is based on a destination location of each delivery order and a delivery window of each delivery order.",
    "3. The method of claim 2, wherein allocating the plurality of delivery orders among the plurality of delivery agents comprises determining an optimal set of delivery orders for each delivery agent to deliver based on the delivery agent progress data, the order preparation progress data, the destination locations of the plurality of delivery orders, and the delivery windows of the plurality of delivery orders.",
    "4. The method of claim 1, wherein each delivery order of the plurality of delivery orders is prepared for delivery by a picking agent of a plurality of picking agents, and the order preparation progress data describes progress of picking agents in preparing the plurality of delivery orders for delivery.",
    "5. The method of claim 1, wherein: the delivery agent progress data comprises an estimated time of arrival for each delivery agent of the plurality of delivery agents; and the order preparation progress data comprises an estimated time of preparation completion of each delivery order of the plurality of delivery orders.",
    "6. The method of claim 5, wherein, at a time that the first delivery agent arrives at the location, the delivery orders allocated to the first delivery agent each have an estimated time of preparation completion of zero.",
    "7. The method of claim 1, further comprising: determining to instruct an additional delivery agent to travel to the location based on a time and a cost associated with the additional delivery agent traveling to the location; adding the additional delivery agent to the plurality of delivery agents; and allocating at least one delivery order of the plurality of delivery orders to the additional delivery agent.",
    "8. The method of claim 1, further comprising: receiving an additional delivery order; adding the additional delivery order to the plurality of delivery orders; and allocating the additional delivery order to a second delivery agent of the plurality of delivery agents.",
    "9. The method of claim 8, further comprising: in response to allocating the additional delivery order to a second delivery agent of the plurality of delivery agents, re-allocating at least one delivery order of the plurality of delivery orders to a different delivery agent of the plurality of delivery agents.",
    "10. The method of claim 1, further comprising: communicating an instruction to the first delivery agent to travel to the location; and in response to the first delivery agent arriving at the location, communicating an instruction to the first delivery agent to deliver the delivery orders allocated to the first delivery agent.",
    "11. A non-transitory computer-readable storage medium storing instructions for optimizing delivery assignments, the instructions when executed causing a processor of an online system to: receive, by an online system from customer devices, a plurality of delivery orders associated with a location, wherein the plurality of delivery orders are prepared at the location for delivery; responsive to receiving the plurality of delivery orders, identify, by the online system, a plurality of delivery agents associated with the location; allocate, by the online system, the plurality of delivery orders among the plurality of delivery agents, each delivery agent being allocated at least one delivery order, each delivery agent being associated with a shopper device having a shopper mobile application installed thereon, the shopper mobile application including: a scanning module configured to identify an item of the at least one delivery order and obtain information describing the identified item from the online system, a basket manager configured to update a running record of items of the at least one delivery order based on the identified item, and generate order preparation progress data describing progress of preparing the at least one delivery order based on the running record of items of the at least one delivery order, and an interface configured to transmit the preparation progress data to the online system; obtain, by the online system from the shopper devices, order preparation progress data describing progress of preparing the plurality of delivery orders for delivery; periodically update, by the online system, the allocation of the plurality of delivery orders among the plurality of delivery agents based on the order preparation progress data by re-allocating at least one delivery order of the plurality of delivery orders to a different delivery agent of the plurality of delivery agents, wherein updating the allocation comprises preventing delivery orders allocated to a first delivery agent from being reallocated to a second delivery agent among the plurality of delivery agents in response to the first delivery agent arriving at the location.",
    "12. The non-transitory computer-readable storage medium of claim 11, wherein allocating the plurality of delivery orders among the plurality of delivery agents is based on a destination location of each delivery order and a delivery window of each delivery order.",
    "13. The non-transitory computer-readable storage medium of claim 12, wherein the instructions when executed cause the processor to allocate the plurality of delivery orders among the plurality of delivery agents further cause the processor to determine an optimal set of delivery orders for each delivery agent to deliver based on the delivery agent progress data, the order preparation progress data, the destination locations of the plurality of delivery orders, and the delivery windows of the plurality of delivery orders.",
    "14. The non-transitory computer-readable storage medium of claim 11, wherein each delivery order of the plurality of delivery orders is prepared for delivery by a picking agent of a plurality of picking agents, and the order preparation progress data describes progress of picking agents in preparing the plurality of delivery orders for delivery.",
    "15. The non-transitory computer-readable storage medium of claim 11, wherein: the delivery agent progress data comprises an estimated time of arrival for each delivery agent of the plurality of delivery agents; and the order preparation progress data comprises an estimated time of preparation completion of each delivery order of the plurality of delivery orders.",
    "16. A computer system for optimizing delivery assignments, the computer system comprising: a computer processor; a non-transitory computer-readable storage medium storing instructions that when executed by the computer processor, cause the computer system to: receive, from customer devices, a plurality of delivery orders associated with a location, wherein the plurality of delivery orders are prepared at the location for delivery; responsive to receiving the plurality of delivery orders, identify a plurality of delivery agents associated with the location; allocate the plurality of delivery orders among the plurality of delivery agents, each delivery agent being allocated at least one delivery order, each delivery agent being associated with a shopper device having a shopper mobile application installed thereon, the shopper mobile application including: a scanning module configured to identify an item of the at least one delivery order and obtain information describing the identified item, a basket manager configured to update a running record of items of the at least one delivery order based on the identified item, and generate order preparation progress data describing progress of preparing the at least one delivery order based on the running record of items of the at least one delivery order, and an interface configured to transmit the preparation progress data to the computer system; obtain from the shopper devices, order preparation progress data describing progress of preparing the plurality of delivery orders for delivery; periodically update the allocation of the plurality of delivery orders among the plurality of delivery agents based on the order preparation progress data by re-allocating at least one delivery order of the plurality of delivery orders to a different delivery agent of the plurality of delivery agents, wherein updating the allocation comprises preventing delivery orders allocated to a first delivery agent from being reallocated to a second delivery agent among the plurality of delivery agents in response to the first delivery agent arriving at the location.",
    "17. The computer system of claim 16, wherein allocating the plurality of delivery orders among the plurality of delivery agents is based on a destination location of each delivery order and a delivery window of each delivery order.",
    "18. The computer system of claim 17, wherein allocating the plurality of delivery orders among the plurality of delivery agents comprises determining an optimal set of delivery orders for each delivery agent to deliver based on the delivery agent progress data, the order preparation progress data, the destination locations of the plurality of delivery orders, and the delivery windows of the plurality of delivery orders.",
    "19. The computer system of claim 16, wherein each delivery orders of the plurality of delivery orders is prepared for delivery by a picking agent of a plurality of picking agents, and the order preparation progress data describes progress of picking agents in preparing the plurality of delivery orders for delivery.",
    "20. The computer system of claim 16, wherein: the delivery agent progress data comprises an estimated time of arrival for each delivery agent of the plurality of delivery agents; and the order preparation progress data comprises an estimated time of preparation completion of each delivery order of the plurality of delivery orders."
  ],
  "description_excerpt": "This invention relates generally to optimizing the assignment of tasks to agents in a delivery system. Some embodiments relate to allocation and re-allocation of delivery tasks to delivery agents, and other embodiments relate to allocation of orders among warehouses, picking agents, and delivery agents in a delivery system. In current delivery systems, shoppers fulfill orders at a physical retailer on behalf of customers, as part of an online shopping concierge service. The online shopping concierge system assigns to shoppers various tasks involved in completing the orders, such as driving to a particular store, collecting one or more items at the store, purchasing the items, and delivering the items to a customer. In some cases, the online shopping concierge service assigns different tasks to different shoppers. For example, the online shopping concierge service can assign one shopper to collect and purchase the items, and assign a second shopper to drive to the store to pick up and deliver the purchased items. Thus, a single order is handed off from the in-store shopper to the delivery driver. Because of variations in the amount of time that it will take the in-store shopper to collect and purchase the items and variations in the amount of time that it will take the delivery driver to get to the store, the assignments of deliveries to the drivers determined by the online shopping concierge service may become sub-optimal before a delivery driver arrives at the store.",
  "cpc": [
    "G08G 1/20",
    "B65G 1/0492",
    "B65G 1/1373",
    "G01C 21/34",
    "G05D 1/0217",
    "G05D 1/0291",
    "G05D 1/644",
    "G05D 1/69",
    "G06Q 10/063116",
    "G06Q 10/0833",
    "G06Q 10/087",
    "G06Q 20/322",
    "G06Q 30/0635"
  ],
  "ipc": [
    "B65G 1/04",
    "B65G 1/137",
    "G01C 21/34",
    "G05D 1/00",
    "G06Q 10/0631",
    "G06Q 10/0833",
    "G06Q 10/087",
    "G06Q 20/32",
    "G06Q 30/0601",
    "G08G 1/00"
  ],
  "assignees": [
    "MAPLEBEAR INC"
  ],
  "inventors": [
    "RIPERT MATHIEU",
    "PUTREVU JAGANNATH",
    "TIRUMALASETTY DEEPAK",
    "SUBRAMANIAN BALA",
    "KANE ANDREW"
  ],
  "filing_date": "2023-01-03",
  "publication_date": "2024-11-19",
  "grant_date": "2024-11-19",
  "priority_date": "2017-10-18",
  "application_number": "US-202318149652-A",
  "family_id": "66097500",
  "citations": [
    "US10115067B2",
    "US10909490B2",
    "US2002133387A1",
    "US2002138358A1",
    "US2002143669A1",
    "US2003171962A1",
    "US2004054592A1",
    "US2004210621A1",
    "US2007040026A1",
    "US2010089997A1",
    "US2011040655A1",
    "US2011173034A1",
    "US2012156337A1",
    "US2012185356A1",
    "US2013090965A1",
    "US2014075004A1",
    "US2015039450A1",
    "US2015207278A1",
    "US2015307278A1",
    "US2016117627A1",
    "US2016304281A1",
    "US2017178070A1",
    "US2017193425A1",
    "US7096189B1",
    "US7212976B2",
    "US7295990B1",
    "US7725366B1",
    "US7747543B1",
    "US7751928B1",
    "US7774243B1",
    "US8117086B1",
    "US8620707B1",
    "US9120622B1",
    "US9466045B1",
    "US9740999B2"
  ]
}