[최적화] P-median 문제(PMP) 정리, 파이썬 코드

p-median 문제는 시설 위치 문제 중 하나로, 주어진 지역 내에서 p개의 시설을 선택하여 전체 수요를 최소화하며, 각 수요 지점과 선택된 시설 사이의 거리를 고려하는 문제입니다. 주로 공급망, 운송, 서비스 분야에서 사용됩니다.

문제의 변수 및 제약 조건은 다음과 같습니다:

- **변수:**

• `xij`: i번째 수요 지점과 j번째 시설 사이의 연결 여부를 나타내는 바이너리 변수 (0 또는 1)
• `yj`: j번째 시설이 선택되었는지를 나타내는 바이너리 변수 (0 또는 1)

- **목적 함수:**

• 목적은 주어진 수요 지점들과 선택된 시설 사이의 거리를 고려하여 전체 거리를 최소화하는 것입니다.
• `dij`: i번째 수요 지점과 j번째 시설 사이의 거리
• `a`: 거리에 대한 가중치 또는 비용 계수

- **제약 조건:**

1. 모든 수요 지점은 정확히 하나의 시설과 연결되어야 합니다.
2. 선택된 시설의 수는 p개여야 합니다.
3. 수요 지점 i가 시설 j에 연결되려면, xij와 yj 모두가 1이어야 합니다.
4. xij는 yj보다 크지 않아야 합니다.

이 문제는 p-median 문제를 정의한 것이며, 이를 해결하는 목적은 주어진 제약 조건 하에서 목적 함수(Zmedian)를 최소화하는 xij와 yj의 값을 찾는 것입니다. 일반적으로 이러한 조합적 최적화 문제는 다양한 알고리즘과 접근 방법을 사용하여 해결할 수 있습니다.

P-median 파이썬 코드

GPT 4.0

https://chat.openai.com/share/1b8b7c44-3976-4205-ab86-2ea1c0cf4560

ChatGPT

 

p-median 문제는 주어진 위치 데이터 집합에서 p 개의 중앙 위치(medians)를 선택하여 모든 위치로부터의 총 거리를 최소화하는 위치들을 찾는 최적화 문제입니다.

p-median 문제를 해결하기 위해 파이썬에서 사용할 수 있는 몇 가지 방법이 있지만, 여기서는 PuLP라는 선형 프로그래밍 패키지를 사용하여 문제를 모델링하고 해결하는 방법을 제시하겠습니다.

먼저, 필요한 라이브러리와 엑셀 데이터를 가져옵니다:

import pandas as pd
import pulp

# 엑셀 파일 로드 (예: 'data.xlsx')
df = pd.read_excel('data.xlsx')

# 거리 데이터 예상
# - 'origin'과 'destination' 열에는 경위도 좌표가 있어야 함
# - 'distance' 열에는 두 위치 사이의 거리가 있어야 함
print(df.head())

이제 p-median 문제를 모델링합니다:

def solve_p_median(df, p):
    locations = df['origin'].unique()

    # 문제 정의
    prob = pulp.LpProblem('p_median', pulp.LpMinimize)

    # 변수
    x = pulp.LpVariable.dicts('x', (locations, locations), 0, 1, pulp.LpBinary)
    y = pulp.LpVariable.dicts('y', locations, 0, 1, pulp.LpBinary)

    # 목적 함수
    prob += pulp.lpSum(df['distance'] * x[origin][destination] for origin, destination in df[['origin', 'destination']].values)

    # 제약 조건
    for origin in locations:
        prob += pulp.lpSum(x[origin][destination] for destination in locations) == 1
        for destination in locations:
            prob += x[origin][destination] <= y[destination]

    prob += pulp.lpSum(y[location] for location in locations) == p

    # 문제 풀기
    prob.solve()

    # 선택된 위치 반환
    medians = [location for location in locations if y[location].value() == 1]
    return medians

# 3개의 중앙 위치를 찾기 위해 함수 호출
medians = solve_p_median(df, 3)
print(medians)

위의 코드는 p-median 문제를 선형 프로그래밍으로 모델링하고, 주어진 데이터에서 3개의 중앙 위치를 찾습니다. data.xlsx 파일은 'origin', 'destination', 'distance' 열을 포함해야 합니다.

참고로, p-median 문제는 NP-hard 문제이므로 큰 데이터셋에 대해서는 해결하는 데 오랜 시간이 걸릴 수 있습니다.

 

 

 

 

이 파이썬 코드는 p-median 문제를 풀기 위해 작성되었습니다. p-median 문제는 일종의 위치 결정 문제입니다. 특히, 주어진 여러 개의 "원점"과 "목적지" 사이에서 p개의 "미디언"을 선택하여 전체 거리를 최소화하려는 문제입니다.

파이썬 라이브러리인 PuLP를 이용하여 이 문제를 풀고 있습니다. PuLP는 선형 및 정수 프로그래밍 문제를 풀 수 있는 라이브러리입니다.

코드를 분석해보겠습니다.

 

 

---

def solve_p_median(df, p):
    prob = pulp.LpProblem('p_median', pulp.LpMinimize)

    x = pulp.LpVariable.dicts('x', (origin_locations, destination_locations), 0, 1, pulp.LpBinary)
    y = pulp.LpVariable.dicts('y', destination_locations, 0, 1, pulp.LpBinary)

    # 목적 함수
    for origin in origin_locations:
        for destination in destination_locations:
            distance_row = df[(df['O_x'] == origin[0]) & (df['O_y'] == origin[1]) &
                              (df['D_x'] == destination[0]) & (df['D_y'] == destination[1])]

            if not distance_row.empty:
                prob += distance_row['distance'].values[0] * x[origin][destination]

    # 제약 조건
    for origin in origin_locations:
        prob += pulp.lpSum(x[origin][destination] for destination in destination_locations) == 1

        for destination in destination_locations:
            prob += x[origin][destination] <= y[destination]

    prob += pulp.lpSum(y[location] for location in destination_locations) == p

    prob.solve()

    medians = [location for location in destination_locations if y[location].value() == 1]
    return medians

medians = solve_p_median(df, 6)
print(medians)

 

함수 정의

def solve_p_median(df, p):

df는 원점과 목적지, 그리고 그 사이의 거리 정보가 들어있는 데이터프레임입니다. p는 선택할 "미디언"의 개수입니다.

변수 선언

x = pulp.LpVariable.dicts('x', (origin_locations, destination_locations), 0, 1, pulp.LpBinary)
y = pulp.LpVariable.dicts('y', destination_locations, 0, 1, pulp.LpBinary)

x와 y는 문제의 결정 변수입니다.

• x[origin][destination]: 원점 origin에서 목적지 destination까지의 연결을 나타내며, 이진 변수입니다.
• y[destination]: 목적지 destination이 선택되었는지 여부를 나타내는 이진 변수입니다.

목적 함수

목적 함수는 선택된 "미디언"에 따른 전체 거리를 최소화하려고 합니다.

제약 조건

1. 각 원점은 정확히 하나의 목적지에 연결되어야 합니다.
2. 원점과 목적지 사이의 연결은 해당 목적지가 "미디언"으로 선택되었을 때만 가능합니다.
3. 정확히 p개의 "미디언"이 선택되어야 합니다.

문제 풀이

prob.solve()

PuLP를 이용해 문제를 풉니다.

결과 추출

선택된 "미디언"의 위치를 반환합니다.

코드에서 주의할 점은 origin_locations와 destination_locations이 어디에서 정의되었는지 명확하지 않다는 것입니다. 이 두 변수는 외부에서 정의되어야 할 것 같습니다. 또한, df의 구조와 어떤 정보를 담고 있는지도 명확하지 않습니다. 이 정보에 따라 코드의 작동 방식이 달라질 수 있습니다.