[Gurobi] 구로비로 P-median 문제 (PMP) 풀기 with Python :: gurobipy

P-median 알고리즘

P-Median 문제는 공장, 창고, 물류센터 또는 공공시설 등을 설치할 수 있는 후보입지가 주어져 있다고 가정하고 각 후보입지는 소비자 수요 발생지역을 나타내며 각 시설로부터 각 소비자에게 제품을 수송할 때 소요되는 단위 당 수송비와 수송거리 가 주어져 있다고 가정할 때, 최소의 수송비용으로 모든 소비자의 수요를 충족시킬 수 있는 p개 이하의 시설 설치 입지를 결정하는 문제로써, 경찰서, 소방서, 전화국, 공공의료시설, 환경처리시설 등과 같은 공공시설이나 백화점, 대형할인매장, 자동차영업소 등과 같이 경쟁사들과의 경쟁이 치열한 민간시설의 입지선정 문제나 통신 및 전력수송 집선장치 위치선정 문제, 파이프라인 시스템 설계문제 등과 같은 많은 응용분야에서 자주 발생되는 문제이다.

 

Park, Bora, LEE, Kyu Jin, & Choi, Keechoo. (2013). 휴리스틱 P-Median 알고리즘을 이용한 자전거주차장 최적입지선정. 대한토목학회논문집, 33(5), 1989–1998. https://doi.org/10.12652/KSCE.2013.33.5.1989

 

구로비 설치

https://kimhongsi.tistory.com/entry/Gurobi-%EC%B5%9C%EC%A0%81%ED%99%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8-%EA%B5%AC%EB%A1%9C%EB%B9%84-%EB%AC%B4%EB%A3%8C-%ED%95%99%EC%83%9D%ED%8C%90-%EB%8B%A4%EC%9A%B4%EB%A1%9C%EB%93%9C

[Gurobi] 최적화 프로그램 구로비 무료 학생판 다운로드

구로비 설치는 여기 참고!

 

 

https://www.youtube.com/watch?v=AYe5xQOm5hU 

를 참고함

 

 

https://kimhongsi.tistory.com/entry/Gurobi-%EA%B5%AC%EB%A1%9C%EB%B9%84%EB%A1%9C-P-center-%EB%AC%B8%EC%A0%9C-%ED%92%80%EA%B8%B0-with-Python-gurobipy

[Gurobi] 구로비로 P-center 문제 풀기 with Python :: gurobipy

P-median이 아닌, P-center가 필요하면 이곳 참고 

 

준비물

구로비가 설치된 파이썬 환경

        *설치방법* : pip install gurobipy 입력

pip install gurobipy

p-median

 

 

코드

from gurobipy import *
import numpy as np
import matplotlib.pyplot as plt

#노드 개수:
N=21

#x.y 좌표:
np.random.seed(1)
X = list (np.random.random(N)*100)
Y = list(np.random.random(N)*100)

#수요량
demanda = list (np.random.randint (low=10,high=50,size=N))

#시각화:
plt.figure(figsize=(12,5))
plt.scatter(X,Y,color='blue')

for i in range(len(X)):
    plt.annotate('$d_{%d}=%d$'%(i, demanda[i]),(X[i]-0.5,Y[i]-5))
    
plt.xlabel("X axis")
plt.ylabel("Y axis")
plt.title("nodes")
plt.show()

# 세트:
nodos = [i for i in range(N)]
ubicaciones = [i for i in nodos]
arcos = [(i,j) for i in nodos for j in ubicaciones]

#최대 위치 수:
P=5

#거리 행렬:
distancia = {(i,j): np.hypot (X[i]-X[j],Y[i]-Y[j]) for i in nodos for j in ubicaciones}

#P-median
model = Model('P-Median')

#결정변수
x = model.addVars(arcos,vtype = GRB.BINARY, name = 'X')
y = model.addVars(ubicaciones,vtype = GRB.BINARY, name = 'Y')

#목적함수
model.setObjective(quicksum(distancia[i,j]*x[i,j] for i,j in arcos),GRB.MINIMIZE)

#제약조건
model.addConstrs (quicksum(x[i,j] for j in ubicaciones) == 1 for i in nodos)
model.addConstr(quicksum(y[j] for j in ubicaciones) <= P)
model.addConstrs(x[i,j]-y[j] <= 0 for i in nodos for j in ubicaciones)
model.optimize()

#ubicaciones Activos:
ubicaciones_activos = [k for k in ubicaciones if y[k].x > 0.9]
print(ubicaciones_activos)

ubicaciones_activos는 몇번 노드가 선택되었는지 보여준다.

#Arcos Activos:
arcos_activos = [ k for k in arcos if x[k].x >0.9]
print(arcos_activos)

참고

nodos = [i for i in range(N)]
ubicaciones = [i for i in nodos]
arcos = [(i,j) for i in nodos for j in ubicaciones]

 

accos는 순서 쌍을 말한다. (노드번호, 어떤 노드로 할당되었는지)

#Gráficar la solución
from colour import Color
plt.figure(figsize=(12,5))
plt.scatter(X,Y,color='blue')

for n in ubicaciones_activos:
    plt.scatter (X[n],Y[n],color='green',marker='D')
    
for i in range (len(X)):
    plt.annotate('$d_{%d}=%d$'  % (i,demanda[i]),(X[i]-0.5,Y[i]-5))
    
for n in arcos_activos:
    i=n[0]
    j=n[1]
    
    plt.plot([X[i],X[j]],[Y[i],Y[j]])

plt.xlabel ("X axis")
plt.ylabel("Y axis")
plt.title("Nodes")
plt.show()