[공간 최적화] P-center을 유전자 알고리즘으로 구현하기

 

 

import pandas as pd

# 엑셀 파일 로드 (예: 'data.xlsx')
df = pd.read_csv('whole.csv', encoding = 'utf-8')

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

 

 

 

 

def p_center_heuristic(df, p):
    # 후보지와 고객의 unique id를 찾기
    candidate_ids = df['Did'].unique()
    customer_ids = df['Oid'].unique()

    # 센터로 선택된 후보지들을 저장할 리스트
    centers = []

    # objective value 초기화
    obj_value = -1

    # p개의 센터를 찾을 때까지 반복
    for _ in range(p):
        max_min_distance = -1
        best_candidate = None

        # 모든 후보지에 대하여 반복
        for candidate_id in candidate_ids:
            if candidate_id in centers:
                continue

            # 이 후보를 센터로 할 때, 모든 고객과의 거리 중 최소 거리를 찾음
            min_distances = []
            for customer_id in customer_ids:
                # 센터로 선택된 후보지를 포함하여 거리 계산
                distances = df[(df['Oid'] == customer_id) & (df['Did'].isin(centers + [candidate_id]))]
                if not distances.empty:  # distances 리스트가 비어있지 않을 때만 min() 함수 호출
                    # 가중치 적용
                    weighted_distance = (distances['distance'] * distances['demand']).min()
                    min_distances.append(weighted_distance)

            # 최소 거리들 중 최대값을 찾음
            if min_distances:  # min_distances 리스트가 비어있지 않을 때만 max() 함수 호출
                current_max_min_distance = max(min_distances)
                # 이전에 찾은 후보지들보다 더 좋은지 확인
                if best_candidate is None or current_max_min_distance < max_min_distance:
                    best_candidate = candidate_id
                    max_min_distance = current_max_min_distance

        # 최적의 후보지를 센터로 추가
        if best_candidate is not None:
            centers.append(best_candidate)
            obj_value = max_min_distance  # objective value 업데이트

    # 고객별 할당된 센터 저장
    assignments = {}
    for customer_id in customer_ids:
        min_distance = float('inf')
        assigned_center = None
        for center_id in centers:
            distance = df[(df['Oid'] == customer_id) & (df['Did'] == center_id)]['distance'].min()
            if distance < min_distance:
                min_distance = distance
                assigned_center = center_id
        assignments[customer_id] = assigned_center


    return centers, obj_value, assignments




# 사용자로부터 p 값(센터의 개수) 입력받기
p = int(input("Enter the number of centers (p): "))

# 휴리스틱하게 p-center 찾기
centers, obj_value, assignments = p_center_heuristic(df, p)
print("Selected Centers: ", centers)
print("Objective Value: ", obj_value)
print("Assignments:")
for oid, did in assignments.items():
    print(f"Customer {oid} is assigned to Center {did}")