# US 12,217,203 B2 · Picking sequence optimization within a warehouse for an item list > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,217,203 B2 - Document ID: US12217203B2 - Status: Granted - Kind: B2 - Application number: 18/235,230 - Filed: 2023-08-17 - Published: 2023-12-07 - Granted: 2025-02-04 - Earliest claimed: 2021-08-26 - Assignees: Maplebear Inc. - Applicants: Maplebear Inc. - Inventors: Xinyu Li; Haixun Wang; Ruoming Jin - Web page: https://patentgrep.com/patent/US12217203B2 ## CPC - G06Q 10/06316: {Sequencing of tasks or work} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem - G06Q 10/087: Inventory or stock management, e.g. order filling, procurement or balancing against orders - G06Q 10/08743: {using optimisation of routes} - G06Q 30/0633: {Managing shopping lists, e.g. compiling or processing purchase lists (shipping orders G06Q10/083; order filling G06Q10/087)} - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An online concierge system receives a delivery order containing a list of items, generates a suggested picking sequence for picking the delivery order in a warehouse, and transmits the suggested picking sequence to a mobile device of the shopper. Generating the suggested sequence includes applying a trained item sequence model to the delivery order. Training the item sequence model includes accessing data about a set of historical orders, determining a pairwise distance between each pair of aisles in the warehouse based on the data about the set of historical orders, and generating a distance graph based on the pairwise distance between each pair of aisles in the warehouse. The plurality of nodes represent a plurality of aisles in the warehouse, and the plurality of edges represent pairwise distances between pairs of aisles. ## Claims ### Claim 1 A computer-implemented method comprising: receiving, by an online concierge system including one or more processors, a delivery order from a device of a customer, the delivery order containing a list of items; generating, by the one or more processors, a suggested picking sequence for picking the delivery order in a warehouse, wherein generating the suggested picking sequence comprises applying a trained item sequence model to the delivery order, wherein the item sequence model is trained to generate the suggested picking sequence to minimize an amount of time a shopper would spend picking the list of items, and wherein training the item sequence model comprises: accessing data about a set of historical orders, wherein for each order in the set of historical orders, the data about the order comprises a duration between picking a first item in a first aisle and a second item in a second aisle in the order; determining a pairwise distance between each pair of aisles in the warehouse based on the data about the set of historical orders; generating a distance graph based on the pairwise distance between each pair of aisles in the warehouse, wherein the distance graph comprises a plurality of nodes and a plurality of edges, the plurality of nodes representing a plurality of aisles in the warehouse, and the plurality of edges representing pairwise distances between pairs of aisles; and training the item sequence model based in part on the distance graph; and transmitting, by the one or more processors, the suggested picking sequence to a mobile device of the shopper, wherein the transmitting causes the mobile device of the shopper to display the list of items in the suggested picking sequence. ### Claim 2 (depends on 1) The method of claim 1, wherein the pairwise distance is calculated by averaging durations between sequentially picked items for an aisle pair in the set of historical orders. ### Claim 3 (depends on 2) The method of claim 2, further comprising eliminating, by the online concierge system and prior to the averaging, a subset of the durations in response to the subset of durations being above or below a threshold. ### Claim 4 (depends on 1) The method of claim 1, generating the suggested picking sequence further comprising: traversing the nodes in the graph to generate a plurality of sequences for the delivery order; ranking the plurality of sequences. ### Claim 5 (depends on 1) The method of claim 1, wherein generating the suggested picking sequence comprises applying a traveling salesperson problem to items in historical orders in the graph. ### Claim 6 (depends on 1) The method of claim 1, wherein generating the suggested picking sequence comprises determining an aisle in the warehouse corresponding to each item in the delivery order. ### Claim 7 (depends on 1) The method of claim 1, further comprising recalculating, by the online concierge system, the suggested picking sequence based on a location of the mobile device within the warehouse. ### Claim 8 (depends on 1) The method of claim 1, further comprising: generating a relative sequence for each of a plurality of delivery orders; and generating a global sequence preserving relative sequences of the plurality of delivery orders. ### Claim 9 A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by one or more processors of an online concierge system, cause the processor to: receive, by the online concierge system, a delivery order from a device of a customer, the delivery order containing a list of items; generate, by the one or more processors, a suggested picking sequence for picking the delivery order in a warehouse, wherein generating the suggested picking sequence comprises applying a trained item sequence model to the delivery order, wherein the item sequence model is trained to generate the suggested picking sequence to minimize an amount of time a shopper would spend picking the list of items, and wherein training the item sequence model comprises: access data about a set of historical orders, wherein for each order in the set of historical orders, the data about the order comprises a duration between picking a first item in a first aisle and a second item in a second aisle in the order; determine a pairwise distance between each pair of aisles in the warehouse based on the data about the set of historical orders; and generate a distance graph based on the pairwise distance between each pair of aisles in the warehouse, wherein the distance graph comprises a plurality of nodes and a plurality of edges, the plurality of nodes representing a plurality of aisles in the warehouse, and the plurality of edges representing pairwise distances between pairs of aisles; and train the item sequence model based in part on the distance graph; and transmit, by the one or more processors, the suggested picking sequence to a mobile device of the shopper, wherein the transmitting causes the mobile device of the shopper to display the list of items in the suggested picking sequence. ### Claim 10 (depends on 9) The computer program product of claim 9, wherein the pairwise distance is calculated by averaging durations between sequentially picked items for an aisle pair in the set of historical orders. ### Claim 11 (depends on 10) The computer program product of claim 10, wherein the instructions further cause the processor to eliminate, by the online concierge system and prior to the averaging, a subset of the durations in response to the subset of durations being above or below a threshold. ### Claim 12 (depends on 11) The computer program product of claim 11, wherein the instructions further cause the processor to eliminate, prior to the averaging, a subset of the durations in response to the subset of durations being above or below a threshold. ### Claim 13 (depends on 9) The computer program product of claim 9, generating the suggested picking sequence further comprising: traversing the nodes in the graph to generate a plurality of sequences for the delivery order; ranking the plurality of sequences. ### Claim 14 (depends on 9) The computer program product of claim 9, generating the suggested picking sequence comprises applying a traveling salesperson problem to items in historical orders in the graph. ### Claim 15 (depends on 9) The computer program product of claim 9, wherein generating the suggested picking sequence comprises determining an aisle in the warehouse corresponding to each item in the delivery order. ### Claim 16 (depends on 9) The computer program product of claim 9, wherein the instructions further cause the processor to recalculate the suggested picking sequence based on a location of the mobile device within the warehouse. ### Claim 17 (depends on 9) The computer program product of claim 9, wherein the instructions further cause the processor to: generate a relative sequence for each of a plurality of delivery orders; and generate a global sequence preserving relative sequences of the plurality of delivery orders. ### Claim 18 A computer system comprising: a processor; and a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to: receive, by an online concierge system, a delivery order from a device of a customer, the delivery order containing a list of items; generate, by the online concierge system, a suggested picking sequence for picking the delivery order in a warehouse, wherein generating the suggested picking sequence comprises applying a trained item sequence model to the delivery order, wherein the item sequence model is trained to generate the suggested picking sequence to minimize an amount of time a shopper would spend picking the list of items, and wherein training the item sequence model comprises: access data about a set of historical orders, wherein for each order in the set of historical orders, the data about the order comprises a duration between picking a first item in a first aisle and a second item in a second aisle in the order; determine a pairwise distance between each pair of aisles in the warehouse based on the data about the set of historical orders; and generate a distance graph based on the pairwise distance between each pair of aisles in the warehouse, wherein the distance graph comprises a plurality of nodes and a plurality of edges, the plurality of nodes representing a plurality of aisles in the warehouse, and the plurality of edges representing pairwise distances between pairs of aisles; and train the item sequence model based in part on the distance graph; and transmit, by the online concierge system, the suggested picking sequence to a mobile device of the shopper, wherein the transmitting causes the mobile device of the shopper to display the list of items in the suggested picking sequence. ### Claim 19 (depends on 18) The computer system of claim 18, wherein the pairwise distance is calculated by averaging durations between sequentially picked items for an aisle pair in the set of historical orders. ### Claim 20 (depends on 18) The computer system of claim 18, wherein the instructions further cause the processor to: generate a relative sequence for each of a plurality of delivery orders; and generate a global sequence preserving relative sequences of the plurality of delivery orders.