Combinatorial optimization-Typical problem-Facility placement problem

Typical problem and execution method

Facility placement problem

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

Execution method

usage


Signature: facility_location(p, point, cand, func=None)
Docstring:
Facility placement problem
    P-Median problem: Minimizing the sum of total distance x quantity
input
    p:Maximum number of facilities
    point:List of customer locations and quantities
    cand:List of facility candidate locations and capacities
    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
facility_location(2, [(1, 0, 1), (0, 1, 1), (2, 2, 1)], 
                     [(1, 0, 1), (0, 1, 1), (2, 2, 2)])

result


[0, 2, 2]

python


# pandas.DataFrame
from ortoolpy.optimization import FacilityLocation
FacilityLocation('data/facility.csv',2)
x y demand capacity id
0 1 0 1.0 1.0 0.0
1 0 1 NaN 1.0 NaN
2 0 1 1.0 NaN 3.0
3 2 2 1.0 2.0 3.0

data

Recommended Posts

Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-typical problems and execution methods