Friday, March 24, 2023
1 change · master
New functionality added to Odoo
Inventory picking can now prioritize using the smallest number of packages needed to fulfill a request. This helps warehouse teams reduce unnecessary unpacking, streamline logistics work, and keep packaged stock intact when possible.
Original PR description
[IMP] stock: add least_packages retrieval strategy ## Proposed feature and relevance Add a new retrieval strategy for gathering products: "Least packages". The goal of this strategy is to select…
[IMP] stock: add least_packages retrieval strategy ## Proposed feature and relevance Add a new retrieval strategy for gathering products: "Least packages". The goal of this strategy is to select specific product quantities from stock by using as few packages as possible, to allow for efficient logistics operations and avoid unnecessary opening/unpacking of packages. This strategy will behave as follows: - In case a negative quantity is requested this strategy will behave as a FIFO strategy. - Otherwise, the strategy will determine a combination using the least amount of packages that sum to the requested quantity, and adapt the provided domain to select only the quantities in these packages. This way no packages need to be opened to select the requested quantity. - In case an exact matching of current packages to get the requested quantity is not possible, a selection of packages is made where the largest packages are selected one by one until the requested quantity is reached, or until no more quantities are available. For this approach, one package needs to be unpacked as it will not be used completely. The final selected package that will be unpacked will be the smallest one possible, to try to unpack smaller packages over bigger packages. - In case the search for a minimal matching of packages results in an out-of-memory situation, the strategy will fall back to a FIFO strategy. - Loose items (not tied to a package) are considered as single-item packages for the purposes of package selection. **NOTE:** To force the selection strategy to "clean up" certain packages that have previously been opened, it is recommended to unpack these packages into single items, as they will then be consumed to "fill up" requested quantities in later retrievals. ## Changes to allow more complex strategies To allow for the integration of this new strategy the structure of `_gather()` needed to be adapted to allow a removal strategy to provide not only the SQL `ORDER BY` string but also adapt the domain used to retrieve the requested quantities. This change is reflected in the method signature of `_get_removal_strategy_domain_order()`. ## How the strategy works The strategy does one extra query of the database, to determine the different packages and their respective quantities (using the provided domain). Loose items (that do not belong to a package) are added as single-item packages to also consider them. For minimal exact package selection, an A* algorithm is used with 2 performance modifications: - Using the information that the packages are sorted by size (large -> small). - Using the information that the generated subtree for a specific package of size x is the same as all other packages of size x at a specific node. By using the A* algorithm, as soon as a matching packaging selection is found, it is ensured to be optimal and other combinations do not need to be considered. In case the A* algorithm runs out of memory the provided domain is just returned, which equates to a FIFO strategy. In case the A* algorithm does not find an exact matching of packages for the requested quantity, a selection is made using the least amount of packages, unpacking the smallest possible package (or until no more quantities are available, in which case effectively all quantities in the domain are returned). ## Used heuristic The heuristic used for the A* algorithm exploits the knowledge that our packages to select from are ordered by the highest to the lowest quantity (on the database side, SQL `ORDER BY`). It assumes the "best case scenario" as an estimate for the amount of packages remaining, which is if we were to "match" the required quantity using fractional multiples of the next biggest package size. ***Example**: Remaining quantity to select: 27 Remaining package sizes to select from: [10, 10, 5, 5, 5, 1, 1, 1] Heuristic for choosing package with qty 10 as next package: 27/10 = 2.7 Heuristic for choosing package with qty 5 as next package: 27/5 = 5.4 Heuristic for choosing package with qty 1 as next package: 27/1 = 27* This way the heuristic is always a "best case" (fractional) for the amount of packages that still need to be selected. As required by the A* algorithm this also results in an underestimation as the fractional result is not possible, and it is not certain that there are still enough packages of this size that can actually be selected, but favours larger packages to make the search converge more quickly. ## Performance ### CPU Two test cases were run to evaluate the performance. ***Total nr of pkg**: The total amount of different packages generated during data generation **Qty to select**: The total quantity that needs to be selected **Selected nr of pkg**: The amount of packages that was ultimately selected by the algorithm **Data generation time**: The time required to generate all packages **Assignment time**: The total time to run `_action_assign()` for the move **A\* time**: The time to run the `_run_least_packages_removal_strategy_astar()` method* #### First test case This scenario simulates a case with a large quantity to select from a large amount of packages, but of relatively homogenous size. Generate 30 different package sizes between 2 and 1000. For each package size, generate 100 to 250 packages each. Also add 100 to 250 "loose items". The quantity to select is chosen between 1 and 50000. | RESULTS | RUN 1 | RUN 2 | RUN 3 | RUN 4 | RUN 5 | AVG | |--------------------------|----------|-----------|------------|-----------|----------|------------| | Total nr of pkg | 5298 | 5772 | 5855 | 5533 | 5179 | 5527.4 | | Qty to select | 10319 | 20762 | 44422 | 39306 | 1783 | 23318.4 | | Selected nr of pkg | 11 | 22 | 48 | 41 | 3 | 25 | | Data generation time (s) | 64.59124 | 92.916682 | 133.673384 | 82.711438 | 85.54542 | 91.8876328 | | Assignment time (s) | 4.060216 | 11.212937 | 4.763776 | 8.60248 | 3.461941 | 6.42027 | | A* time (s) | 0.28 | 6.88 | 0.21 | 3.96 | 0.03 | 2.272 | #### Second test case This scenario generates a large amount of small packages of different sizes. Generate 250 different package sizes between 2 and 10. For each package size, generate 5 to 15 packages each. Also add 5 to 15 "loose items". The quantity to select is chosen between 1 and 10000. | RESULTS | RUN 1 | RUN 2 | RUN 3 | RUN 4 | RUN 5 | AVG | |--------------------------|-----------|-----------|-----------|-----------|----------|------------| | Total nr of pkg | 2485 | 2406 | 2491 | 2555 | 2542 | 2495.8 | | Amount to assign | 27 | 4029 | 3966 | 3049 | 1833 | 2580.8 | | Selected nr of pkg | 3 | 411 | 411 | 306 | 184 | 263 | | Data generation time (s) | 18.502933 | 18.692048 | 19.969955 | 19.169106 | 19.16439 | 19.0996864 | | Assignment time (s) | 1.35635 | 7.958852 | 8.470518 | 6.300406 | 3.895457 | 5.5963166 | | A* time (s) | 0.01 | 0.07 | 0.77 | 0.56 | 0.31 | 0.344 | ### Memory In cases with large amounts of different-sized packages (200+ different sizes and 200+ packages required to get an exact match) the memory performance of the A* strategy might become problematic. When lots of packages have the same size (which would be considered typical in cases where there are large amounts of packages) the specific modifications to the A* algorithm ensure that the strategy still delivers good memory performance for this use case as the tree size can be significantly reduced, even with large quantities. ### IO This strategy only requires one extra SQL query to fetch the different quantities and their respective packages. ## Limitations No tests for this strategy were done for non-integer quantities. In these cases the performance of the A* algorithm might not be satisfactory and another approach might be preferred. More research could be done for specific use cases where packaged quantities are non-integer values.