[최적화] p-center 문제 정리, 파이썬 코드

p-median 문제는 이곳으로

https://kimhongsi.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94-P-median-%EB%AC%B8%EC%A0%9CPMP-%EC%A0%95%EB%A6%AC

[최적화] P-median 문제(PMP) 정리

 

p-centdian 문제는 이곳으로

https://kimhongsi.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94-p-centdian-%EB%AC%B8%EC%A0%9C-%EC%A0%95%EB%A6%AC

[최적화] p-centdian 문제 정리, 파이썬 코드

 

p-median 문제와 유사하지만, 차이점은 거리 대신 최대 거리를 최소화하려는 것입니다. 즉, 모든 수요 지점의 최대 이동 거리를 최소화하는 것이 목표입니다.

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

- **변수:**

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

- **목적 함수:**

• 목적은 모든 수요 지점의 최대 이동 거리를 최소화하는 것입니다.
• `dij`: i번째 수요 지점과 j번째 시설 사이의 거리
• `a`: 거리에 대한 가중치 또는 비용 계수
• `W`: 모든 수요 지점의 최대 이동 거리

- **제약 조건:**

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

이 문제 역시 p-center 문제를 정의한 것이며, 이를 해결하는 목적은 주어진 제약 조건 하에서 목적 함수(Zcenter)를 최소화하는 xij와 yj의 값을 찾는 것입니다. 이러한 종류의 문제도 다양한 최적화 알고리즘을 활용하여 효과적으로 해결할 수 있습니다.

 

 

 

파이썬 코드

GPT 4.0

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

ChatGPT

 

 

 

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

여기서는 PuLP라는 선형 프로그래밍 패키지를 사용하여 p-center 문제를 모델링하고 해결합니다.

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

import pandas as pd
import pulp

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

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

2. p-center 문제를 모델링합니다:

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

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

    # 변수
    x = pulp.LpVariable.dicts('x', (locations, locations), 0, 1, pulp.LpBinary)
    y = pulp.LpVariable.dicts('y', locations, 0, 1, pulp.LpBinary)
    M = pulp.LpVariable('M', lowBound=0, cat='Continuous')  # 최대 거리 변수

    # 목적 함수
    prob += M

    # 제약 조건
    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 += x[origin][destination] * df[(df['origin'] == origin) & (df['destination'] == destination)]['distance'].values[0] <= M

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

    # 문제 풀기
    prob.solve()

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

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

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

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

 

 

import pandas as pd
import pulp

# CSV 파일 로드
df = pd.read_csv('/content/test_.csv')

# 고유한 위치 목록 생성
origin_locations = df[['O_x', 'O_y']].drop_duplicates().to_records(index=False).tolist()
destination_locations = df[['D_x', 'D_y']].drop_duplicates().to_records(index=False).tolist()

def solve_p_center(df, p):
    # 문제 정의
    prob = pulp.LpProblem('p_center', 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)
    M = pulp.LpVariable('M', lowBound=0, cat='Continuous')  # 최대 거리 변수

    # 목적 함수
    prob += M

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

        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:
                distance = distance_row['distance'].values[0]
                prob += x[origin][destination] * distance <= M
            prob += x[origin][destination] <= y[destination]  # y값에 따라 x값 제한

    # 중앙 위치의 총 개수는 p개여야 합니다.
    prob += pulp.lpSum(y[location] for location in destination_locations) == p

    # 문제 풀기
    prob.solve()
    
    # 선택된 위치 반환
    centers = [location for location in destination_locations if y[location].value() == 1]
    return centers

# 예: 3개의 중앙 위치를 찾기 위해 함수 호출
centers = solve_p_center(df, 5)
print(centers)

 

 

 

 

여기에서 ?가 p-center로 선택된 지점