[최적화] p-centdian greedy 휴리스틱 파이썬 코드

import pandas as pd

def greedy_p_centdian(df, p, w):
    unique_Dids = df['Did'].unique()
    selected_combination = []

    while len(selected_combination) < p:
        min_obj = float('inf')
        selected_Did = None
        for Did in unique_Dids:
            if Did in selected_combination:
                continue

            temp_combination = selected_combination + [Did]
            subset_df = df[df['Did'].isin(temp_combination)].copy()

            # Zmedian 계산
            subset_df = subset_df.loc[subset_df.groupby('Oid')['distance'].idxmin()]
            Zmedian = (subset_df['distance'] * subset_df['demand']).sum()

            # 수요를 고려한 Zcenter 계산
            weighted_distances = subset_df['distance'] * subset_df['demand']
            Zcenter = weighted_distances.max()

            obj = w * Zmedian + (1 - w) * Zcenter

            if obj < min_obj:
                min_obj = obj
                selected_Did = Did

        selected_combination.append(selected_Did)

    # 최종 결과 계산
    subset_df = df[df['Did'].isin(selected_combination)].copy()
    subset_df = subset_df.loc[subset_df.groupby('Oid')['distance'].idxmin()]
    final_Zmedian = (subset_df['distance'] * subset_df['demand']).sum()
    weighted_distances = subset_df['distance'] * subset_df['demand']
    final_Zcenter = weighted_distances.max()

    result = {
        'combination': selected_combination,
        'final_Zmedian': final_Zmedian,
        'final_Zcenter': final_Zcenter,
        'final_obj': w * final_Zmedian + (1 - w) * final_Zcenter
    }

    return result

# 예시
# p는 시설의 개수, w는 가중치입니다.
# df는 사용자가 지정한 데이터 프레임입니다.
p = 3
w = 0.5
result = greedy_p_centdian(df, p, w)
print(result)

이 코드는 p-centdian 문제를 해결하기 위한 탐욕 알고리즘(greedy algorithm)을 구현한 것입니다. p-centdian 문제는 미리 정의된 여러 위치 중에서 p개의 위치를 선택하여, 주어진 점들과 선택된 위치 사이의 거리를 최소화하는 문제입니다.

이 코드는 다음과 같이 작동합니다:

1. 준비 단계
   • 주어진 데이터프레임 df에서 고유한 Did 값을 가져와 unique_Dids에 저장합니다.
   • selected_combination은 선택된 Did의 리스트로, 초기에는 비어있습니다.
   • p는 선택해야 하는 시설의 수이고, w는 가중치입니다.
2. 탐욕 알고리즘 수행
   • 선택된 Did의 개수가 p보다 작은 동안 다음을 반복합니다.
     • 각 Did에 대하여
       • Did가 이미 selected_combination에 있다면 건너뜁니다.
       • 현재의 Did를 selected_combination에 추가하여 temp_combination을 만듭니다.
       • temp_combination에 있는 Did를 포함하는 행만 선택하여 subset_df를 만듭니다.
       • Zmedian을 계산합니다. 이는 각 객체 Oid에 대하여 최소 거리를 가지는 행만 선택하여, 거리와 수요(demand)의 가중 평균을 구합니다.
       • 수요를 고려한 Zcenter를 계산합니다. 이는 각 거리에 수요를 곱한 값 중 최대값입니다.
       • obj를 계산합니다. 이는 w * Zmedian + (1 - w) * Zcenter로, Zmedian과 Zcenter의 가중 합입니다.
       • 만약 obj가 min_obj보다 작다면, min_obj와 selected_Did를 갱신합니다.
     • selected_combination에 selected_Did를 추가합니다.
3. 최종 결과 계산
   • 최종 선택된 Did들로부터 subset_df를 만들고, 최종 Zmedian, Zcenter, 그리고 final_obj를 계산합니다.
   • 계산 결과는 딕셔너리 형태로 반환됩니다.

예시

이 코드는 사용자가 지정한 데이터 프레임 df에 대하여, 시설의 개수 p와 가중치 w를 인자로 받아 결과를 출력합니다. 예제에서는 p가 3이고 w가 0.5입니다. 따라서 코드는 3개의 시설을 선택하여 Zmedian과 Zcenter의 가중 합을 최소화하려고 시도합니다.