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

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-median 문제(PMP) 정리

 

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

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

[최적화] p-center 문제 정리

 

p-centdian 문제는 p-median 문제와 p-center 문제를 통합한 형태의 문제로, 두 가지 목적 함수를 조절하는 가중치 w를 사용하여 최적화하는 문제입니다. p-centdian 문제는 주어진 지역 내에서 p개의 시설을 선택하여 전체 수요를 최소화하면서, 최대 이동 거리도 최소화하려는 문제입니다.

주어진 수식에서:
- `Zmedian`: p-median 문제의 목적 함수 (전체 수요를 최소화하는데 필요한 거리)
- `Zcenter`: p-center 문제의 목적 함수 (모든 수요 지점의 최대 이동 거리를 최소화하는데 필요한 거리)
- `w`: 두 목적 함수 간의 가중치 (0부터 1 사이의 값)

이 문제의 목적은 p-median 문제의 해와 p-center 문제의 해를 trade-off하면서 최적화하는 것입니다. `w` 값에 따라서 두 목적 함수 간의 중요도를 조절할 수 있습니다. `w`가 0에 가까울수록 p-center 목적이 강조되며, 1에 가까울수록 p-median 목적이 강조됩니다. 이를 통해 다양한 상황에 대한 해를 얻을 수 있습니다.

p-centdian 문제 역시 최적화 알고리즘을 사용하여 해결할 수 있으며, 가중치 `w`를 조절하면서 다양한 해를 얻을 수 있는 장점을 가지고 있습니다.

https://chat.openai.com/share/465bd24c-4141-4b5e-b333-a231e0eedb42

def solve_p_centdian(df, p, w=0.5):
    prob = pulp.LpProblem('p_centdian', 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')

    # 목적 함수
    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:
                distance = distance_row['distance'].values[0]
                prob += w * distance * x[origin][destination]
                prob += (1-w) * x[origin][destination] * distance <= M

    # 제약 조건
    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()

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

centdians = solve_p_centdian(df, 6, 0.5)
print(centdians)

이 파이썬 코드는 p-centdian 문제를 해결하는 최적화 코드입니다. p-centdian 문제는 주어진 원점과 목적지 사이에서 특정 수(p)의 중앙 위치(centdian)를 찾는 문제입니다. 코드는 pulp 라이브러리를 이용하여 선형 프로그래밍 문제를 정의하고 해결합니다.

코드 설명:

변수 선언

• x: 원점(origin_locations)에서 목적지(destination_locations)로 이동하는 결정 변수입니다. 이는 이진 변수(0 또는 1)입니다.
• y: 목적지(destination_locations)가 centdian인지를 나타내는 이진 결정 변수입니다.
• M: 목적 함수에 사용되는 연속 변수입니다.

목적 함수(Objective Function)

• w * distance * x[origin][destination]: 거리와 결정 변수를 곱한 항을 w로 가중치를 주어 더합니다.
• (1-w) * x[origin][destination] * distance <= M: 목적지까지의 거리를 (1-w)로 가중치를 주어 M과 비교합니다.

제약 조건(Constraints)

1. 각 원점에서는 하나의 목적지로만 이동할 수 있습니다.
2. 원점에서 목적지로 이동이 가능하려면, 해당 목적지가 centdian이어야 합니다.
3. 선택할 수 있는 centdian의 수는 p개여야 합니다.

결과

• 문제를 풀고, 선택된 centdian의 위치를 반환합니다.

함수 호출

• solve_p_centdian(df, 6, 0.5): df 데이터프레임에서 p=6과 w=0.5로 설정하여 centdian 위치를 찾습니다.

주의할 점:

• origin_locations와 destination_locations 등은 함수 내부에서 정의되지 않았으므로, 이 코드를 그대로 실행하려면 이 변수들이 어디에서 오는지 확인이 필요합니다.
• df는 거리 정보가 들어있는 데이터프레임으로 추정되며, 이것도 외부에서 제공되어야 합니다.

이렇게 코드는 원점과 목적지 간의 최적의 p개의 centdian 위치를 찾아줍니다.