Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
2002-04-03
2004-08-31
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06785662
ABSTRACT:
FIELD OF THE INVENTION
The general field of the invention is in scheduling; specifically, a genetic algorithm is used to optimize the scheduling of crude oil vessels arriving at a refinery, unloading of the crude oil, and transfer of the crude oil to a storage tank.
BACKGROUND OF THE INVENTION
A refinery that processes crude oil is faced with the ongoing problem of continually scheduling the delivery, unloading, and temporary storage of crude oil. Usually the delivery of the crude oil is by a water-craft such as oil tankers or by pipeline. The vessels carrying the crude oil must be docked, usually at refinery facilities, and the crude oil unloaded and transferred through a conduit system to storage tanks. Each vessel has an arrival date, a specified number of days for unloading, and a demurrage charge if the unloading period is extended. Furthermore, each vessel may be of a different size and carrying a different amount of crude oil, and the composition of the crude oil itself varies from vessel to vessel. The refinery schedule is further defined by the number of available berths in the harbor or dock for the vessels, the size of the berths and the transportation conduits and equipment available at each of the berths. When the crude oil is delivered primarily by pipeline, sufficient temporary storage must be available at the time the crude oil arrives at the destination. It is common for refineries close to main waterways to primarily rely on vessels to deliver crude oil, and for refineries inland to rely on pipelines. Of course, a number of refineries have both vessel delivery of crude oil as well as pipeline delivery of crude oil.
Others have attempted to solve refinery scheduling problems using processes involving linear programming algorithms, see Lee, H. Pinto, J. M.; Grossmann, I. E. Park, S.
Ind. Eng. Chem. Res
. 35, 5, 1996 p. 1630-1641. In this article, the problem to be solved involved optimal operation of crude oil unloading, the transfer of the crude oil from storage tanks to charging tanks, and the charging schedule for each crude distillation unit. To optimize this operation, a mixed-integer optimization model was used which relied on time discretization. The problem involved bilinear equations due to mixing operations, However, the linearity in the form of a mixed-integer program was maintained by replacing the bilinear terms with individual component flows. The linear programming based branch and bound method was applied to solve the model and several techniques such as priority branching and bounding and special ordered sets were implemented to reduce computation time.
In the coal industry, U.S. Pat. No. 5,541,848 B1 describes a method of scheduling the delivery of coal to a series of incoming coal trains using a genetic algorithm where each of the coal trains corresponds to a coal recipient having different premium and penalty rates for energy yield, and contaminate specifications. The method is applied to a coal facility having a plurality of bins where the coal is of varying quality at the various bins and where the bins are grouped so that loading into trains must be done in succession.
Genetic algorithms such as that described in U.S. Pat. No. 5,541,848 B1 are known and multiple specific variations exist, see for example, U.S. Pat. No. 5,255,345 B1, U.S. Pat. No. 5,897,629 B1, U.S. Pat. No. 5,581,657 B1, and U.S. Pat. No. 5,848,403 B1. Genetic algorithms have been employed in a number of applications such as in U.S. Pat. No. 6,002,985 B1 which describes managing the development of oil or gas reserves using a neural network and genetic algorithm program to define a neural network topology. Drilling, completion, and stimulation of the reservoir is determined and applied based on hypothetical alternatives input to the topology and resulting outputs.
In the present invention, refinery scheduling problems dealing with incoming crude oil are at least semi-optimized using a genetic algorithm to arrive at a suitable feasible solution within a relatively short period of time. The use of genetic algorithms allows for acceptable solutions to be generated in the typical time frame available to a refiner. Changes in variables may be incorporated and the schedules re-optimized in a timely fashion.
SUMMARY OF THE INVENTION
The present invention is a method of forming a schedule of crude oil shipments being received at a refinery facility. The method begins by determining a period of time, T, within which the crude oil shipment schedule is to be formed. Then the goals of the crude oil shipment schedule, the variable parameters associated with the crude oil shipments to the refinery facility, and the constraints associated with the crude oil shipments to the refinery facility are all identified. A fitness function is determined in accordance with the goals of the schedule, the variable parameters, and the constraints. A first generation of chromosomes is randomly generated, with each chromosome in the generation representing a possible solution. The fitness function value for each of the chromosomes is calculated using the fitness function. A succeeding generation of chromosomes is created using a genetic algorithm and the fitness function value for each of the chromosomes is determined using the fitness function. The steps of producing a succeeding generation of chromosomes using a genetic algorithms and determining a fitness function value for each of the chromosomes in the succeeding generation are repeated. The chromosome having the highest fitness function value within time T is identified.
REFERENCES:
patent: 5255345 (1993-10-01), Shaefer
patent: 5541848 (1996-07-01), McCormack et al.
patent: 5581657 (1996-12-01), Lyon
patent: 5848403 (1998-12-01), Gabriner et al.
patent: 5897629 (1999-04-01), Shinagawa et al.
patent: 5924048 (1999-07-01), McCormack et al.
patent: 6002985 (1999-12-01), Stephenson
patent: 6236894 (2001-05-01), Stoisits et al.
patent: 6446721 (2002-09-01), Patel et al.
Leung et al, “A genetic Algorithm for Mulitple Destiniation Routing Problems”, IEEE Transactions on Evolutionary Computing, Nov. 1998.*
Oaks et al, “Generation of Realistic Air Traffic Scenarios Using a Genetic Alogrithm” IEEE proceedings of DAS conference, 2002.*
Tawanaka et al, “Genetic Algorithm with the Constraints for Nurse Scheduling problem” IEEE on Evolutionary Computing, May 2001.*
Andrzej et al, “A New Costraint Tournament Selection Method for Multi criteria Optimization using Genetic Algorithm” IEEE on Evolutionary Computing, Jul. 2000.*
Lee, H. Pinto, J.M.; Grossman, I.E; Park, S.;Ind. Eng. Chem. Res., 35, 5 1996 pp. 1630-1641.
Barsamian, A; “Genetic Algorithm Optimizers for Blend Planning Applications”; Refinery Automation Institute, LLC.
Hydrocarbon Processing, Sep. 2001, 119.
Guy R. Kirk
Nelson, Jr. E. Cole
Davis George B.
Maas Maryann
Molinaro Frank S.
Tolomei John G.
UOP LLC
LandOfFree
Refinery scheduling of incoming crude oil using a genetic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Refinery scheduling of incoming crude oil using a genetic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Refinery scheduling of incoming crude oil using a genetic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3285047