Robust optimization of bulk gas distribution

• US 8,762,291 B2
• Filed: 10/28/2010
• Issued: 06/24/2014
• Est. Priority Date: 06/14/2010
• Status: Expired due to Fees

• Current Assignee: L'Air Liquide Societe Anonyme Pour L'Etude et L'Exploitation Des Procedes Georges Claude (L'Air Liquide SA)
• Original Assignee: L'Air Liquide Societe Anonyme Pour L'Etude et L'Exploitation Des Procedes Georges Claude (L'Air Liquide SA)
• Inventors: Neagu, Nicoleta, Dubedout, Hugues
• Primary Examiner(s): EPSTEIN, BRIAN M
• Application Number:
  US12/914,241
• Publication Number:
  US 20110307407A1
• Time in Patent Office: 1,335 Days
• Field of Search: 705/332, 705/337, 705/7.26, 705/7.22, 705/7.12
• US Class Current: 705/337
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/083 Shipping

Abstract

Techniques are disclosed for increasing the robustness of optimization solutions for bulk gas distribution, relative to uncertain events such as unexpected plant outages. The techniques actively consider different assumptions regarding unexpected plant outages while searching for a solution (i.e., when generating a delivery schedule). A robust solution (delivery schedule) is one on which a plant outage only has a limited impact. A computer-implemented delivery scheduling application may identify a robust solution that performs well with respect to a range of uncertain future conditions (e.g., a variety of plant outages), at the lowest additional cost to the producer/distributor relative to other solutions.

Claims

1. A computer-implemented method for generating a robust delivery schedule for delivering a commodity product to a set of customers, the method comprising:

generating, by operation of at least one computer processor, one or more production outage scenarios based on historical production facility outage data, wherein each production outage scenario specifies a period of time during which a first one of one or more production facilities is presumed to be unavailable to produce the commodity product, wherein the commodity product comprises industrial gases delivered to a storage tank at each customer site via at least one delivery truck;

generating a set of solutions, wherein each solution specifies a delivery schedule for delivering the commodity product to the set of customers;

determining a cost for each solution relative to each generated scenario;

evaluating the cost of each solution according to a specified evaluation method to compute a robustness measure for each solution, wherein the robustness measure is determined based an expected change in the cost of the solution relative to the one or more production outage scenarios; and

returning, as the robust delivery schedule, a solution having a best determined cost versus robustness measure tradeoff, relative to other solutions in the generated set of solutions.

2. The method of claim, 1 further comprising, receiving a set of input data describing distribution requirements for delivering the commodity product to the set of customers, from the one or more production facilities.

3. The method of claim 1, wherein the specified evaluation method includes a minmax regret and minmax deviation method.

4. The method of claim 3, wherein the measure of robustness of a given solution is measured relative to a deviation from an identified reference solution determined for each of the outage scenarios.

5. The method of claim 1, wherein generating the set of solutions comprises:

generating an initial solution according to a Greedy Algorithm; and

generating additional solutions by modifying the initial solution according to a local search strategy.

6. A non-transitory computer-readable storage medium containing a delivery scheduling application, which when executed on a processor performs an operation for generating a robust delivery schedule for delivering a commodity product to a set of customers, the operation comprising:

generating one or more production outage scenarios based on historical production facility outage data, wherein each production outage scenario specifies a period of time during which a first one of one or more production facilities is presumed to be unavailable to produce the commodity product, wherein the commodity product comprises industrial gases delivered to a storage tank at each customer site via at least one delivery truck;

generating a set of solutions, wherein each solution specifies a delivery schedule for delivering the commodity product to the set of customers;

determining a cost for each solution relative to each generated scenario;

evaluating the cost of each solution according to a specified evaluation method to compute a robustness measure for each solution, wherein the robustness measure is determined based an expected change in the cost of the solution relative to the one or more production outage scenarios; and

returning, as the robust delivery schedule, a solution having a best determined cost versus robustness measure tradeoff, relative to other solutions in the generated set of solutions.

7. The computer-readable storage medium of claim 6, wherein the operation further comprises, receiving a set of input data describing distribution requirements for delivering the commodity product to the set of customers, from the one or more production facilities.

8. The computer-readable storage medium of claim 6, wherein the specified evaluation method includes a minmax regret and minmax deviation method.

9. The computer-readable storage medium of claim 8, wherein the measure of robustness of a given solution is measured relative to a deviation from an identified reference solution determined for each of the outage scenarios.

10. The computer-readable storage medium of claim 6, wherein generating the set of solutions comprises:

generating an initial solution according to a Greedy Algorithm; and

generating additional solutions by modifying the initial solution according to a local search strategy.

11. A system, comprising:

a processor; and

a memory storing a delivery scheduling application, which when executed on the processor performs an operation for generating a robust delivery schedule for delivering a commodity product to a set of customers, the operation comprising;

generating one or more production outage scenarios based on historical production facility outage data, wherein each production outage scenario specifies a period of time during which a first one of one or more production facilities is presumed to be unavailable to produce the commodity product, wherein the commodity product comprises industrial gases delivered to a storage tank at each customer site via at least one delivery truck,

generating a set of solutions, wherein each solution specifies a delivery schedule for delivering the commodity product to the set of customers,

determining a cost for each solution relative to each generated scenario,

evaluating the cost of each solution according to a specified evaluation method to compute a robustness measure for each solution, wherein the robustness measure is determined based an expected change in the cost of the solution relative to the one or more production outage scenarios, and

returning, as the robust delivery schedule, a solution having a best determined cost versus robustness measure tradeoff, relative to other solutions in the generated set of solutions.

12. The system of claim, 11 wherein the operation further comprises, receiving a set of input data describing distribution requirements for delivering the commodity product to the set of customers, from the one or more production facilities.

13. The system of claim 11, wherein the specified evaluation method includes a minmax regret and minmax deviation method.

14. The system of claim 13, wherein the measure of robustness of a given solution is measured relative to a deviation from an identified reference solution determined for each of the outage scenarios.

15. The system of claim 11, wherein generating the set of solutions comprises:

generating an initial solution according to a Greedy Algorithm; and

generating additional solutions by modifying the initial solution according to a local search strategy.