Pipeline optimizer system

• US 7,643,974 B2
• Filed: 04/12/2006
• Issued: 01/05/2010
• Est. Priority Date: 04/22/2005
• Status: Active Grant

• Current Assignee: Air Liquide Large Industries U S LP (L'Air Liquide SA)
• Original Assignee: Air Liquide Large Industries U S LP (L'Air Liquide SA)
• Inventors: Boczon, Michael T., Harper, Charles N.
• Primary Examiner(s): Rodriguez; Paul L
• Assistant Examiner(s): Thangavelu; Kandasamy
• Application Number:
  US11/279,554
• Publication Number:
  US 20060241924A1
• Time in Patent Office: 1,364 Days
• Field of Search: 703/7, 703/6, 703/9, 703/13, 702/32, 713/401, 435/6, 406/12, 707/200, 717/104, 709/223
• US Class Current: 703/7
• CPC Class Codes: F17D 3/00 Arrangements for supervising or controlling working operations
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

One embodiment of the invention provides a method for optimizing a variety of aspects of pipeline operations by using a genetic algorithm. Generally, the genetic algorithm is used to evolve a population of feasible solutions over successive generations until a termination condition is satisfied. Each solution specifies a feasible operational state of the pipeline system. Over successive generations existing solutions are modified, and an identified solution in the population is removed at each successive generation. Over repeated generations, the solutions in the population improve. Once an optimized production solution is generated, an optimized pressure solution may be generated using a direct pressure optimization process.

Claims

1. A computer-implemented method of optimizing operation of a pipeline system, comprising:

executing instructions on one or more computer processors to perform operations, comprising;

a) reading input data, wherein the input data describes the pipeline system;

b) generating a population of solutions, wherein each solution in the population specifies a feasible operational state for the pipeline system;

c) evaluating an expected performance of each solution in the population and sorting the solutions in the population according to the evaluations;

d) performing a genetic algorithm optimization process on the population of solutions until a termination condition specified by the input data is satisfied, whereby a plurality of optimized production solutions is generated;

e) after the genetic algorithm optimization process is performed, selecting an optimized production solution from the plurality of optimized production solutions, wherein the selected optimized production solution has a highest evaluation, relative to the evaluations of other solutions in the population; and

f) generating an optimized pressure solution specifying an output pressure for one or more delivery points of the pipeline system and an input pressure for one or more production nodes of the pipeline system, for the selected optimized production solution, using a direct pressure optimization process to change pressures of some pipeline elements, wherein the direct pressure optimization is performed by;

calculating flows thorough a plurality of elements and nodes of the pipeline system;

determining and propagating pressures at the plurality of nodes;

generating a pressure dependency graph and using it to compute generalized pressure gap and minimum pressure for each sub network;

reducing pressures of high pressure nodes where possible;

propagating the pressures through the nodes of each sub network; and

recalculating at least one unknown parameter of the elements of each sub network.

2. The method of claim 1, wherein performing the genetic algorithm optimization process comprises:

a) modifying at least one solution in the population by modifying at least one aspect of the feasible operational state specified by the at least one solution;

b) simulating the operation of the pipeline system, according to the feasible operational state specified by the modified solution;

c) evaluating an expected performance of the modified solution;

d) adding the modified solution to the population; and

e) removing a solution from the population with a poorest evaluation, relative to the evaluations of other solutions in the population.

3. The method of claim 2, wherein modifying the at least one aspect of the feasible operational state specified by the at least one solution in the population, comprises:

a) selecting a solution modification technique;

b) selecting the at least one solution from the population to modify; and

c) modifying the at least one solution, according to the selected solution modification technique.

4. The method of claim 3, wherein the solution modification technique randomly modifies the least one aspect of the feasible operational state specified by the at least one solution.

5. The method of claim 3, wherein the solution modification technique modifies the at least one solution according to a heuristic rule.

6. The method of claim 3, wherein the solution modification technique cross-breeds two or more solutions to generate the modified solution.

7. The method of claim 1, wherein modifying the at least one aspect of the feasible operational state specified by the at least one solution in the population, comprises probabilistically selecting one or more solutions, wherein a solution with a superior evaluation is more likely to be selected for modification than a solution with an inferior evaluation.

8. The method of claim 1, further comprising,

validating that the input data describes a feasible pipeline system, according to a set of constraints.

9. The method of claim 1, wherein the termination condition specified by the input data includes at least one of a maximum number of solutions generated, a maximum amount of time spent, a maximum number of generations, and a generation of a solution that exceeds a specified evaluation threshold.

10. The method of claim 1, wherein generating the population of solutions comprises:

generating a first group of solutions and a second group of solutions, wherein the first group of solutions is generated according to heuristic rules, and wherein the second group of solutions is generated using a random process; and

combining the first group of solutions and the second group of solutions to form the generated population of solutions.

11. The method of claim 1, wherein the input data comprises at least one extensible markup language (XML) document.

12. The method of claim 1, wherein the input data is retrieved from a pipeline status database that stores a current operational state of the pipeline system.

13. A computer-readable storage medium containing a program which, when executed, performs a method for optimizing operation of a pipeline system, the computer-readable storage medium comprising instructions for:

a) reading input data, wherein the input data describes the pipeline system to be optimized;

b) generating a population of solutions, wherein each solution in the population specifies a feasible operational state for the pipeline system;

c) evaluating an expected performance of each solution in the population and sorting the solutions in the population according to the evaluation;

d) performing a genetic algorithm optimization process on the population until a termination condition specified by the input data is satisfied, whereby a plurality of optimized production solutions is generated;

e) after the genetic algorithm optimization process is performed, selecting an optimized production solution from the plurality of optimized production solutions, wherein the selected optimized production solution has a highest evaluation, relative to the evaluations of other solutions in the population;

f) generating, for the selected optimized production solution, an optimized pressure solution specifying an output pressure for one or more delivery points of the pipeline system and an input pressure for one or more production nodes of the pipeline system, using a direct pressure optimization process to change pressures of some pipeline elements, wherein the direct pressure optimization is performed by;

calculating flows thorough a plurality of elements and nodes of the pipeline system;

determining and propagating pressures at the plurality of nodes;

generating a pressure dependency graph and using it to compute generalized pressure gap and minimum pressure for each sub network;

reducing pressures of high pressure nodes where possible;

propagating the pressures through the nodes of each sub network; and

recalculating at least one unknown parameter of the elements of each sub network.

14. The computer-readable storage medium of claim 13, wherein performing the genetic algorithm optimization process, comprises:

a) modifying at least one solution in the population by modifying at least one aspect of the feasible operational state specified by the at least one solution;

b) simulating the operation of the pipeline system, according to the feasible operational state specified by the modified solution;

c) evaluating an expected performance of the modified solution;

d) adding the modified solution to the population; and

e) removing a solution from the population with a poorest evaluation, relative to the evaluations of other solutions in the population.

15. The computer-readable storage medium of claim 14, wherein modifying the at least one aspect of the feasible operational state specified by the at least one solution in the population, comprises:

a) selecting a solution modification technique;

b) selecting the at least one solution from the population to modify; and

c) modifying the at least one solution, according to the selected solution modification technique.

16. The computer-readable storage medium of claim 15, wherein the solution modification technique randomly modifies the least one aspect of the feasible operational state specified by the at least one solution.

17. The computer-readable storage medium of claim 15, wherein the solution modification technique modifies the at least one solution according to a heuristic rule.

18. The computer-readable storage medium of claim 15, wherein the solution modification technique cross-breeds two or more solutions to generate the modified solution.

19. The computer-readable storage medium of claim 13, wherein modifying the at least one aspect of the feasible operational state specified by the at least one solution in the population, comprises probabilistically selecting one or more solutions, wherein a solution with a superior evaluation is more likely to be selected for modification than a solution with an inferior evaluation.

20. The computer-readable storage medium of claim 13, wherein the method further comprises, validating that the input data describes a feasible pipeline system, according to a set of hard constraints.

21. The computer-readable storage medium of claim 13, wherein the termination condition specified by the input data includes at least one of a maximum number of solutions generated, a maximum amount of time spent, a maximum number of generations, and a generation of a solution that exceeds a specified evaluation threshold.

22. The computer-readable storage medium of claim 13, wherein generating the population of solutions comprises:

generating a first group of solutions and a second group of solutions, wherein the first group of solutions is generated according to heuristic rules, and wherein the second group of solutions is generated using a random process; and

combining the first group of solutions and the second group of solutions to form the generated population of solutions.

23. The computer-readable storage medium of claim 13, wherein the input data comprises at least one extensible markup language (XML) document.

24. The computer-readable storage medium of claim 13, wherein the input data is retrieved from a pipeline status database that stores a current operational state of the pipeline system.

25. A system for optimizing the operation of a pipeline system, comprising:

a) a processor; and

b) an optimization program, which when executed by the processor, is configured to;

i) read input data, wherein the input data describes the pipeline system to be optimized;

ii) generate a population of solutions, wherein each solution in the population specifies a feasible operational state for the pipeline system;

iii) evaluate an expected performance of each solution in the population of solutions and sort the solutions in the population according to the evaluations;

iv) perform a genetic algorithm optimization process on the population until a termination condition specified by the input data is satisfied, whereby a plurality of optimized production solutions is generated;

v) after the genetic algorithm optimization process is performed, selecting an optimized production solution from the plurality of optimized production solutions, wherein the selected optimized production solution has a highest evaluation, relative to the evaluations of other solutions in the population; and

vi) generate, for the selected optimized production solution, an optimized pressure solution specifying an output pressure for one or more delivery points of the pipeline system and an input pressure for one or more production nodes of the pipeline system, using a direct pressure optimization process to change pressures of some pipeline elements, wherein the direct pressure optimization is performed by;

calculating flows thorough a plurality of elements and nodes of the pipeline system;

determining and propagating pressures at the plurality of nodes;

generating a pressure dependency graph and using it to compute generalized pressure gap and minimum pressure for each sub network;

reducing pressures of high pressure nodes where possible;

propagating the pressures through the nodes of each sub network; and

recalculating at least one unknown parameter of the elements of each sub network.

26. The system of claim 25, wherein the optimization program is configured to perform the genetic algorithm optimization process by:

a) modifying at least one solution in the population by modifying at least one aspect of the feasible operational state specified by the at least one solution;

b) simulating the operation of the pipeline system, according to the feasible operational state specified by the modified solution;

c) evaluating an expected performance of the modified solution;

d) adding the modified solution to the population; and

e) removing a solution from the population with a poorest evaluation, relative to the evaluations of other solutions in the population.

27. The system of claim 26, wherein the optimization program is configured to modify the at least one aspect of the feasible operational state specified by the at least one solution in the population by performing the steps of:

a) selecting a solution modification technique;

b) selecting the at least one solution from the population to modify; and

c) modifying the at least one solution, according to the selected solution modification technique.

28. The system of claim 27, wherein the solution modification technique randomly modifies the least one aspect of the feasible operational state specified by the at least one solution.

29. The system of claim 27, wherein the solution modification technique modifies the at least one solution according to a heuristic rule.

30. The system of claim 27, wherein the solution modification technique cross-breeds two or more solutions to generate the modified solution.

31. The system of claim 25, wherein modifying the at least one aspect of the feasible operational state specified by the at least one solution in the population, comprises probabilistically selecting one or more solutions, wherein a solution with a superior evaluation is more likely to be selected for modification than a solution with an inferior evaluation.

32. The system of claim 25, wherein the termination conditions specified by the input data include at least one of a maximum number of solutions generated, a maximum amount of time spent, a maximum number of generations, and a generation of a solution that exceeds a specified evaluation threshold.

33. The system of claim 25, wherein the optimization program is configured to generate the population of solutions by:

generating a first group of solutions and a second group of solutions, wherein the first group of solutions is generated according to heuristic rules and wherein the second group of solutions is generated using a random process; and

combining the first group of solutions and the second group of solutions to form the generated population of solutions.

34. The system of claim 25, wherein the input data is retrieved from a pipeline status database that stores a current operational state of the pipeline system.

35. A computer-implemented method of optimizing operations of a pipeline system, comprising:

a) generating, using a computer, an optimized production solution for a production of material supplied to the pipeline system using a genetic algorithm optimization technique to optimize a population of seed solutions; and

b) generating, using the computer, an optimized pressure solution specifying an output pressure present at one or more delivery points of the pipeline system and an input pressure to generate at one or more production nodes of the pipeline system, for the generated optimized production solution using a direct pressure optimization technique to change pressures of some pipeline elements, wherein the direct pressure optimization is performed by;

calculating flows thorough a plurality of elements and nodes of the pipeline system;

determining and propagating pressures at the plurality of nodes;

generating a pressure dependency graph and using it to compute generalized pressure gap and minimum pressure for each sub network;

reducing pressures of high pressure nodes where possible;

propagating the pressures through the nodes of each sub network; and

recalculating at least one unknown parameter of the elements of each sub network.

36. The method of claim 35, wherein the output pressures are within a required minimal delivery pressure for each respective delivery point and wherein the input pressures are within a maximal input pressure allowed for each respective production node of the pipeline system.

37. The method of claim 35, wherein generating an optimized production solution for the production of material included in the pipeline system, comprises:

a) reading input data, wherein the input data describes the pipeline system to be optimized;

b) generating a population of solutions, wherein each solution in the population specifies a feasible operational state for the pipeline system;

c) evaluating an expected performance of each solution in the population and sorting the solutions in the population according to the evaluation;

d) performing a genetic algorithm optimization process on the population until a termination condition specified by the input data is satisfied, whereby a plurality of optimized production solutions is selected; and

e) after the genetic algorithm optimization process is performed, generating an optimized production solution from the selected plurality of optimized production solutions, wherein the generated optimized production solution has a highest evaluation, relative to the evaluations of other solutions in the population.

38. The method of claim 37, wherein performing the genetic algorithm optimization technique comprises:

a) modifying at least one solution in the population by modifying at least one aspect of the feasible operational state specified by the at least one solution;

b) simulating the operation of the pipeline system, according to the feasible operational state specified by the modified solution;

c) evaluating an expected performance of the modified solution;

d) adding the modified solution to the population; and

e) removing a solution from the population with a poorest evaluation, relative to the evaluations of other solutions in the population.

39. The method of claim 38, wherein modifying the at least one aspect of the at least one solution in the population, comprises:

a) selecting a solution modification technique;

b) selecting the at least one solution from the population to modify; and

c) modifying the at least one solution, according to the selected solution modification technique,

wherein the selected solution modification technique either randomly modifies the least one aspect of the feasible operational state specified by the at least one solution or modifies the at least one solution according to a heuristic rule or cross-breeds two or more solutions to generate the modified solution.