Transshipment 문제는 물류 최적화 문제 중 하나로, 공급지에서 수요지로 물품을 직접 운송하는 것이 아니라,
중간 경유지(Transshipment point)를 통해 물품을 전달하는 문제를 다룹니다.
즉, 물품이 한 번에 최종 목적지로 가는 것이 아니라, 경유지를 거쳐 최종 목적지에 도착하는 구조입니다.
구성
Transshipment 문제는 크게 세 가지 요소로 구성됩니다.
1. 공급지(Supply nodes): 물품을 제공하는 출발지입니다. 예를 들어 공장이나 창고가 될 수 있습니다.
2. 수요지(Demand nodes): 물품을 필요로 하는 목적지입니다. 매장이나 고객지일 수 있습니다.
3. 경유지(Transshipment nodes): 물품이 중간에 머무르거나 분배되는 장소입니다. 이 경유지에서는 물품이 도착한 후 다른 목적지로 다시 이동할 수 있습니다.
Transshipment 문제의 목표는 물품을 공급지에서 수요지로 이동시키는 총 운송 비용을 최소화하는 것입니다.
다만, 물품이 경유지를 거쳐서 이동한다는 것이 Transportation 문제와 다른 부분입니다.
수리적 모델
Transshipment 문제는 선형 계획법(Linear Programming)으로 모델링할 수 있습니다.
이를 위해 다음과 같은 변수와 제약 조건을 정의합니다.
설명을 위해서 아래와 같은 Transshipment 문제가 있다고 가정해 보겠습니다.
목적함수
목적은 운송비용을 최소화 하는 것입니다.
여기에서:
제약식
각 공급지에서 경유지로 운송되는 물품의 총량은 그 공급지의 최대 공급량을 초과할 수 없습니다.
각 수요지로 경유지에서 운송되는 물품의 총량은 해당 수요지의 요구량과 정확히 일치해야 합니다. (Balanced)
각 경유지로 들어온 물품의 양은 그 경유지에서 나가는 물품의 양과 동일해야 합니다.
즉, 경유지는 물품을 보관하는 것이 아니라, 들어온 물품을 다른 경로로 내보내는 역할을 합니다.
전체소스
from ortools.linear_solver import pywraplp
def create_data_model():
"""Stores the data for the problem."""
data = {}
# Supply at each source
data['supply'] = [300, 300]
# Demand at each destination
data['demand'] = [200, 200, 200]
# Transshipment nodes capacities
data['transshipment'] = [300, 300]
# Transportation costs between each node (source, transshipment, and destination)
data['costs'] = [
# From sources to transshipment nodes
[8, 6], # Source 1 to transshipment 1 and 2
[7, 5], # Source 2 to transshipment 1 and 2
# From transshipment nodes to destinations
[4, 2, 7], # Transshipment 1 to destinations 1, 2, 3
[3, 8, 6], # Transshipment 2 to destinations 1, 2, 3
]
# Number of nodes
data['num_sources'] = len(data['supply'])
data['num_destinations'] = len(data['demand'])
data['num_transshipment'] = len(data['transshipment'])
return data
def main():
# Create the data
data = create_data_model()
# Create the linear solver using the GLOP backend
solver = pywraplp.Solver.CreateSolver('GLOP')
if not solver:
return
# Create variables for each transportation route
x = {}
# From sources to transshipment nodes
for i in range(data['num_sources']):
for j in range(data['num_transshipment']):
x[(i, j)] = solver.NumVar(0, solver.infinity(), f'x_source{i}_trans{j}')
# From transshipment nodes to destinations
for i in range(data['num_transshipment']):
for j in range(data['num_destinations']):
x[(data['num_sources'] + i, j)] = solver.NumVar(0, solver.infinity(), f'x_trans{i}_dest{j}')
# Objective function: Minimize transportation costs
objective = solver.Objective()
# Costs from sources to transshipment nodes
for i in range(data['num_sources']):
for j in range(data['num_transshipment']):
objective.SetCoefficient(x[(i, j)], data['costs'][i][j])
# Costs from transshipment nodes to destinations
for i in range(data['num_transshipment']):
for j in range(data['num_destinations']):
objective.SetCoefficient(x[(data['num_sources'] + i, j)], data['costs'][data['num_sources'] + i][j])
objective.SetMinimization()
# Constraints: Supply from each source
for i in range(data['num_sources']):
solver.Add(sum(x[(i, j)] for j in range(data['num_transshipment'])) <= data['supply'][i])
# Constraints: Demand at each destination
for j in range(data['num_destinations']):
solver.Add(sum(x[(data['num_sources'] + i, j)] for i in range(data['num_transshipment'])) == data['demand'][j])
# Flow conservation at transshipment nodes
for i in range(data['num_transshipment']):
solver.Add(sum(x[(data['num_sources'] + i, j)] for j in range(data['num_destinations'])) ==
sum(x[(j, i)] for j in range(data['num_sources'])))
# Capacity constraints for transshipment nodes
for i in range(data['num_transshipment']):
# Ensure the total goods entering and leaving each transshipment node do not exceed its capacity
solver.Add(sum(x[(j, i)] for j in range(data['num_sources'])) <= data['transshipment'][i])
solver.Add(sum(x[(data['num_sources'] + i, j)] for j in range(data['num_destinations'])) <= data['transshipment'][i])
# Solve the problem
status = solver.Solve()
# Output results
if status == pywraplp.Solver.OPTIMAL:
print('Solution:')
print(f'Total transportation cost = {solver.Objective().Value()}\n')
for i in range(data['num_sources']):
for j in range(data['num_transshipment']):
print(f'Source {i} to Transshipment {j}: {x[(i, j)].solution_value()} units')
for i in range(data['num_transshipment']):
for j in range(data['num_destinations']):
print(f'Transshipment {i} to Destination {j}: {x[(data['num_sources'] + i, j)].solution_value()} units')
else:
print('The problem does not have an optimal solution.')
if __name__ == '__main__':
main()
Python
복사
위의 코드를 수행하면 아래와 같은 결과를 얻을 수 있습니다.
Solution:
Total transportation cost = 6200.0
Source 0 to Transshipment 0: 0.0 units
Source 0 to Transshipment 1: 300.0 units
Source 1 to Transshipment 0: 300.0 units
Source 1 to Transshipment 1: 0.0 units
Transshipment 0 to Destination 0: 100.0 units
Transshipment 0 to Destination 1: 200.0 units
Transshipment 0 to Destination 2: 0.0 units
Transshipment 1 to Destination 0: 100.0 units
Transshipment 1 to Destination 1: 0.0 units
Transshipment 1 to Destination 2: 200.0 units
JavaScript
복사
Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Google OR Tools
Reference:
