🚚 물류 최적 운송경로 계산 & 네트워크 가시화

1️⃣ 목표: 최적 운송 경로 산출 & 네트워크 시각화

이번 포스팅에서는 supply.csv 와 demand.csv 두 개의 데이터만을 이용해:

✅ 각 창고(W)와 공장(F)의 공급/수요 데이터 확인 ✅ 최적 운송 경로(코스트 최소화) 산출 ✅ NetworkX로 네트워크 가시화

까지 진행해봅니다.

---

2️⃣ 데이터 살펴보기

📦 supply.csv (공급량)

W1W2W3

35

41

42

🏭 demand.csv (수요량)

F1	F2	F3	F4
28	29	31	25

✅ 총 공급량 = 35+41+42 = 118 ✅ 총 수요량 = 28+29+31+25 = 113

👉 공급량이 더 많아 공급 초과 상태 (페널티 없이 가능)

---

3️⃣ 최적 운송경로 계산 (Linear Sum Assignment)

이번 단계에서는 헝가리안 알고리즘 (Hungarian Algorithm) 으로도 알려진 Linear Sum Assignment 방법을 사용해 최적 운송 경로를 계산합니다.

📌 왜 이 알고리즘을 사용하는가?

• 이 문제는 창고(W)와 공장(F) 간 매칭 문제로, 각 창고-공장 쌍에 대해 운송 비용이 존재하고 그 비용의 총합을 최소화해야 합니다.
• 이는 수학적으로 이진 할당 문제 (Assignment Problem) 로 분류되며, Linear Sum Assignment는 이 문제를 효율적으로 풀어주는 대표적인 알고리즘입니다.
• 단순 탐색 방식은 계산량이 폭발적으로 증가하기 때문에, O(n³) 시간복잡도를 가진 헝가리안 알고리즘이 현실적인 선택입니다.

⚙️ 알고리즘 동작 방식 (과정별 데이터 변환 예시로 이해)

Linear Sum Assignment (Hungarian Algorithm)은 실제로 데이터를 어떻게 처리하면서 최적 매칭을 도출하는지 단계별로 살펴보겠습니다.

1️⃣ Step 1: 비용 행렬 작성

	F1	F2	F3	F4
W1	2	3	1	4
W2	3	2	2	3
W3	4	3	2	1

👉 각 값은 창고-공장 간 예상 운송비용입니다.

2️⃣ Step 2: 행 최소값 빼기 (Row Reduction)

• 각 행에서 가장 작은 값을 빼서 최소값이 0이 되게 만듭니다.

	F1	F2	F3	F4
W1	1	2	0	3
W2	1	0	0	1
W3	3	2	1	0

3️⃣ Step 3: 열 최소값 빼기 (Column Reduction)

• 각 열에서도 최소값을 빼서 0이 더 많이 등장하도록 변환합니다.

	F1	F2	F3	F4
W1	0	2	0	3
W2	0	0	0	1
W3	2	2	1	0

4️⃣ Step 4: 0 위치 기반 매칭

• 0이 있는 곳만 골라서 겹치지 않게 매칭합니다 (예: W1→F1, W2→F3, W3→F4).
• 만약 불가능할 경우 최소 커버 선을 추가해 다시 계산합니다.

5️⃣ Step 5: 최적 경로 도출

• 가능한 조합 중 가장 총 비용이 낮은 매칭을 선택하여 결과로 확정합니다.

👉 이런 과정을 거치면서 매칭이 결정되며, scipy의 linear_sum_assignment는 이 모든 과정을 내부적으로 자동으로 처리합니다.

---

4️⃣ 네트워크 가시화 (NetworkX)

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()

warehouses = list(supply.keys())
factories = list(demand.keys())

for w in warehouses:
    G.add_node(w)
for f in factories:
    G.add_node(f)

for r, c in zip(row_ind, col_ind):
    from_node = warehouses[r]
    to_node = factories[c]
    G.add_edge(from_node, to_node, weight=cost_matrix[r, c])

pos = {
    'W1': (0, 1), 'W2': (0, 2), 'W3': (0, 3),
    'F1': (3, 1), 'F2': (3, 2), 'F3': (3, 3), 'F4': (3, 4)
}

plt.figure(figsize=(10,6))
nx.draw(G, pos, with_labels=True, node_size=1000, node_color='skyblue', arrows=True)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red')
plt.title("🚛 최적 운송경로 네트워크")
plt.show()

✅ 선 두께나 색깔은 운송량에 따라 조절 가능.

---

5️⃣ 핵심 정리

단계	내용
✅ 데이터 확인	공급/수요 확인 & 정리
✅ 최적 경로 계산	linear_sum_assignment 사용
✅ 네트워크 시각화	NetworkX + Matplotlib