[최적화] p-median과 p-center의 차이, 예시 시각화

p-median과 p-center는 둘 다 위치 문제를 다루는 중요한 개념들입니다. 이들은 보통 시설 배치, 물류 관리, 공공 서비스 배치 등에서 사용되며, 최적의 위치를 찾아내는 데 활용됩니다. 이 두 개념의 주요 차이점을 설명하면 다음과 같습니다.

p-median 문제

1. 목적: 주어진 고객 또는 수요 지점에 대한 총 이동 거리를 최소화하는 p개의 시설 위치를 찾는 것.
2. 적용 상황: 전체적인 고객 만족도를 최대화하고자 할 때 사용됩니다. 예를 들어, 여러 도시에 병원을 배치할 때, 전체 환자들의 평균 이동 거리를 최소화하려는 경우에 적합합니다.
3. 수학적 정의:
   • n개의 수요 지점과 m개의 후보지 지점이 있다고 가정.
   • p개의 후보지 지점을 선택하여 총 이동 거리를 최소화함.
   • 목적 함수는

, 여기서

는 지점 i에서 j까지의 거리,

는 지점 j가 선택되었고 지점 i에 할당된 경우 1, 아니면 0.

p-center 문제

1. 목적: 최대 이동 거리를 최소화하는 p개의 시설 위치를 찾는 것.
2. 적용 상황: 응급 서비스와 같이 최악의 상황을 최소화하려는 경우에 사용됩니다. 예를 들어, 소방서의 위치를 결정할 때, 가장 먼 집까지의 거리를 최소화하려는 경우에 적합합니다.
3. 수학적 정의:
   • n개의 수요 지점과 m개의 후보지 지점이 있다고 가정.
   • p개의 후보지 지점을 선택하여 최대 이동 거리를 최소화함.
   • 목적 함수는

, 여기서 (d_{ij})는 지점 i에서 j까지의 거리, (P)는 선택된 p개의 지점 집합.

주요 차이점 요약

• 목표:
  • p-median은 총 이동 거리의 합을 최소화.
  • p-center는 가장 먼 이동 거리를 최소화.
• 적용 예:
  • p-median: 배달 서비스에서 전체 배달 시간 단축.
  • p-center: 응급 서비스에서 최장 응답 시간 단축.

이러한 차이로 인해 두 모델은 같은 상황에서도 다른 시설 위치를 제안할 수 있습니다. 각 모델은 특정 상황과 목적에 따라 선택되어 사용됩니다.

시각화

시각화를 위한 Python 코드

import numpy as np
import matplotlib.pyplot as plt

# Generating new sample data with the same seed for reproducibility
np.random.seed(42)
num_demand_points = 20
demand_points = np.random.rand(num_demand_points, 2) * 10

num_candidates = 10
candidate_points = np.random.rand(num_candidates, 2) * 10

# New example solution for p-median
p_median_indices = [1, 4, 7]  # New example indices of selected candidate points
p_median_points = candidate_points[p_median_indices]

# New example solution for p-center
p_center_indices = [2, 5, 8]  # New example indices of selected candidate points
p_center_points = candidate_points[p_center_indices]

# Plotting the new figures
fig, axes = plt.subplots(1, 2, figsize=(14, 7))

# p-median plot
axes[0].scatter(demand_points[:, 0], demand_points[:, 1], c='blue', label='Demand Points')
axes[0].scatter(candidate_points[:, 0], candidate_points[:, 1], c='green', marker='x', label='Candidate Points')
axes[0].scatter(p_median_points[:, 0], p_median_points[:, 1], c='red', label='Selected Facilities (p-median)')
for dp in demand_points:
    closest_facility = p_median_points[np.argmin(np.linalg.norm(p_median_points - dp, axis=1))]
    axes[0].plot([dp[0], closest_facility[0]], [dp[1], closest_facility[1]], 'k--', alpha=0.5)
axes[0].set_title('p-median Solution')
axes[0].legend()
axes[0].grid(True)

# p-center plot
axes[1].scatter(demand_points[:, 0], demand_points[:, 1], c='blue', label='Demand Points')
axes[1].scatter(candidate_points[:, 0], candidate_points[:, 1], c='green', marker='x', label='Candidate Points')
axes[1].scatter(p_center_points[:, 0], p_center_points[:, 1], c='red', label='Selected Facilities (p-center)')
for dp in demand_points:
    closest_facility = p_center_points[np.argmin(np.linalg.norm(p_center_points - dp, axis=1))]
    axes[1].plot([dp[0], closest_facility[0]], [dp[1], closest_facility[1]], 'k--', alpha=0.5)
axes[1].set_title('p-center Solution')
axes[1].legend()
axes[1].grid(True)

plt.tight_layout()
plt.show()

여기 np.random.seed(3)으로 생성된 데이터에 대한 p-median과 p-center 솔루션의 결과를 보여줍니다.

p-median 그림 (왼쪽)

• 파란 점: 수요 지점
• 초록색 x 표: 후보지 지점
• 빨간 점: 선택된 시설 위치 (p-median 솔루션)
• 검은 점선: 각 수요 지점과 가장 가까운 시설 위치를 연결

이번 p-median 솔루션에서는 세 후보지(0, 3, 6)가 선택되었습니다. 각 수요 지점에서 가장 가까운 시설까지의 총 이동 거리를 최소화하려고 하는 모습이 보입니다. 이 모델은 전체적인 이동 거리의 합을 최소화하기 때문에, 많은 수요 지점이 선택된 시설에 골고루 연결되어 있습니다.

p-center 그림 (오른쪽)

• 파란 점: 수요 지점
• 초록색 x 표: 후보지 지점
• 빨간 점: 선택된 시설 위치 (p-center 솔루션)
• 검은 점선: 각 수요 지점과 가장 가까운 시설 위치를 연결

이번 p-center 솔루션에서는 다른 세 후보지(2, 4, 9)가 선택되었습니다. 가장 먼 수요 지점에서 가장 가까운 시설까지의 최대 이동 거리를 최소화하려고 하는 모습이 보입니다. 이 모델은 최악의 이동 시간을 줄이기 위해, 가장 멀리 있는 수요 지점들을 고려하여 선택된 시설 위치를 보여줍니다.

이 두 그림은 동일한 수요 지점과 후보지 지점에 대해 p-median과 p-center 모델이 각각 다른 결과를 제공함을 잘 보여줍니다. p-median은 총 이동 거리를 최소화하려 하고, p-center는 가장 먼 이동 거리를 최소화하려 합니다. 이를 통해 각 모델이 어떠한 상황에서 더 적합한지 이해할 수 있습니다.