[PYTHON] Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints

Typical problem and execution method

Facility placement problem without capacity constraints

A set of customers (demand points) $ D $ and a set of facility placement points $ F $ are given. Each customer $ i \ in D $ always moves to one of the facilities $ i \ in F $. There is no capacity in each facility. Find the customer's destination so as to minimize the sum of the customer's capacity and distance traveled. However, the facility can only be used up to $ p $.

Execution method

usage

Signature: facility_location_without_capacity(p, point, cand=None, func=None)
Docstring:
Facility placement problem without capacity constraints
    P-Median problem: Minimizing the sum of total distances
input
    p:Maximum number of facilities
    point:List of customer locations
    cand:List of facility candidate locations(If None, same as point)
    func:Customer position index,Weight function with facility candidate index as an argument
output
Facility number list for each customer

python

from ortoolpy import facility_location_without_capacity
facility_location_without_capacity(2, [(1, 0), (0, 1), (2, 2)])

result

[1, 1, 2]

python

# pandas.DataFrame
from ortoolpy.optimization import FacilityLocationWithoutCapacity
FacilityLocationWithoutCapacity('data/facility.csv',2)

data

• data/facility.csv