# spopt.locate.KNearestPMedian

class spopt.locate.KNearestPMedian(name: str, ai_sum: int | float, clients: array, facilities: array, weights: array, k_array: array, p_facilities: int, capacities: array = None, distance_metric: str = 'euclidean')

  Implement the P-Median Model with Near-Far Cost Allocation and solve it. The model is adapted from [Chu18], and can be formulated as:

  \[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{i \in I}\sum_{k \in k_{i}}{a_i d_{ik} X_{ik}} + \sum_{i \in I}{g_i (d_{i{k_i}} + 1)} && & (1) \\ \displaystyle \textbf{Subject To} & \sum_{k \in k_{i}}{X_{ik} + g_i = 1} && \forall i \in I & (2) \\ & \sum_{j \in J}{Y_j} = p && & (3) \\ & \sum_{i \in I}{a_i X_{ik}} \leq {Y_{k} c_{k}} && \forall k \in k_{i} & (4) \\ & X_{ij} \leq Y_{j} && \forall i \in I \quad \forall j \in J & (5) \\ & X_{ij} \in \{0, 1\} && \forall i \in I \quad \forall j \in J & (6) \\ & Y_j \in \{0, 1\} && \forall j \in J & (7) \\ & && & \\ \displaystyle \textbf{Where} && i & = & \textrm{index of demand points/areas/objects in set } I \\ && j & = & \textrm{index of potential facility sites in set } J \\ && p & = & \textrm{the number of facilities to be sited} \\ && a_i & = & \textrm{service load or population demand at client location } i \\ && k_{i} & = & \textrm{the } k \textrm{nearest facilities of client location } i \\ && c_{j} & = & \textrm{the capacity of facility} j \\ && d_{ij} & = & \textrm{shortest distance or travel time between locations } i \textrm{ and } j \\ && X_{ij} & = & \begin{cases} 1, \textrm{if client location } i \textrm{ is served by facility } j \\ 0, \textrm{otherwise} \\ \end{cases} \\ && Y_j & = & \begin{cases} 1, \textrm{if a facility is sited at location } j \\ 0, \textrm{otherwise} \\ \end{cases} \\ && g_i & = & \begin{cases} 1, \textrm{if the client } i \textrm{ needs to be served by non-k-nearest facilities} \\ 0, \textrm{otherwise} \\ \end{cases} \\ \end{array}\end{split}\]
  Parameters:
    name `python:str`

      The problem name.

    ai_sum `Union`[`python:int`, `python:float`]

      The sum of weights representing the service loads of the clients.

    clients `np.array`

      An array of coordinates of clients.

    facilities `np.array`

      An array of coordinates of facilities.

    weights `np.array`

      An array of weights representing the service loads of the clients.

    k_array `np.array`

      An array of k values representing the number of nearest facilities for each client.

    p_facilities: int

      The number of facilities to be located.

    capacities `np.array` or `python:None`

      An array of facility capacities. None if capacity constraints are not considered.

    distance_metric `python:str`

      The distance metric used for computing distances between clients and facilities.

  Attributes:
    sparse_matrix `Compressed` `Sparse` `Row` `matrix`

      A cost matrix in the form of a compressed sparse row matrix between origins and destinations.

    aij `Compressed` `Sparse` `Row` `matrix`

      A weighted cost matrix in the form of a compressed sparse row matrix between origins and destinations.

    problem `pulp.LpProblem`

      A `pulp` instance of an optimization model that contains constraints, variables, and an objective function.

    fac2cli `numpy.array`

      A 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated. An empty client array indicates the facility is associated with no clients.

    cli2fac `numpy.array`

      The inverse of `fac2cli` where client to facility relationships are shown.

  __init__(name: str, ai_sum: int | float, clients: array, facilities: array, weights: array, k_array: array, p_facilities: int, capacities: array = None, distance_metric: str = 'euclidean')

    Initialize.

    Parameters:
      name `python:str`

        The desired name for the model.

  Methods

  `__init__`(name, ai_sum, clients, facilities, ...) | Initialize.
  `check_status`() | Ensure a model is solved.
  `client_facility_array`() | Create a 2D array storing client to facility relationships where each row represents a client and contains an array of facility indices with which it is associated.
  `facility_client_array`() | Create a 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated.
  `from_cost_matrix`(*args, **kwargs) | Warning: This method is not supported in the KNearestPMedian subclass.
  `from_geodataframe`(gdf_demand, gdf_fac, ...) | Create the object of KNearestPMedian class using input data.
  `get_mean_distance`() | Calculate the mean distance.
  `solve`(solver[, results]) | Solve the k-nearest p-median model.

  facility_client_array() → None

    Create a 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated. An empty client array indicates the facility is associated with no clients.

    Returns:
      `python:None`
  classmethod from_cost_matrix(*args, **kwargs)

    Warning: This method is not supported in the KNearestPMedian subclass.

  classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, weights_cols: str, p_facilities: int, facility_capacity_col: str = None, k_array: array = None, distance_metric: str = 'euclidean', name: str = 'k-nearest-p-median')

    Create the object of KNearestPMedian class using input data.

    Parameters:
      gdf_demand `GeoDataFrame`

        A GeoDataFrame containing demand points with their associated attributes.

      gdf_fac `GeoDataFrame`

        A GeoDataFrame containing facility points with their associated attributes.

      demand_col `python:str`

        The column name in gdf_demand representing the coordinate of each client.

      facility_col `python:str`

        The column name in gdf_fac representing the coordinate of each facility.

      weights_cols `python:str`

        The column name in gdf_demand representing the weights for each client.

      p_facilities: int

        The number of facilities to be located.

      facility_capacity_col `python:str`, optional

        The column name in gdf_fac representing the capacity of each facility, by default None.

      k_array `np.array`, optional

        An array of integers representing the k values for each client. If not provided, a default value of 5 or the number of facilities, whichever is smaller, will be used.

      distance_metric `python:str`, optional

        The distance metric to be used in calculating distances between clients and facilities, by default “euclidean”.

      name `python:str`, optional

        The name of the problem, by default “k-nearest-p-median”.

    Returns:
      `spopt.locate.p_median.KNearestPMedian`

    Examples

        >>> from spopt.locate import KNearestPMedian
        >>> import geopandas

    Create the input data and attributes.

        >>> k = np.array([1, 1])
        >>> demand_data = {
        ...    'ID': [1, 2],
        ...    'geometry': [Point(0.5, 1), Point(1.5, 1)],
        ...    'demand': [1, 1]}
        >>> facility_data = {
        ...    'ID': [101, 102],
        ...    'geometry': [Point(1,1), Point(0, 2), Point(2, 0)],
        ...    'capacity': [1, 1, 1]}
        >>> gdf_demand = geopandas.GeoDataFrame(demand_data, crs='EPSG:4326')
        >>> gdf_fac = geopandas.GeoDataFrame(facility_data, crs='EPSG:4326')

    Create and solve a `KNearestPMedian` instance from the geodataframe.

        >>> k_nearest_pmedian = KNearestPMedian.from_geodataframe(
        ...     gdf_demand, gdf_fac,'geometry','geometry', weights_cols='demand',
        ...     2, facility_capacity_col='capacity', k_array = k)
        >>> k_nearest_pmedian = k_nearest_pmedian.solve(pulp.PULP_CBC_CMD(msg=False))

    Get the facility-client associations.

        >>> for fac, cli in enumerate(k_nearest_pmedian.fac2cli):
        ...     print(f"facility {fac} serving {len(cli)} clients")
        facility 0 serving 1 clients
        facility 1 serving 1 clients
        facility 2 serving 0 clients

    Get the total and average weighted travel cost.

        >>> round(k_nearest_pmedian.problem.objective.value(), 3)
        1.618
        >>> round(k_nearest_pmedian.mean_dist, 3)
        0.809

    Get the k values for the last iteration.

        >>> print(k_nearest_pmedian.k_array)
        [2, 1]

  solve(solver: LpSolver, results: bool = True)

    Solve the k-nearest p-median model.

    This method iteratively solves the `KNearestPMedian` model using a specified solver until no more clients need to be assigned to placeholder facilities. The `k` values for clients are increased dynamically based on the presence of clients not assigned to `k` nearest facilities.

    Parameters:
      solver `pulp.LpSolver`

        The solver to be used for solving the optimization model.

      results bool (default `python:True`)

        If `True` it will create metainfo (which facilities cover which demand) and vice versa, and the uncovered demand.

    Returns:
      `spopt.locate.p_median.KNearestPMedian`