Facilities optimization method

• US 20100004905A1
• Filed: 07/07/2008
• Published: 01/07/2010
• Est. Priority Date: 07/07/2008
• Status: Active Grant

• Current Assignee: King Fahd University of Petroleum & Minerals (Government of Saudi Arabia)
• Original Assignee: King Fahd University of Petroleum & Minerals (Government of Saudi Arabia)
• Inventors: Aldajani, Mansour A.
• Granted Patent: US 7,949,503 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06Q 10/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 Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

The facilities optimization method utilizes Coulomb'"'"'s law to model placement of facilities relative to a population using the facilities. The natural phenomenon of electrical charge attraction and repulsion can be used to model a wide variety of facility layout and planning problems. The physical phenomenon of charge interaction is simulated and used to effectively find a solution for a facilities supply-demand problem. Utilizing the charge model, problem solutions are naturally reached and are self-adjusting in response to parameter changes in the problem. A methodology for static, dynamic, elastic or inelastic demand is provided. The charge simulation approach supports any distance metric. The method always provides a solution regardless of the initial conditions used. The method provides high flexibility in choosing arbitrary demand and supply patterns.

Claims

1. A computer product for facilities optimization comprising a medium readable by a computer, the medium having a set of computer-readable instructions stored thereon executable by a processor when loaded into main memory, the instructions including:

simulating a physical phenomenon of charged particle interaction, thereby producing a charged particle interaction simulation;

assigning a first charge of first charge type particles to users of service supplying facilities;

assigning a second charge of second charge type particles to the service supplying facilities;

disposing a first plurality of the user particles and a second plurality of the facility particles in an initial configuration within the simulation;

constraining a first of the first and second pluralities of particles to their initial configuration;

allowing a second of the first and second pluralities of particles to move, said second of the first and second pluralities of particles finding an equilibrium state with respect to the first of the first and second pluralities of particles; and

iteratively performing the previous steps while varying first plurality and second plurality of particles, the iterative performance of the simulation settling into an optimum location and number of supply points associated with the facility particles with respect to demand points associated with the user particles.

2. The computer product according to claim 1, wherein the first of the first and second pluralities of particles are the user particles and the second of the first and second pluralities of particles are the facility particles.

3. The computer product according to claim 1, wherein the simulating step further comprises the step of calculating particle interactions based on Coulomb'"'"'s law, the particle interactions calculating step including evaluating the equation for particles i, j, and w as follows;

$\begin{array}{cc}<br><br>f_{\mathrm{ij}}<br><br>=\{\begin{array}{c}\frac{{\mathrm{kg}}_i<br><br>g_j}{h_{\mathrm{ij}}^2},\arg <br><br><br><br>{\max }_w<br><br>\left\{\frac{{\mathrm{kg}}_w<br><br>g_j}{h_{\mathrm{wj}}^2}\right\}=i\\ 0,\mathrm{Otherwise}\end{array},& \left(2\right)\end{array}$

wherein g_i and g_j are the amounts of charge for particles i , j and w respectively and k is a degradation factor, the parameter h_ij being the distance between the two particles.

4. The computer product according to claim 1, wherein said instructions further include calculating a force direction for each pair of particles by evaluating the equation:

$u_{\mathrm{ij}}=\frac{1}{{\left(x_i-x_j\right)}^2-{\left(y_i-y_j\right)}^2}<br><br>\left[\left(x_i-x_j\right)<br><br>\left(y_i-y_j\right)\right],$

wherein u_ij is a unity vector, x_i, x_j, y_i, y_j are Cartesian coordinates of the i_th particle and the j_th particle respectively.

5. The computer product according to claim 4, wherein said instructions further include calculating a net force applied to any particle in the simulation by evaluating the equation,

f_i=Σ

<sub>j=[1,M],j≠

i</sub>|f_ij|u_ij,

wherein M is the total number of particles.

6. The computer product according to claim 5, wherein said instructions further include calculating particle velocities and particle displacements by evaluating the equations,

v_i(t+Δ

)=v_i(t)+a₁f_i(t), and

p_i(t+Δ

)=p_i(t)+a₂v_i(t), respectively, wherein v_i is the velocity of the i_th particle, p_i is the displacement of the i_th particle, t is time, Δ

is a computation step-size, and constants a₁ and a₂ are dependent on the computation step size.

7. The computer product according to claim 4, wherein said instructions further include minimizing the number of facilities and their locations such that a service level all over an entire space Γ

is at least equal to a constant threshold α

, thereby fulfilling a criteria,

min N,

such that

r(x,y)≧

∝

∀

x,y ∈

Γ

, wherein N is the number of facilities and r(x,y) is a net service level offered at a point having the coordinates (x,y).

8. The computer product according to claim 7, wherein said instructions further include:

evaluating a first quantity,

$s_i<br><br>\left(x,y\right)={G_i<br><br>\left(\frac{1}{h_i<br><br>\left(x,y\right)}\right)}^2,$

the first quantity being an amount of coverage supplied by the i_th facility to the demand point at location (x,y)

evaluating a second quantity, d(x,y), the second quantity being a demand value represented in the simulation as the amount of charge carried by the negative particles; and

evaluating

r(x,y)=Σ

_i=1{s_i(x,y)}−

d(x,y),

wherein r(x,y) is the difference between supply and demand.

9. The computer product according to claim 7, wherein said instructions further include evaluating the equation

r(x,y)=max{s_i(x,y)}−

d(x,y),

wherein each demand point is covered satisfactorily by at least one of the facilities.

10. The computer product according to claim 7, wherein said instructions further include:

placing a first positive particle at an arbitrary site inside a field;

allowing the particle to begin moving towards the demand particles via a force of attraction defined by the simulation;

measuring the net field strength (service level) all over the area;

terminating the simulation with a solution if the net field strength is above the threshold α

for all points;

placing a second positive particle at an arbitrary site if the net field strength is below the threshold α

for all points; and

repeating the previous steps in this claim until the simulation ends on condition of the terminating step.

11. The computer product according to claim 1, wherein said instructions further include producing a color-coded demand pattern, wherein color codes of the demand pattern facilitate observation of the solution by a user of the simulation.

12. The computer product according to claim 11, wherein the color codes comprise representations of a priority level category, a population density category, and a service category.

13. The computer product according to claim 12, wherein a color code includes a combination of more than one of the categories.