수송계획법(경유지를 포함한)

예전 포스팅에서 간단한 수송계획법을 다루어보았습니다.(https://direction-f.tistory.com/106) 이번 포스팅에서는 수송계획법을 확장하여 경유지를 포함한 수송계획법에 대해서 정리해보겠습니다.

일반 수송계획법에서는 공급지와 수송지가 있었다면 경유지를 포함한 문제는 경유지가 포함됩니다. 따라서 3가지의 수송망이 있습니다.

1. 공급지 - 제품을 공급하는 곳(공장)
2. 경유지 - 제품이 중간에 보관되는 곳(창고)
3. 수요지 - 공급지 또는 경유지로부터 제품을 공급받는곳(도시)

예시 문제로 2개의 공장(P1,P2) / 2개의 창고(W1,W2) / 3개의 도시(C1, C2, C3)가 있다고 해보겠습니다. 이때 발생하는 Cost matrix는 아래와 같습니다.

1) 공장 -> 창고(cost_pw)

	W1	W2
P1	2	3
P2	4	1

 

2) 창고 -> 도시(cost_wc)

	C1	C2	C3
W1	5	5	4
W2	3	6	3

 

3) 공장-> 도시(cost_pc)
(수요지는 경유지 뿐만아니라 공급지에서도 제품을 받을 수 있습니다.)

	C1	C2	C3
P1	10	8	12
P2	9	7	11

 

최적화 모형은 아래와 같습니다.

 

공급지 제약조건:

수요 제약조건:

창고 제약 조건: 각 창고로 들어오는 총 물량과 해당 창고에서 나가는 총 물량은 같다

 

이제 코드를 기반으로 해당문제를 해결해보겠습니다. 먼저 문제의 조건을 입력합니다.

from ortools.linear_solver import pywraplp
import pandas as pd
import numpy as np


## Problem Conditions
num_plant = 2
num_warehouse = 2
num_city = 3

# Costs
cost_pw = [[2, 3],  # P1->W1, P1->W2
           [4, 1]]  # P2->W1, P2->W2

cost_wc = [[5, 2, 4],  # W1->C1, W1->C2, W1->C3
           [3, 6, 3]]  # W2->C1, W2->C2, W2->C3

cost_pc = [[10, 8, 12], # P1->C1, P1->C2, P1->C3
           [9, 7, 11]]  # P2->C1, P2->C2, P2->C3

plant_supply_capa = [500, 600] # P1, P2 supplies
city_demand = [300, 450, 350]  # C1, C2, C3 demands

그 다음 우리가 답을 찾아야할 의사결정 변수를 입력합니다.

## Define Solver
solver = pywraplp.Solver.CreateSolver('GLOP')

## Define Decision Variable
x={}
for i in range(num_plant):
    for j in range(num_warehouse):
        x[i,j] = solver.NumVar(0, solver.infinity(), '')

y={}
for j in range(num_warehouse):
    for k in range(num_city):
        y[j,k] = solver.NumVar(0, solver.infinity(), '')

z={}
for i in range(num_plant):
    for k in range(num_city):
        z[i,k] = solver.NumVar(0, solver.infinity(), '')

 그 다음에는 공급지, 수요지, 창고 제약조건을 입력합니다. 

## Define Constratins

# 1. Plant Supply Constraints
for i in range(num_plant):
    constraint_expr = [x[i,j] for j in range(num_warehouse)] + [z[i,k] for k in range(num_city)]
    solver.Add(solver.Sum(constraint_expr) == plant_supply_capa[i], f'PlantSupply_{i}')
 
# 2. City Demand Constraints
for k in range(num_city):
    constraint_expr = [y[j,k] for j in range(num_warehouse)] + [z[i,k] for i in range(num_plant)]
    solver.Add(solver.Sum(constraint_expr) == city_demand[k], f'CityDemand_{k}')

# 3. Warehouse Flow Conservation Constraints
for j in range(num_warehouse):
    inflow = [x[i,j] for i in range(num_plant)]
    outflow = [y[j,k] for k in range(num_city)]
    solver.Add(solver.Sum(inflow) == solver.Sum(outflow), f'WarehouseFlow_{j}')

마지막으로 목적함수를 입력합니다. Dictionary를 활용하여 의사결정변수들과 Cost matrix를 다룰 수 있기 때문에 직관적입니다.

## Define Objective function
objective_terms = []
# Cost from plant to warehouse
for i in range(num_plant):
    for j in range(num_warehouse):
        objective_terms.append(cost_pw[i][j] * x[i,j])

# Cost from warehouse to city
for j in range(num_warehouse):
    for k in range(num_city):
        objective_terms.append(cost_wc[j][k] * y[j,k])

# Cost from plant to city (direct)
for i in range(num_plant):
    for k in range(num_city):
        objective_terms.append(cost_pc[i][k] * z[i,k])

solver.Minimize(solver.Sum(objective_terms))

마지막으로 앞에 정의한 문제를 해결하는 코드입니다.

## Invoke the solver
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print(f'Optimal solution found.')
    print(f'Total Transportation Cost = {solver.Objective().Value():.2f}\n')
    print("Flows from Plant to Warehouse (x_ij):")
    for i in range(num_plant):
        for j in range(num_warehouse):
            if x[i,j].solution_value() > 0.001: # Print only non-zero flows
                print(f'  Plant {i+1} to Warehouse {j+1}: {x[i,j].solution_value():.2f} units')

    print("\nFlows from Warehouse to City (y_jk):")
    for j in range(num_warehouse):
        for k in range(num_city):
            if y[j,k].solution_value() > 0.001:
                print(f'  Warehouse {j+1} to City {k+1}: {y[j,k].solution_value():.2f} units')

    print("\nFlows directly from Plant to City (z_ik):")
    for i in range(num_plant):
        for k in range(num_city):
            if z[i,k].solution_value() > 0.001:
                print(f'  Plant {i+1} to City {k+1}: {z[i,k].solution_value():.2f} units')
    
    print(f'\nSolver wall time: {solver.wall_time()} ms')
    print(f'Solver iterations: {solver.iterations()}')

else:
    print('The problem does not have an optimal solution.')
    
    
    
    """
    Optimal solution found.
Total Transportation Cost = 4500.00

Flows from Plant to Warehouse (x_ij):
  Plant 1 to Warehouse 1: 450.00 units
  Plant 1 to Warehouse 2: 50.00 units
  Plant 2 to Warehouse 2: 600.00 units

Flows from Warehouse to City (y_jk):
  Warehouse 1 to City 2: 450.00 units
  Warehouse 2 to City 1: 300.00 units
  Warehouse 2 to City 3: 350.00 units

Flows directly from Plant to City (z_ik):

"""

결과적으로 공급지에서 수요지로 가는 물량은 없었습니다. 당연하게도 공급지->창고 + 창고->수요지 Cost가 더 낮기 때문입니다.그래서 cost_pc를 낮추면 공급지에서 바로 수요지로 가는 물량이 생길 것입니다.