Minimum Cost Flow 문제는 플로우 네트워크를 통해 일정량의 플로우를 송신하는 가장 저렴한 방법을 찾는 최적화 문제입니다.
이 문제에서는 공급 노드와 수요 노드라는 특수한 형태의 노드를 정의해야 합니다.
공급 노드는 물량을 공급할 수 있는 노드를 의미하고, 수요 노드는 수요를 나타내는 노드입니다.
예를 들어, 공장(Plant)과 고객(Customer) 간의 물동량을 시뮬레이션한다고 했을 때,
공장은 공급 노드로, 고객은 수요 노드로 정의할 수 있습니다.
아래 그림에서 0번 노드에 표시된 15은 공급수량을 의미하며, 3번노드에 표시된 -15는 수요량를 나타냅니다.
노드와 노드를 이어주는 간선에는 Capacity와 Cost를 정의할 수 있습니다.
Solver 설정
solver = min_cost_flow.SimpleMinCostFlow()
Python
복사
OR Tools는 MIP Solver를 제공하여 MIP를 사용할 수 있지만,
Minimum Cost Flow 문제를 해결할 때는 OR Tools에서 제공하는 전용 라이브러리인 min_cost_flow를 사용하는 것이 더 적합한 선택입니다.
Network 설정
for i in range(len(start_nodes)):
solver.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i], capacities[i], costs[i])
Python
복사
Solver 실행
status = solver.solve()
Python
복사
전체 소스
from ortools.graph.python import min_cost_flow
def solve_minimum_cost_flow_4_nodes():
# Create the minimum cost flow solver
solver = min_cost_flow.SimpleMinCostFlow()
# Define the directed graph using an adjacency list
start_nodes = [0, 0, 1, 2]
end_nodes = [1, 2, 3, 3]
capacities = [10, 15, 20, 10]
costs = [5, 4, 3, 2]
# Supply/Demand for each node
supplies = [15, 0, 0, -15]
# Add the edges to the solver
for i in range(len(start_nodes)):
solver.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i], capacities[i], costs[i])
# Add the supplies/demands
for i in range(len(supplies)):
solver.set_node_supply(i, supplies[i])
# Solve the minimum cost flow problem
status = solver.solve()
if status == solver.OPTIMAL:
print('Minimum cost:', solver.optimal_cost())
print('\n Arc Flow / Capacity Cost')
for i in range(solver.num_arcs()):
if solver.flow(i) > 0:
cost = solver.flow(i) * solver.unit_cost(i)
print('%1s -> %1s %3s / %3s %3s' % (
solver.tail(i),
solver.head(i),
solver.flow(i),
solver.capacity(i),
cost))
else:
print('There was an issue with the min cost flow input.')
solve_minimum_cost_flow_4_nodes()
Python
복사
결과는 아래와 같습니다.
Minimum cost: 100
Arc Flow / Capacity Cost
0 -> 1 5 / 10 25
0 -> 2 10 / 15 40
1 -> 3 5 / 20 15
2 -> 3 10 / 10 20
Python
복사
Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Google OR Tools
Reference:
[1] Assignment as a Min cost Flow Problem by Google, https://developers.google.com/optimization/flow/mincostflow
