spopt.locate.PDispersion¶

class spopt.locate.PDispersion(name: str, problem: LpProblem, p_facilities: int)[source]¶

Implement the \(p\)-dispersion optimization model and solve it [Kub87]. The \(p\)-dispersion problem, as adapted from [MKH12], can be formulated as:

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Maximize} & \displaystyle D && & (1) \\ \displaystyle \textbf{Subject To} & \displaystyle \sum_{i \in I}{Y_i} = p && & (2) \\ & D \leq d_{ij} + M (2 - Y_{i} - Y_{j}) && \forall i \in I \quad \forall j > i & (3) \\ & Y_i \in \{0, 1\} && \forall i \in I & (4) \\ & && & \\ \displaystyle \textbf{Where} && i, j & = & \textrm{index of potential facility sites in set } I \\ && p & = & \textrm{the number of facilities to be sited} \\ && d_{ij} & = & \textrm{shortest distance or travel time between locations } i \textrm{ and } j \\ && D & = & \textrm{minimum distance between any two sited facilities } i \textrm{ and } j \\ && M & = & \textrm{some large number; such that } M \geq \max_{ij}\{d_{ij}\} \\ && Y_i & = & \begin{cases} 1, \textrm{if a facility is sited at location } i \\ 0, \textrm{otherwise} \\ \end{cases} \\ \end{array}\end{split}\]

Parameters:

namestr: The problem name.
problempulp.LpProblem: A pulp instance of an optimization model that contains constraints, variables, and an objective function.

Attributes:

namestr: The problem name.
problempulp.LpProblem: A pulp instance of an optimization model that contains constraints, variables, and an objective function.

__init__(name: str, problem: LpProblem, p_facilities: int)[source]¶

Initialize.

Parameters:

namestr: The desired name for the model.

Methods

`__init__`(name, problem, p_facilities)	Initialize.
`check_status`()	Ensure a model is solved.
`from_cost_matrix`(cost_matrix, p_facilities)	Create a `PDispersion` object based on a cost matrix.
`from_geodataframe`(gdf_fac, facility_col, ...)	Create a `PDispersion` object based on a geodataframe.
`solve`(solver)	Solve the `PDispersion` model.

classmethod from_cost_matrix(cost_matrix: array, p_facilities: int, predefined_facilities_arr: array = None, name: str = 'p-dispersion')[source]¶

Create a PDispersion object based on a cost matrix.

Parameters:

cost_matrixnp.array: A cost matrix in the form of a 2D array between origins and destinations.
p_facilitiesint: The number of facilities to be located.
predefined_facilities_arrnumpy.array (default None): A binary 1D array of service facilities that must appear in the solution. For example, consider 3 facilites ['A', 'B', 'C']. If facility 'B' must be in the model solution, then the passed in array should be [0, 1, 0].
namestr (default ‘p-dispersion’): The name of the problem.

Returns:

spopt.locate.p_dispersion.PDispersion

Examples

>>> from spopt.locate.p_dispersion import PDispersion
>>> from spopt.locate.util import simulated_geo_points
>>> import geopandas
>>> import pulp
>>> import spaghetti

Create a regular lattice.

>>> lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
>>> ntw = spaghetti.Network(in_data=lattice)
>>> streets = spaghetti.element_as_gdf(ntw, arcs=True)
>>> streets_buffered = geopandas.GeoDataFrame(
...     geopandas.GeoSeries(streets["geometry"].buffer(0.2).unary_union),
...     crs=streets.crs,
...     columns=["geometry"]
... )

Simulate points about the lattice.

>>> facility_points = simulated_geo_points(streets_buffered, needed=5, seed=6)

Snap the points to the network of lattice edges.

>>> ntw.snapobservations(facility_points, "facilities", attribute=True)
>>> facilities_snapped = spaghetti.element_as_gdf(
...     ntw, pp_name="facilities", snapped=True
... )

Calculate the cost matrix from origins to destinations. Origins and destinations are both 'facilities' in this case.

>>> cost_matrix = ntw.allneighbordistances(
...    sourcepattern=ntw.pointpatterns["facilities"],
...    destpattern=ntw.pointpatterns["facilities"]
... )

Create and solve a PDispersion instance from the cost matrix.

>>> pdispersion_from_cost_matrix = PDispersion.from_cost_matrix(
...     cost_matrix, p_fac=2
... )
>>> pdispersion_from_cost_matrix = pdispersion_from_cost_matrix.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Examine the solution.

>>> for dv in pdispersion_from_cost_matrix.fac_vars:
...     if dv.varValue:
...         print(f"facility {dv.name} is selected")
facility y_0_ is selected
facility y_1_ is selected

classmethod from_geodataframe(gdf_fac: GeoDataFrame, facility_col: str, p_facilities: int, predefined_facility_col: str = None, distance_metric: str = 'euclidean', name: str = 'p-dispersion')[source]¶

Create a PDispersion object based on a geodataframe. Calculate the cost matrix between facilities, and then use the from_cost_matrix method.

Parameters:

gdf_facgeopandas.GeoDataFrame: Facility locations.
facility_colstr: Facility candidate sites geometry column name.
p_facilitiesint: The number of facilities to be located.
predefined_facility_colstr (default None): Column name representing facilities are already defined. This a binary assignment per facility. For example, consider 3 facilites ['A', 'B', 'C']. If facility 'B' must be in the model solution, then the column should be [0, 1, 0].
distance_metricstr (default ‘euclidean’): A metric used for the distance calculations supported by scipy.spatial.distance.cdist.
namestr (default ‘p-dispersion’): The name of the problem.

Returns:

spopt.locate.p_dispersion.PDispersion

Examples

>>> from spopt.locate.p_dispersion import PDispersion
>>> from spopt.locate.util import simulated_geo_points
>>> import geopandas
>>> import pulp
>>> import spaghetti

Create a regular lattice.

>>> lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
>>> ntw = spaghetti.Network(in_data=lattice)
>>> streets = spaghetti.element_as_gdf(ntw, arcs=True)
>>> streets_buffered = geopandas.GeoDataFrame(
...     geopandas.GeoSeries(streets["geometry"].buffer(0.2).unary_union),
...     crs=streets.crs,
...     columns=["geometry"]
... )

Simulate points about the lattice.

>>> facility_points = simulated_geo_points(streets_buffered, needed=5, seed=6)

Snap the points to the network of lattice edges and extract as a GeoDataFrame object.

>>> ntw.snapobservations(facility_points, "facilities", attribute=True)
>>> facilities_snapped = spaghetti.element_as_gdf(
...     ntw, pp_name="facilities", snapped=True
... )

Create and solve a PDispersion instance from the GeoDataFrame object.

>>> pdispersion_from_geodataframe = PDispersion.from_geodataframe(
...     facilities_snapped,
...     "geometry",
...     p_fac=2,
...     distance_metric="euclidean"
... )
>>> pdispersion_from_geodataframe = pdispersion_from_geodataframe.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Examine the solution.

>>> for dv in pdispersion_from_geodataframe.fac_vars:
...     if dv.varValue:
...         print(f"facility {dv.name} is selected")
facility y_0_ is selected
facility y_1_ is selected

solve(solver: LpSolver)[source]¶

Solve the PDispersion model.

Parameters:

solverpulp.LpSolver: A solver supported by pulp.

Returns:

spopt.locate.p_dispersion.PDispersion