Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Operations research or analysis
Reexamination Certificate
1998-12-03
2002-01-22
Hafiz, Tariq R. (Department: 2163)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Operations research or analysis
C705S002000
Reexamination Certificate
active
06341266
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methodology for optimization of transportation planning by linear programming, and more particularly, to maximization of the range of coverage profiles for a multiple level transportation network by use of an optimization algorithm to determine shipment and production schedules.
BACKGROUND OF THE INVENTION
A need for allocation of inventory and transportation resources arises in a broad range of industrial areas related to manufacturing and distribution. These allocation decisions are typically subject to constraints such as limitations on equipment, time, cost, storage capacity and other parameters affecting the outcome of a distribution process. As an example of the particular interest herein, there is a need to optimize the distribution and inventory levels of a supply chain where there are multiple production facilities with multiple distribution centers located strategically near customers.
Resource allocation decisions are typically subject to constraints on such allocations. Resources are always limited in overall availability, and, furthermore, the usefulness of a particular resource in some particular application may also be limited. For example, the traffic-carrying capacity of each individual link in a telecommunications system is limited, while the overall traffic offered to the communications system is also limited. Each particular allocation of resources can be associated with a “payoff,” i.e., a cost of that allocation or an allocation benefit. The problem, then, is to allocate the resources so as to satisfy all of the constraints and, simultaneously, to maximize the payoff, i.e. minimize the costs or maximize the benefits.
One method of representing such allocation decision problems is known as the linear programming model. Such a model consists of a number of linear relationships set forth in a matrix format, representing quantitatively the relationships among allocations, constraints and the results of the process. In the linear relationships, there is provided the sum of constant coefficients multiplied by unknown allocation values. While many resource allocation problems are not normally represented by such linear relationships, the optimization of transportation processes is still treated as a linear model. Such modeling of linear programming is accomplished in multidimensional space with multidimensional vectors providing a multidimensional figure, or polytope, wherein each facet on a surface thereof is bounded by equations defining relationships among allocated resources in the process. As an example, an optimal solution to the linear programming problem has been obtained by use of the simplex algorithm developed by George Dantzig in 1947, or by the more recent Karmarkar algorithm. There a number of optimization algorithms that are available to solve minimum-cost flow network problems.
Network flow problems are a special case of linear programming. As mentioned before, Dantzig described an efficient polynomial algorithm for solving the minimum-cost flow problem. Although, in 1984, Karmarkar published an efficient polynomial time algorithm for linear programming, the algorithms for the special case of network flow remain much faster.
Network flow algorithms have many applications in industrial planning problems. For example, they can be used in assignment, transportation, minimum-cost flow, shortest path, and maximum flow through network problems. In assignment problems, there is a bipartite graph consisting of a set of productive nodes and consumptive nodes (for example, workers and tasks). The arcs between the workers and tasks are weighted by costs for assigning the worker with the task. The optimization problem in this scenario is the assignment of one task to each worker such that the overall costs are minimized. In transportation problems, there is a bipartite graph where the productive and consumptive nodes are plants and distribution centers. Each plant produce units and each distribution center has a demand for said units. The arcs between plants and the distribution centers are weighted by costs for transporting the units. In this case, the optimization problem is to minimize the transportation costs with the constraint that all demands in the distribution centers be fulfilled. The minimum-cost flow problem is merely the transportation problem with intermediate nodes in the network. Additionally, the arcs may have minimal and maximal capacity. In the shortest path problem, you have a graph with positively weighted arcs. The optimization problem is to find the shortest path between two given nodes in the transportation network. The maximum flow through a network problem is similar to the transportation problem except that the arcs between the nodes have limited transportation capacities but no transportation costs. The optimization problem is to get a maximum flow transported through the network without violating the transport capacities.
However, in the prior art, network flow problems have been limited to networks with nodes and arcs between them, where flow is penalized linearly by transportation costs between them. There is a need for a network flow solution where the minimization of the transportation costs has a lower priority and where maximization of the range of coverage of profiles in the consumption nodes is of primary importance. This problem cannot be formulated as in the prior art as a linear optimization problem or even a network flow problem.
BRIEF SUMMARY OF THE INVENTION
The objective of this invention is to implement a new algorithm for the maximization of the range of coverage profiles in the deployment problem which arises in industrial production planning systems. Several algorithms designed to be applicable to this problem are proposed. The decision on which one is appropriate for a given deployment problem depends on the problem size and the acceptable CPU-time for the computation. This invention proposes a new formulation of the network flow problem takes into account different transport modes, calendar constraints, demand priorities, and fixed flows of production. The algorithmic function is then applied to this formulation. The objective of the algorithm is to select the free variables of the range profile formulation such that, first, the range of coverage profile is maximized and second, the transportation costs are minimized. The proposed algorithm can use any minimum-cost flow algorithm as a basic building block.
REFERENCES:
patent: 5712985 (1998-01-01), Lee et al.
patent: 5797113 (1998-08-01), Kambe et al.
patent: 5819232 (1998-10-01), Shipman
patent: 196 12 652 (1997-03-01), None
Loren P. Rees et al, “A Linear Goal Programming Model of a Multi-Period, Multi-Commodity Network Flow Problem”, Journal of Business Logistics, 1987, p. 117-138.*
James Orlin, “A Faster Strongly Polynomial Minimum Cost Flow Algorithm”, Proceedings of the 1988 Twentieth Annual ACM Symposium on Theory of Computing, May 1988, p. 377-387.*
Andrew Goldberg et al, “Solving Minimum-Cost Flow Problems by Successive Approximation”, The Nineteenth Annual ACM Conference on Theory of Computing, May 1987, p. 7-18.*
Andrew Goldberg, “Scaling Algorithms for the Shortest Paths Problems”, Proceedings of the ACM-SIAM Symposium of Discrete Algorithms, Jan. 1993, p. 222-231.*
Andrew V. Goldberg et al, “An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow”, NECI Technical Report 98-038, Apr. 1998, p. 1-16.*
ILOG Press Release, Jan. 5, 1998, “Manugistics Extends Partnership with ILOG for Supply Chain Management”.*
ILOG Press Release, Feb. 12, 1998, “ILOG Planner 2.2 Joins ILOG and CPLEX Expertise”.*
ILOG Press Release, Apr. 27, 1998, “ILOG's CPLEX 6.0 Delivers Significant Performance Improvements”.*
Konstantin Kogan et al. “Optimal flow control of flexible manufacturing systems: Setup locationization by an iterative procedure”, International Journal of Production Economics, Aug. 15, 1997, p. 37-46.
Chadbourne & Parke LLP
Hafiz Tariq R.
Norman Marc
SAP Aktiengesellschaft
LandOfFree
Method and system for the maximization of the range of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for the maximization of the range of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for the maximization of the range of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2863911