Operations Research LOCational Analysis Models

Description

Objects and methods to handle and solve the min-sum location problem, also known as Fermat-Weber problem.

Details

Package:   orloca

Type:      Package

Version:   5.6

Date:      2024-01-31

License:   GPL (>= 3)

The min-sum location problem search for a point such that the weighted sum of the distances to the demand points are minimized. See "The Fermat-Weber location problem revisited" by Brimberg, Mathematical Programming, 1, pg. 71-76, 1995, doi:10.1007/BF01592245.

General global optimization algorithms are used to solve the problem, along with the adhoc Weiszfeld method, see "Sur le point pour lequel la Somme des distances de n points donnes est minimum", by E. Weiszfeld, Tohoku Mathematical Journal, First Series, 43, pg. 355-386, 1937 or "On the point for which the sum of the distances to n given points is minimum", by E. Weiszfeld and F. Plastria, Annals of Operations Research, 167, pg. 7-41, 2009, doi:10.1007/s10479-008-0352-z.

The package provides a class loca.p that represents a location problem with a finite set of demand points on the plane. Also, it is possible to plot the points and the objective function. Such objective function is the total weighted distances travelled by all the customers to the service.

Non-planar location problems could be handle in future versions of the package.

For a demo, load the package with the instruction library(orloca), and run the demo executing the instruction demo(orloca).

The package is ready for internationalization. The author kindly ask for translated version of the .mo file to include in the package.

Author(s)

Manuel Munoz-Marquez <manuel.munoz@uca.es>

Mantainer: Manuel Munoz-Marquez <manuel.munoz@uca.es>

References

[1] Brimberg, J. The Fermat-Weber location problem revisited, Mathematical Programming, 1, pg. 71-76, 1995. doi:10.1007/BF01592245.

[2] Love, R. F., Morris, J. G., Wesolowsky, G. O. Facilities Location: Chapter 2: Introduction to Single-Facility Location, 1988, North-Holland. ISBN: 0-444-01031-9.

[3] Weiszfeld, E. and Plastria, F. On the point for which the sum of the distances to n given points is minimum, Annals of Operations Research, 167, pg. 7-41, 2009, doi:10.1007/s10479-008-0352-z.

[4] http://knuth.uca.es/orloca/

See Also

Useful links:

• http://knuth.uca.es/orloca/

Examples

# A new unweighted loca.p object
o <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Compute the sum of distances to point (3, 4)
# [1] 20.39384
distsum(o, 3, 4)

# Compute the sum of distances to point (3, 4) using lp norm with p = 2.5
# [1] 19.27258
distsum(o, 3, 4, lp = 2.5)

# Solve the optimization problem
# [1] 0 0
distsummin(o)

# Contour plot
contour(o)

# Run a demo of the package
demo(orloca)

Cities of Andalusia

Description

The 'andalusia' data frame has 12 rows and 4 columns, which are the geographical position of the main capital cities of andalusia.

Format

name: The name of the city or relative position label.

x: The x coordinate of points.

y: The y coordinate of points.

city: If yes the point is a city in other case is a limit.

Usage

data('andalusia')

Source

Data are taken from wikipedia.

See Also

See also orloca-package.

as-methods

Description

Conversions between loca.p class and some others classes

Arguments

Details

Methods to convert from and to loca.p class.

NA's values are not allowed in any of the arguments.

The matrix or data.frame to convert into loca.p must have at least two columns. The first column will be consider as the x coordinates, the second as the y coordinates, and the third (if given) as the values of weights w.

Value

It returns a new object of the new class.

See Also

See also loca.p

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Conversion to matrix
m <- as.matrix(loca)

# Show matrix
m

# Conversion from matrix
as.loca.p(m)

as.data.frame.loca.p S3 method to convert from loca.p to data.frame

Description

Conversions between loca.p class and some others classes

Usage

## S3 method for class 'loca.p'
as.data.frame(x, row.names = NULL, optional = FALSE, ...)

Arguments

Details

Methods to convert from and to loca.p class.

NA's values are not allowed in any of the arguments.

The matrix or data.frame to convert into loca.p must have at least two columns. The first column will be consider as the x coordinates, the second as the y coordinates, and the third (if given) as the values of weights w.

Value

It returns a new object of the new class.

See Also

See also loca.p

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Conversion to matrix
m <- as.matrix(loca)

# Show matrix
m

# Conversion from matrix
as.loca.p(m)

as.loca.p The following is for S3 compatibility, mainly for documentation check

Description

Conversions between loca.p class and some others classes

Usage

as.loca.p(x, ...)

Arguments

Details

Methods to convert from and to loca.p class.

NA's values are not allowed in any of the arguments.

The matrix or data.frame to convert into loca.p must have at least two columns. The first column will be consider as the x coordinates, the second as the y coordinates, and the third (if given) as the values of weights w.

Value

It returns a new object of the new class.

See Also

See also loca.p

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Conversion to matrix
m <- as.matrix(loca)

# Show matrix
m

# Conversion from matrix
as.loca.p(m)

as.loca.p.data.frame S3 method to convert from data.frame to loca.p

Description

Conversions between loca.p class and some others classes

Usage

as.loca.p.data.frame(x, ...)

Arguments

Details

Methods to convert from and to loca.p class.

NA's values are not allowed in any of the arguments.

The matrix or data.frame to convert into loca.p must have at least two columns. The first column will be consider as the x coordinates, the second as the y coordinates, and the third (if given) as the values of weights w.

Value

It returns a new object of the new class.

See Also

See also loca.p

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Conversion to matrix
m <- as.matrix(loca)

# Show matrix
m

# Conversion from matrix
as.loca.p(m)

as.loca.p.matrix S3 method to convert from matrix to loca.p

Description

Conversions between loca.p class and some others classes

Usage

as.loca.p.matrix(x, ...)

Arguments

Details

Methods to convert from and to loca.p class.

NA's values are not allowed in any of the arguments.

The matrix or data.frame to convert into loca.p must have at least two columns. The first column will be consider as the x coordinates, the second as the y coordinates, and the third (if given) as the values of weights w.

Value

It returns a new object of the new class.

See Also

See also loca.p

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Conversion to matrix
m <- as.matrix(loca)

# Show matrix
m

# Conversion from matrix
as.loca.p(m)

as.matrix.loca.p S3 method to convert from loca.p to matrix

Description

Conversions between loca.p class and some others classes

Usage

## S3 method for class 'loca.p'
as.matrix(x, rownames.force = NA, ...)

Arguments

Details

Methods to convert from and to loca.p class.

NA's values are not allowed in any of the arguments.

The matrix or data.frame to convert into loca.p must have at least two columns. The first column will be consider as the x coordinates, the second as the y coordinates, and the third (if given) as the values of weights w.

Value

It returns a new object of the new class.

See Also

See also loca.p

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Conversion to matrix
m <- as.matrix(loca)

# Show matrix
m

# Conversion from matrix
as.loca.p(m)

Plots of the min-sum objective function

Description

contour provides a graphical representations of min-sum objective function, which is the weighted sum of the distances to demand points (distsum).

Usage

## S3 method for class 'loca.p'
contour(
  x,
  lp = numeric(0),
  xmin = min(min(x@x), xleft),
  xmax = max(max(x@x), xright),
  ymin = min(min(x@y), ybottom),
  ymax = max(max(x@y), ytop),
  n = 100,
  img = NULL,
  xleft = min(x@x),
  ybottom = min(x@y),
  xright = max(x@x),
  ytop = max(x@y),
  ...
)

Arguments

Details

If p<1 then l_p is not a norm, so only p>=1 are valid values.

Value

contour.loca.p plots a contour plot of min-sum function (distsum).

See Also

See also orloca-package, plot.loca.p and loca.p.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# The contour plot of min-sum function for loca (a loca.p object)
contour(loca)

Computes distsum function

Description

The objective function and the gradient of the objective function for the min-sum location problem.

Usage

distsum(o, x = 0, y = 0, lp = numeric(0))

Arguments

Details

The function zsum is deprecated and will be removed from new versions of the package.

Value

distsum returns the objective function of the min-sum location problem, \sum_{a_i \in o} w_i d(a_i, (x,y)), where d(a_i, (x,y)) gives the euclidean or the l_p distances between a_i and the point (x,y).

See Also

See also orloca-package and distsummin.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# Evaluation of distsum at (0, 0)
distsum(loca)

# Evaluation of distsum at (1, 3)
distsum(loca, 1, 3)
# Compute the objective function at point (3, 4) using lp norm and p = 2.5
distsum(loca, 3, 4, lp=2.5)
# The gradient function at (1,3)
distsumgra(loca, 1, 3)

Computes the gradient of distsum function

Description

The gradient of the objective function for the min-sum location problem.

Usage

distsumgra(o, x = 0, y = 0, lp = numeric(0), partial = F)

Arguments

Details

The function zsumgra is deprecated and will be removed from new versions of the package.

Value

distsumgra returns the gradient vector of the objective function of the min-sum location problem, \sum_{a_i \in o} w_i d(a_i, (x,y)), where d(a_i, (x,y)) gives the euclidean or the l_p distances between a_i and the point (x,y).

See Also

See also orloca-package and distsum.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# Evaluation of distsum at (0, 0)
distsum(loca)

# Evaluation of distsum at (1, 3)
distsum(loca, 1, 3)
# Compute the objective function at point (3, 4) using lp norm and p = 2.5
distsum(loca, 3, 4, lp=2.5)
# The gradient function at (1,3)
distsumgra(loca, 1, 3)

distsuml2 and distsuml2gra at orloca package

Description

distsum and distsumgra functions for the Euclidean norm (l_2). Mainly for internal use.

Usage

distsuml2(o, x = 0, y = 0)

Arguments

Details

If (x,y) is a demand point partial=T means ignore such point to compute the gradient. This option is mainly for internal use.

Value

distsuml2 returns the objective function of the min-sum location problem, \sum_{a_i \in o} w_i d(a_i, (x,y)), where d(a_i, (x,y)) gives the euclidean distances between a_i and the point (x,y). distsumgra returns the gradient vector of the function distsum.

See Also

See also orloca-package, distsum, distsumgra and distsummin.

distsuml2min at orloca package

Description

distsuml2min is the distsummin function for the Euclidean norm (l_2). This function returns the solution of the minimization problem. Mainly for internal use.

Usage

distsuml2min(
  o,
  x = 0,
  y = 0,
  max.iter = 100,
  eps = 0.001,
  verbose = FALSE,
  algorithm = "Weiszfeld",
  ...
)

Arguments

Details

The algorithms Weiszfeld and gradient include and optimality test for demand points. The Weiszfeld version of the algorithm also implements slow convergence test and accelerator procedure.

If p < 1 thus l_p is not a norm, so, only p \ge 1 are valid values.

Since l_2 norm is the Euclidean norm, when p=2 distsumlpmin are equal to distsummin. But the computations involved are greater for the first form.

max.iter for SANN algorithm is the number of evaluation of objective function, so this method usually requires large values of max.iter to reach optimal value

The function zsummin is deprecated and will be removed from new versions of the package.

Value

distsummin returns an array with the coordinates of the solution point.

See Also

See also orloca-package, loca.p and distsum.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# Compute the minimum
sol<-distsummin(loca)

# Show the result
sol

# Evaluation of the objective function at solution point
distsum(loca, sol[1], sol[2])

distsumlp and distsumlpgra at orloca package

Description

distsum and distsumgra functions with l_p norm. Mainly for internal use.

Usage

distsumlp(o, x = 0, y = 0, p = 2)

Arguments

Details

If p<1 then l_p is not a norm, so only p>=1 are valid values.

Since l_2 norm is the Euclidean norm, when p=2 distsumlp are equal to distsum, and distsumlpgra are equal to distsumgra. But the computations involved are greater for the firsts form.

Value

distsumlp returns the objective function of the min-sum location problem with l_p norm, \sum_{a_i \in o} w_i d(a_i, (x,y)), where d(a_i, (x,y)) gives the distances between a_i and the point (x,y) using l_p norm.

distsumlpgra returns the gradient vector of the function distsumlp. If (x,y) is a demand point partial=T means ignore such point to compute the gradient. This option is mainly for internal use.

See Also

See also distsum, orloca-package and distsumlpmin.

distsumlpmin at orloca package

Description

distsumlpmin is the distsummin function for the norm (l_p). This function returns the solution of the minimization problem. Mainly for internal use.

Usage

distsumlpmin(
  o,
  x = 0,
  y = 0,
  p = 2,
  max.iter = 100,
  eps = 0.001,
  verbose = FALSE,
  algorithm = "Weiszfeld",
  ...
)

Arguments

Details

The algorithms Weiszfeld and gradient include and optimality test for demand points. The Weiszfeld version of the algorithm also implements slow convergence test and accelerator procedure.

If p < 1 thus l_p is not a norm, so, only p \ge 1 are valid values.

Since l_2 norm is the Euclidean norm, when p=2 distsumlpmin are equal to distsummin. But the computations involved are greater for the first form.

max.iter for SANN algorithm is the number of evaluation of objective function, so this method usually requires large values of max.iter to reach optimal value

The function zsummin is deprecated and will be removed from new versions of the package.

Value

distsummin returns an array with the coordinates of the solution point.

See Also

See also orloca-package, loca.p and distsum.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# Compute the minimum
sol<-distsummin(loca)

# Show the result
sol

# Evaluation of the objective function at solution point
distsum(loca, sol[1], sol[2])

Returns the solution of the minimization problem

Description

Solve the min-sum location problem for a given loca.p class object.

Usage

distsummin(
  o,
  x = 0,
  y = 0,
  lp = numeric(0),
  max.iter = 1e+05,
  eps = 0.001,
  verbose = FALSE,
  algorithm = "Weiszfeld",
  ...
)

Arguments

Details

The algorithms Weiszfeld and gradient include and optimality test for demand points. The Weiszfeld version of the algorithm also implements slow convergence test and accelerator procedure.

If p < 1 thus l_p is not a norm, so, only p \ge 1 are valid values.

Since l_2 norm is the Euclidean norm, when p=2 distsumlpmin are equal to distsummin. But the computations involved are greater for the first form.

max.iter for SANN algorithm is the number of evaluation of objective function, so this method usually requires large values of max.iter to reach optimal value

The function zsummin is deprecated and will be removed from new versions of the package.

Value

distsummin returns an array with the coordinates of the solution point.

See Also

See also orloca-package, loca.p and distsum.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# Compute the minimum
sol<-distsummin(loca)

# Show the result
sol

# Evaluation of the objective function at solution point
distsum(loca, sol[1], sol[2])

loca.p class for Operations Research LOCational Analysis

Description

An object of class loca.p represents a weighted location problem with a finite demand points set. The orloca-package is mainly devoted to deals with location problems.

Arguments

Details

The main generator of the loca.p class is loca.p(x, y, w = numeric(0), label = ""). An alternative form is new("loca.p", x, y, w = numeric(0), label = "").

The lengths of x and y vector must be equals. The length of w must be equal to the previous ones or must be 0, or should be omitted. NA's values are not allowed at any of the arguments.

summary(x) returns a summary of the x loca.p object and print(x) prints the x loca.p object in table format.

Value

If the arguments have valid values, it returns a new object of class loca.p, else it returns an error.

See Also

See also orloca-package.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# or
loca <- new("loca.p", x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# An example with weights and name
locb <- new("loca.p", x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1),
w = c(1, 2, 1, 2), label = "Weighted case")

Modelos de Investigacion Operativa para el Analisis de Localizacion (Operations Research LOCational Analysis Models)

Description

Objetos y metodos para manejar y resolver el problema de localizacion de suma ponderada minima, tambien conocido como problema de Fermat-Weber.

Paquete:   orloca

Version:   5.5

Fecha:      2023-09-19

Licencia:   GPL (>= 3)

Details

El problema de localizacion de suma minima busca un punto tal que la suma ponderada de las distancias a los puntos de demanda se minimice. Vease "The Fermat-Weber location problem revisited" por Brimberg, Mathematical Programming, 1, pag. 71-76, 1995. doi:10.1007/BF01592245.

Se usan algoritmos generales de optimizacion global para resolver el problema, junto con el metodo adhoc Weiszfeld, vease "Sur le point pour lequel la Somme des distance de n points donnes est minimum", por Weiszfeld, Tohoku Mathematical Journal, First Series, 43, pag. 355-386, 1937 o "On the point for which the sum of the distances to n given points is minimum", por E. Weiszfeld y F. Plastria, Annals of Operations Research, 167, pg. 7-41, 2009. doi:10.1007/s10479-008-0352-z.

El paquete proporciona una clase loca.p que representa un problema de localizacion sobre el plano. Tambien permite dibujar los puntos junto a la funcion objetivo. Dicho objetivo es la suma ponderada de las distancias que viajan los clientes del servicio.

Versiones no planas del problema podrian incorporarse en futuras versiones del paquete.

Para una demostracion, cargue el paquete con la instrucción library(orloca) y ejecute la demostracion con la instruccion demo(orloca).

El paquete esta preparado para su internacionalizacion. Las traducciones de los ficheros .mo recibidas seran anadidas en proximas versiones del paquete.

Author(s)

Manuel Munoz-Marquez <manuel.munoz@uca.es>

Mantenedor: Manuel Munoz-Marquez <manuel.munoz@uca.es>

References

[1] Brimberg, J. The Fermat-Weber location problem revisited, Mathematical Programming, 1, pg. 71-76, 1995. doi:10.1007/BF01592245.

[2] Love, R. F., Morris, J. G., Wesolowsky, G. O. Facilities Location: Chapter 2: Introduction to Single-Facility Location, 1988, North-Holland

[3] Weiszfeld, E. and Plastria, F. On the point for which the sum of the distances to n given points is minimum, Annals of Operations Research, 167, pg. 7-41, 2009, doi:10.1007/s10479-008-0352-z.

[4] http://knuth.uca.es/orloca/

Examples

# Un objeto loca.p no ponderado
o <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# Calcula la funcion objetivo en el punto (3, 4)
# [1] 20.39384
zsum(o, 3, 4)

# Calcula la suma de las distancias al punto (3, 4) usando la norma lp con p = 2.5
# [1] 19.27258
zsum(o, 3, 4, lp = 2.5)

# Resuelve el problema de localizacion
# [1] 0 0
zsummin(o)

# Curvas de nivel
contour(o)

# Ejecuta una demo del paquete
demo(orloca)

Plots of the min-sum objective function

Description

persp provides a graphical representations of objetive function of the min-sum problem, which is the total weighte distance to the demand points (distsum).

Usage

## S3 method for class 'loca.p'
persp(
  x,
  lp = numeric(0),
  xmin = min(x@x),
  xmax = max(x@x),
  ymin = min(x@y),
  ymax = max(x@y),
  n = 10,
  ticktype = "detailed",
  ...
)

Arguments

Details

If p<1 then l_p is not a norm, so only p>=1 are valid values.

Value

A plot a 3D plot or min-sum function.

See Also

See also orloca-package, plot.loca.p and loca.p.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))

# The 3D graphics
persp(loca)

plot of loca.p class objects

Description

This method provides a graphical representations of an object of class loca.p.

Usage

## S3 method for class 'loca.p'
plot(
  x,
  xlab = "",
  ylab = "",
  main = paste(gettext("Plot of loca.p"), ifelse(x@label == "", "", paste0(": \"",
    x@label, "\""))),
  img = NULL,
  xlim = c(min(xleft, min(x@x)), max(xright, max(x@x))),
  ylim = c(min(ybottom, min(x@y)), max(ytop, max(x@y))),
  xleft = min(x@x),
  ybottom = min(x@y),
  xright = max(x@x),
  ytop = max(x@y),
  ...
)

Arguments

Details

The function plots demand points by evaluating limits automatically.

Value

The function plots the required graphics.

See Also

See also orloca-package, loca.p and plot.

Examples

# A new unweighted loca.p object
loca <- loca.p(x = c(-1, 1, 1, -1), y = c(-1, -1, 1, 1))
# The plot of loca object
plot(loca)

Random instances generator of loca.p class object

Description

rloca.p function returns a random instance of loca.p class object at a given rectangular region.

Usage

rloca.p(
  n,
  xmin = 0,
  xmax = 1,
  ymin = 0,
  ymax = 1,
  wmin = 1,
  wmax = 1,
  label = "",
  groups = 0,
  xgmin = xmin,
  xgmax = xmax,
  ygmin = ymin,
  ygmax = ymax
)

Arguments

Details

n must be at least 1.

xmin must be less or equal than xmax.

ymin must be less or equal than ymax.

If a non zero value is given for groups parameter, then a reference point for each group are generated. At second stage, the offset part for each demand point are generated, and added to the reference point generated at the first stage.

Note that groups = 1 is not equivalent to the default value groups = 0, because in the first case a reference point are generated at the first stage.

Value

If the arguments are valid values, it returns a new object of loca.p class, else it returns an error.

See Also

See also orloca-package and loca.p.

Examples

# A random loca.p object at unit square with 5 demand points
rloca.p(5)
# At another region
rloca.p(10, xmin=-2, xmax=2, ymin=-2, ymax=2)
# Five groups
rloca.p(48, groups=5)
# Three unequal size groups
rloca.p(1, groups=c(10, 7, 2))

zsum

Description

The function zsum is deprected and could be removed in next version of the package. Use distsum instead.

Usage

zsum(...)

Arguments

zsumgra

Description

The function zsumgra is deprected and could be removed in next version of the package. Use distsumgra instead.

Usage

zsumgra(...)

Arguments

zsummin

Description

The function zsummin is deprected and could be removed in next version of the package. Use distsummin instead.

Usage

zsummin(...)

Arguments