(구로비) 파이썬으로 PMP(P-Median Problems) 풀기

by

P-중앙값 알고리즘

P-median 문제는 공장, 창고, 물류센터, 공공시설 등을 설치할 수 있는 후보지가 주어진다고 가정하고, 각 후보지는 소비자의 수요가 있는 지역과 어떤 시설에서 어떤 시설로든 제품을 운송하는 데 필요한 단위를 나타냅니다.
소비자 운송비와 운송거리가 각각 주어졌다고 가정하면 최소한의 운송비로 모든 소비자의 니즈를 충족시킬 수 있는 p개 이하의 시설물 설치위치를 결정하는 것이 문제가 된다.
설비 나. 가공공장, 백화점, 대형할인점, 자동차판매소 등 경쟁사와의 경쟁이 치열한 민간시설, 통신 및 송전집중장치의 부지문제, 건설 배관 시스템의 문제 등 현장에서 자주 발생하는 문제입니다.

박보라, 이규진, 최기추. (2013). 휴리스틱 P-중앙값 알고리즘을 이용한 자전거 주차 공간의 최적 위치 선정. 대한토목학회지, 33(5), 1989-1998. https://doi.org/10.12652/KSCE.2013.33.5.1989

P-중앙값 구로비 코드

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

'추천 관련글,

인용하다

재료

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

*설치 지침*: pip install gurobipy 입력

pip install gurobipy

암호

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()


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


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


#Gráficar la solución
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()