Systems and methods for determining path solutions associated with a supply chain network

Patent metadata

Field	Value
Publication number	US-11769093-B2
Application number	US-202117219628-A
Country	US
Kind code	B2
Filing date	Mar 31, 2021
Priority date	Mar 31, 2021
Publication date	Sep 26, 2023
Grant date	Sep 26, 2023

Abstract

Input data comprises an order to provide a quantity of one or more finished goods to a site. Software is programmed for: accessing information that defines an architecture of a supply chain network comprising a plurality of sites connected by a plurality of path fragments; generating one or more path solutions to fulfill the order; removing one or more loops from the one or more path solutions; generating based on the one or more path solutions and the one or more removed loops, one or more revised path solutions; outputting the one or more revised path solutions for display on a client device; and transmitting, only to computers of the sites of a revised subset of a plurality of path fragments, a plurality of signals to initiate movement of one or more of raw materials or finished goods.

First claim

What is claimed is:

1. A computer-implemented method executed by a computing system, the method comprising:
receiving input data comprising an order to provide a quantity of one or more finished goods to a site through an acyclic supply chain network, the one or more finished goods each comprising one or more raw materials;
accessing information that defines an architecture of the acyclic supply chain network comprising a plurality of sites connected by a plurality of path fragments, wherein a path fragment defines a movement of a sub-quantity of the one or more finished goods or the one or more raw materials between two sites of the plurality of sites;
decomposing the acyclic supply chain network by generating one or more clusters of finished goods based on a raw material connection, wherein the raw material connection is based on a common raw material shared between two or more of the finished goods, and generating a sub-network for each of the one or more clusters of finished goods;
generating, based on the sub-networks, one or more path solutions to fulfill the order, wherein each path solution comprises an initial subset of the plurality of path fragments;
removing one or more invalid path fragments from the one or more path solutions, wherein an invalid path fragment is redundant or unnecessary to fulfill the order;
removing one or more loops from the one or more path solutions, wherein removing the one or more loops comprises removing one or more path fragments that comprises the subset of path fragments for each path solution that connect two or more sites of the plurality of sites in a circular manner by removing the one or more loops exclusively between two sites of the plurality of sites, detecting one or more elementary circuits in the one or more path solutions and removing the one or more elementary circuits by determining a quantity of elementary circuits associated with each path fragment of the initial subset of the plurality fragments for each path solution, and removing one or more path fragments associated with a largest quantity of elementary circuits from the one or more path solutions;
releasing computing memory associated with the one or more removed invalid path fragments, and the one or more removed loops;
generating, based on the one or more path solutions and the one or more removed loops, one or more revised path solutions each comprising a revised subset of the plurality of path fragments by adjusting the sub-quantity of the one or more finished goods or the one or more raw materials associated with one or more path fragments of the initial subset of path fragments for each path solution;
outputting the one or more revised path solutions for display on a client device; and
transmitting, only to computers of the sites of the revised subset of the plurality of path fragments of a first path represented in the one or more revised path solutions, a plurality of signals to initiate movement of one or more of the raw materials or finished goods in the acyclic supply chain network along the first path.

2. The method of claim 1 , each of the revised subset of path fragments being associated with a time to move the sub-quantity of the one or more finished goods or the one or more raw materials between the two sites.

3. The method of claim 2 , further comprising ranking the one or more revised path solutions, wherein the revised path solutions are ranked by summing the time associated with the revised subset of path fragments comprising each of the one or more revised path solutions.

4. The method of claim 2 , wherein the plurality of signals are transmitted to computers based on the time to move the sub-quantity of the one or more finished goods or the one or more raw materials between the two sites.

5. The method of claim 1 , wherein one or more of the generated sub-networks are associated with a first site of the plurality of sites.

6. The method of claim 1 , wherein removing the one or more loops exclusively between two sites of the plurality of sites comprises:
assigning a weight to each of the two sites in the exclusive loop; and
removing one or more path fragments originating from the site with a lowest weight.

7. The method of claim 1 , wherein the one or more elementary circuits are detected using a Greedy algorithm.

8. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
receive input data comprising an order to provide a quantity of one or more finished goods to a site through an acyclic supply chain network, the one or more finished goods each comprising one or more raw materials;
access information that defines an architecture of the acyclic supply chain network comprising a plurality of sites connected by a plurality of path fragments, wherein a path fragment defines a movement of a sub-quantity of the one or more finished goods or the one or more raw materials between two sites of the plurality of sites;
decompose the acyclic supply chain network by generating one or more clusters of finished goods based on a raw material connection, wherein the raw material connection is based on a common raw material shared between two or more of the finished goods, and generating a sub-network for each of the one or more clusters of finished goods;
generate, based on the sub-networks, one or more path solutions to fulfill the order, wherein each path solution comprises an initial subset of the plurality of path fragments;
remove one or more invalid path fragments from the one or more path solutions, wherein an invalid path fragment is redundant or unnecessary to fulfill the order;
remove one or more loops from the one or more path solutions, wherein removing the one or more loops comprises removing one or more path fragments that comprises the subset of path fragments for each path solution that connect two or more sites of the plurality of sites in a circular manner by removing one or more loops exclusively between two sites of the plurality of sites, detecting one or more elementary circuits in the one or more path solutions and removing the one or more elementary circuits by determining a quantity of elementary circuits associated with each path fragment of the initial subset of the plurality fragments for each path solution, and removing one or more path fragments associated with a largest quantity of elementary circuits from the one or more path solutions;
release computing memory associated with the one or more removed invalid path fragments, and the one or more removed loops;
generate, based on the one or more path solutions and the one or more removed loops, one or more revised path solutions each comprising a revised subset of the plurality of path fragments by adjusting the sub-quantity of the one or more finished goods or the one or more raw materials associated with one or more path fragments of the initial subset of path fragments for each path solution;
output the one or more revised path solutions for display on a client device; and
transmit, only to computers of the sites of the revised subset of the plurality of path fragments of a first path represented in the one or more revised path solutions, a plurality of signals to initiate movement of one or more of the raw materials or finished goods in the acyclic supply chain network along the first path.

9. The media of claim 8 , wherein one or more of the generated sub-networks are associated with a first site of the plurality of sites.

10. The media of claim 8 , wherein removing the one or more loops exclusively between two sites of the plurality of sites comprises:
assigning a weight to each of the two sites in the exclusive loop; and
removing one or more p

Assignees

• Coupa Software Inc

Inventors

• Ouyang Zheng
• Xu Yun

Classifications

• G06Q10/06315 Primary

  Needs-based resource requirements planning or analysis · CPC title

• G06Q10/04

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title

• G06Q10/06

  Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling · CPC title

• G06Q10/08 Primary

  Logistics, e.g. warehousing, loading or distribution; Inventory or stock management · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title