Transshipment 문제에서 중간 경유지를 Source와 Transshipment 사이에 추가한 확장된 모델을 살펴보겠습니다.
이 확장된 모델에서는 물류 네트워크가 다음과 같은 계층 구조를 가집니다.
공급지(Source) → 2. 중간 노드(Intermediate Node) → 3. 환적 노드(Transshipment Node) → 4. 목적지(Destination)
수리적 모델
Multi Layer Network 문제는 선형 계획법(Linear Programming)으로 모델링할 수 있습니다.
이를 위해 다음과 같은 변수와 제약 조건을 정의합니다.
설명을 위해서 아래와 같은 Multi Layer Network문제가 있다고 가정해 보겠습니다.
목적함수
목적은 운송비용을 최소화 하는 것입니다.
여기에서:
제약식
각 원천에서 나가는 물량은 해당 원천의 공급량을 초과할 수 없습니다.
중간 노드로 들어오는 물량은 반드시 환적 노드로 나가야 합니다. 즉, 중간 노드에서 들어온 물량과 나가는 물량은 같아야 합니다.
환적 노드로 들어오는 물량은 반드시 목적지로 나가야 합니다. 즉, 환적 노드에서 들어온 물량과 나가는 물량은 같아야 합니다.
각 목적지에서 들어오는 물량은 해당 목적지의 수요와 같아야 합니다.
중간 노드와 환적 노드를 통과하는 물량은 해당 노드의 용량을 초과할 수 없습니다.
전체소스
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]
# Intermediate nodes capacities
data['intermediate'] = [300, 300]
# Transshipment nodes capacities
data['transshipment'] = [300, 300]
# Transportation costs between each node (source, intermediate, transshipment, and destination)
data['costs'] = {
# From sources to intermediate nodes
'source_to_intermediate': [
[8, 6], # Source 1 to Intermediate 1 and 2
[7, 5], # Source 2 to Intermediate 1 and 2
],
# From intermediate nodes to transshipment nodes
'intermediate_to_transshipment': [
[3, 2], # Intermediate 1 to Transshipment 1 and 2
[4, 6], # Intermediate 2 to Transshipment 1 and 2
],
# From transshipment nodes to destinations
'transshipment_to_destination': [
[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_intermediate'] = len(data['intermediate'])
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 intermediate nodes
for i in range(data['num_sources']):
for j in range(data['num_intermediate']):
x[(i, j)] = solver.NumVar(0, solver.infinity(), f'x_source{i}_intermediate{j}')
# From intermediate nodes to transshipment nodes
for i in range(data['num_intermediate']):
for j in range(data['num_transshipment']):
x[(data['num_sources'] + i, j)] = solver.NumVar(0, solver.infinity(), f'x_intermediate{i}_transshipment{j}')
# From transshipment nodes to destinations
for i in range(data['num_transshipment']):
for j in range(data['num_destinations']):
x[(data['num_sources'] + data['num_intermediate'] + i, j)] = solver.NumVar(0, solver.infinity(),
f'x_transshipment{i}_destination{j}')
# Objective function: Minimize transportation costs
objective = solver.Objective()
# Costs from sources to intermediate nodes
for i in range(data['num_sources']):
for j in range(data['num_intermediate']):
objective.SetCoefficient(x[(i, j)], data['costs']['source_to_intermediate'][i][j])
# Costs from intermediate nodes to transshipment nodes
for i in range(data['num_intermediate']):
for j in range(data['num_transshipment']):
objective.SetCoefficient(x[(data['num_sources'] + i, j)],
data['costs']['intermediate_to_transshipment'][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'] + data['num_intermediate'] + i, j)],
data['costs']['transshipment_to_destination'][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_intermediate'])) <= data['supply'][i])
# Flow conservation at intermediate nodes
for i in range(data['num_intermediate']):
solver.Add(sum(x[(data['num_sources'] + i, j)] for j in range(data['num_transshipment'])) ==
sum(x[(j, i)] for j in range(data['num_sources'])))
# Flow conservation at transshipment nodes
for i in range(data['num_transshipment']):
solver.Add(
sum(x[(data['num_sources'] + data['num_intermediate'] + i, j)] for j in range(data['num_destinations'])) ==
sum(x[(data['num_sources'] + j, i)] for j in range(data['num_intermediate'])))
# Constraints: Demand at each destination
for j in range(data['num_destinations']):
solver.Add(
sum(x[(data['num_sources'] + data['num_intermediate'] + i, j)] for i in range(data['num_transshipment'])) ==
data['demand'][j])
# Capacity constraints for intermediate nodes
for i in range(data['num_intermediate']):
solver.Add(sum(x[(j, i)] for j in range(data['num_sources'])) <= data['intermediate'][i])
solver.Add(
sum(x[(data['num_sources'] + i, j)] for j in range(data['num_transshipment'])) <= data['intermediate'][i])
# Capacity constraints for transshipment nodes
for i in range(data['num_transshipment']):
solver.Add(
sum(x[(data['num_sources'] + data['num_intermediate'] + 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_intermediate']):
print(f'Source {i} to Intermediate {j}: {x[(i, j)].solution_value()} units')
for i in range(data['num_intermediate']):
for j in range(data['num_transshipment']):
print(
f'Intermediate {i} to Transshipment {j}: {x[(data['num_sources'] + 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'] + data['num_intermediate'] + i, j)].solution_value()} units')
else:
print('The problem does not have an optimal solution.')
if __name__ == '__main__':
main()
Python
복사
위의 코드를 수행하면 아래와 같은 결과를 얻을 수 있습니다.
Solution:
Total transportation cost = 8000.0
Source 0 to Intermediate 0: 300.0 units
Source 0 to Intermediate 1: 0.0 units
Source 1 to Intermediate 0: 0.0 units
Source 1 to Intermediate 1: 300.0 units
Intermediate 0 to Transshipment 0: 0.0 units
Intermediate 0 to Transshipment 1: 300.0 units
Intermediate 1 to Transshipment 0: 300.0 units
Intermediate 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:
