Divide-and-conquer framework and modularized algorithmic scheme for large-scale optimization

Patent metadata

Field	Value
Publication number	US-12505404-B2
Application number	US-202318103131-A
Country	US
Kind code	B2
Filing date	Jan 30, 2023
Priority date	Jan 30, 2023
Publication date	Dec 23, 2025
Grant date	Dec 23, 2025

Abstract

A method including obtaining an optimization request at a coordinating engine. The method also can include triggering engines to process the optimization request. At least one of the engines divides the optimization request into subproblems. At least a portion of the engines solve the subproblems. Respective instances of at least one of the engines are triggered to handle respective ones of the subproblems. Each of the engines provides a dynamic algorithmic flow using modularized algorithmic solvers. The dynamic algorithmic flow is adjusted based on a respective input to each of the engines. The method additionally can include outputting, from the coordinating engine, one or more results in response to the optimization request, based on results for the subproblems generated by the engines. Other embodiments are described.

First claim

What is claimed is:

1 . A system comprising:
a processor; and a non-transitory computer-readable medium storing computing instructions that, when executed on the processor, cause the processor to perform operations comprising:
obtaining an optimization request at a coordinating engine;
triggering multiple different engines to process the optimization request, wherein at least one of the multiple different engines divides the optimization request into subproblems, wherein at least two or more of the multiple different engines solve the subproblems in parallel and using data sharing, between the multiple different engines, based on data, stored in a data persistence system, that includes at least one of inputs, constraints, data structures, or outputs, wherein respective instances of the multiple different engines are triggered to handle respective different ones of the subproblems, wherein each of the multiple different engines provides a dynamic algorithmic flow using modularized algorithmic solvers, wherein the dynamic algorithmic flow is adjusted based on a respective input to each of the multiple different engines and based on a saved status of at least one of the multiple different engines by copying steps of the dynamic algorithmic flow from a previous run, wherein the dynamic algorithmic flow comprises each of the respective instances of the multiple different engines (i) selecting and sequencing multiple different ones of the modularized algorithmic solvers within each of the respective instances of the multiple different engines based on characteristics of the respective input to each of the respective instances of the multiple different engines and (ii) collecting results from the different ones of the modularized algorithmic solvers to select a respective result for each of the subproblems, and wherein each of the multiple different ones of the modularized algorithmic solvers perform a different function; and
outputting, from the coordinating engine, one or more overall results in response to the optimization request, based on the respective results for the subproblems generated by the multiple different engines, to cause a set of loads to be delivered on an inbound transportation network using respective carriers according to the one or more overall results output from the coordinating engine, wherein:
each of the multiple different engines uses a uniform IO data structure;
each of the multiple different engines is configured to import data from computer memory and to import data from external storage; and
the dynamic algorithmic flow provides a plug-and-play framework for adding other modularized algorithmic solvers to the respective instances of the multiple different engines to extend capabilities of the multiple different engines and allow the multiple different engines to scale dynamically.

2 . The system of claim 1 , wherein the multiple different engines comprise:
a partition engine; a routing engine; a picking engine; and a lane optimizer engine.

3 . The system of claim 2 , wherein:
the optimization request is for the inbound transportation network; and the partition engine divides the inbound transportation network into subnetworks.

4 . The system of claim 3 , wherein:
multiple instances of the routing engine are triggered; and each instance of the multiple instances of the routing engine is used for a different subnetwork of the subnetworks.

5 . The system of claim 4 , wherein the picking engine selects the set of loads from a combined pool of candidate loads generated by the multiple instances of the routing engine.

6 . The system of claim 5 , wherein the lane optimizer engine selects a carrier of the respective carriers for each load of the set of loads.

7 . The system of claim 1 , wherein:
the dynamic algorithmic flow is configurable to use recursion for one or more of the modularized algorithmic solvers.

8 . A computer-implemented method comprising:
obtaining an optimization request at a coordinating engine; triggering multiple different engines to process the optimization request, wherein at least one of the multiple different engines divides the optimization request into subproblems, wherein at least two or more of the multiple different engines solve the subproblems in parallel and using data sharing, between the multiple different engines, based on data, stored in a data persistence system, that includes at least one of inputs, constraints, data structures, or outputs, wherein respective instances of the multiple different engines are triggered to handle respective different ones of the subproblems, wherein each of the multiple different engines provides a dynamic algorithmic flow using modularized algorithmic solvers, wherein the dynamic algorithmic flow is adjusted based on a respective input to each of the multiple different engines and based on a saved status of at least one of the multiple different engines by copying steps of the dynamic algorithmic flow from a previous run, wherein the dynamic algorithmic flow comprises each of the respective instances of the multiple different engines (i) selecting and sequencing multiple different ones of the modularized algorithmic solvers within each of the respective instances of the multiple different engines based on characteristics of the respective input to each of the respective instances of the multiple different engines and (ii) collecting results from the different ones of the modularized algorithmic solvers to select a respective result for each of the subproblems, and wherein each of the multiple different ones of the modularized algorithmic solvers perform a different function; and outputting, from the coordinating engine, one or more overall results in response to the optimization request, based on the respective results for the subproblems generated by the multiple different engines, to cause a set of loads to be delivered on an inbound transportation network using respective carriers according to the one or more overall results output from the coordinating engine, wherein:
each of the multiple different engines uses a uniform IO data structure;
each of the multiple different engines is configured to import data from computer memory and to import data from external storage; and
the dynamic algorithmic flow provides a plug-and-play framework for adding other modularized algorithmic solvers to the respective instances of the multiple different engines to extend capabilities of the multiple different engines and allow the multiple different engines to scale dynamically.

9 . The computer-implemented method of claim 8 , wherein:
the dynamic algorithmic flow is configurable to use recursion for one or more of the modularized algorithmic solvers.

10 . The computer-implemented method of claim 8 , wherein the multiple different engines comprise:
a partition engine; a routing engine; a picking engine; and a lane optimizer engine.

11 . The computer-implemented method of claim 10 , wherein:
the optimization request is for the inbound transportation network; and the partition engine divides the inbound transportation network into subnetworks.

12 . The computer-implemented method of claim 11 , wherein:
multiple instances of the routing engine are triggered; and each instance of the multiple instances of the routing engine is used for a different subnetwork of the subnetworks.

13 . The computer-implemented method of claim 12 , wherein the picking engine selects the set of loads from a combined pool of candidate loads generated by the multiple instances of the routing engine.

14 . The computer-

Assignees

• Walmart Apollo Llc

Inventors

• Ni Ming
• Lian Kunlei
• Zheng Yu
• Zhang Liqing
• Zhang Ti
• Huang Jing
• Fu Mingang

Classifications

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G06Q10/087 Primary

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

• G06Q10/0834 Primary

  Choice of carriers · CPC title