In the competitive landscape of modern business, minimizing operational costs is essential for maintaining profitability. Transportation costs, in particular, play a significant role in the overall cost structure of companies that rely on distributing goods from manufacturing plants to various markets. Efficiently optimizing these transportation routes can lead to significant savings and improved service delivery.
In this blog post, we’ll explore how Python can be used to solve transportation problems, focusing on minimizing transportation costs when distributing goods from plants to markets. We’ll walk through the problem, define the necessary variables and constraints, and demonstrate how Python can be used to implement an optimal solution.
Understanding the Problem#
The transportation problem is a classic optimization challenge in operations research. It involves determining the most cost-effective way to transport goods from a set of suppliers (e.g., plants) to a set of consumers (e.g., markets). The objective is to minimize the total transportation cost while satisfying supply and demand constraints.
Input Parameters#
To model the problem, we need three key input parameters:
- Supply: The available quantity of goods at each plant.
- Demand: The required quantity of goods at each market.
- Transportation Costs: The cost of transporting one unit of goods from a particular plant to a particular market.
For those interested in the mathematical derivation, jump right in to the math.
Math Magician's Secret Scroll
The transportation problem can be expressed as a linear programming model. Let \(x_{ij}\) represent the number of units transported from plant \(i\) to market \(j\). The objective is to minimize the total cost:
graph TD
A[Plant i] -->|x_ij| B[Market j]
$$
\text{Minimize } Z= \sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}
$$Subject to:
- Supply constraints: \(\sum_{j=1}^nx_{ij}\leq s_i\) for all plants \(i \in \{1,..,m\}\)
- Demand constraints: \(\sum_{i=1}^mx_{ij}\leq d_i\) for all markets \(j \in \{1,..,n\}\)
- Non-negativity: \(x_{ij} \geq 0\)
Where:
- \(c_{ij}\) is the cost of transporting one unit from plant \(i\) to market \(j\)
- \(s_i\) is the supply at plant \(i\)
- \(d_j\) is the demand at market \(j\)
The solution to this linear programming problem yields the optimal transportation plan and minimum cost.
If you’d rather see the optimization in action, follow through.
import sympy as sp
from scipy.optimize import linprogWe have all the required packages loaded and ready. Let us now implement the input parameters in python.
# Step 1: Define the supply at each plant
supply = [20, 30, 25]
plant_names = ['Plant 1', 'Plant 2', 'Plant 3']
# Step 2: Define the demand at each market
demand = [15, 25, 35]
market_names = ['Market A', 'Market B', 'Market C']
# Step 3: Define the transportation costs from each plant to each market
transportation_costs = [
[8, 9, 14], # Costs from Plant 1 to Market A, B, C
[6, 12, 9], # Costs from Plant 2 to Market A, B, C
[10, 13, 16] # Costs from Plant 3 to Market A, B, C
]
print("Input parameters defined!")Decision Variables#
In optimization problems, decision variables represent the quantities we want to determine. In this case, the decision variables will represent the number of units to be transported from each plant to each market.
Note: The decision variables are the unknowns that we need to solve for. These variables are subject to constraints (supply and demand) and are used in the objective function to calculate the total transportation cost.
# Step 4: Create symbolic variables for the units transported
X = sp.Matrix([[sp.symbols(f'X_{i+1}_{j+1}') for j in range(len(market_names))] for i in range(len(plant_names))])
sp.pprint(X)Resource Constraints#
Resource constraints ensure that the supply from each plant is not exceeded and the demand at each market is met.
Supply Constraints#
Each plant can only supply a limited number of goods, so the sum of goods transported from a plant to all markets cannot exceed the plant’s supply.
# Step 5: Define the supply constraints symbolically
supply_constraints = []
for i in range(len(plant_names)):
constraint = sp.Eq(sum(X[i, j] for j in range(len(market_names))), supply[i])
supply_constraints.append(constraint)
print("Supply Constraints:")
for constraint in supply_constraints:
sp.pprint(constraint)Demand Constraints#
Each market requires a certain amount of goods, so the sum of goods received from all plants should meet the market’s demand.
# Step 6: Define the demand constraints symbolically
demand_constraints = []
for j in range(len(market_names)):
constraint = sp.Eq(sum(X[i, j] for i in range(len(plant_names))), demand[j])
demand_constraints.append(constraint)
print("Demand Constraints:")
for constraint in demand_constraints:
sp.pprint(constraint)Objective Function#
The objective is to minimize the total transportation cost, which is the sum of the cost for each route multiplied by the number of units transported.
# Step 7: Define the objective function symbolically (minimize transportation costs)
objective_function = sum(X[i, j] * transportation_costs[i][j] for i in range(len(plant_names)) for j in range(len(market_names)))
# Display the objective function and constraints
print("Objective Function:")
sp.pprint(objective_function)Solving the Problem with Python#
With the decision variables, constraints, and objective function defined, we can now solve the transportation problem using Python. Since the API wise intuitive pulp package does not work in browser yet, let us use Scipy’s solver. However, it requires us to convert the problem to a form that the API understands. Let us do that first.
# Step 8: Convert the problem to a form that can be solved by linprog
# Flatten the transportation costs and convert the objective function to a linear cost vector
c = [transportation_costs[i][j] for i in range(len(plant_names)) for j in range(len(market_names))]
# Create the equality constraint matrix for supply (Ax = b)
A_eq = []
b_eq = supply + demand
# Supply constraints (each row ensures the sum of shipments from a plant equals the plant's supply)
for i in range(len(plant_names)):
row = [1 if k // len(market_names) == i else 0 for k in range(len(plant_names) * len(market_names))]
A_eq.append(row)
# Demand constraints (each row ensures the sum of shipments to a market equals the market's demand)
for j in range(len(market_names)):
row = [1 if k % len(market_names) == j else 0 for k in range(len(plant_names) * len(market_names))]
A_eq.append(row)
# Convert to the appropriate format for linprog
A_eq = sp.Matrix(A_eq).tolist()
b_eq = sp.Matrix(b_eq).tolist()
# Step 9: Define the bounds for decision variables (non-negative)
bounds = [(0, None) for _ in range(len(c))]
print("Ready for optimization!")Warning: The quantity transported from each plant to each market is always non-negative.
Now, we can go ahead and solve the cost minimization problem.
# Step 10: Solve the linear programming problem using scipy.optimize.linprog
result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')
# Extract and print the results
optimal_values = result.x.reshape((len(plant_names), len(market_names)))
print("Optimal Transportation Matrix:")
print(" " * 12, end="") # Print space for the column headers
for market in market_names:
print(f"{market:>10}", end="") # Print market names as column headers
print() # New line after column headers
for i, plant in enumerate(plant_names):
print(f"{plant:>10}", end="") # Print plant names as row headers
for j in range(len(market_names)):
print(f"{optimal_values[i, j]:10.2f}", end="") # Print the cost values
print() # New line after each row
print("Detailed Optimal Transportation Plan:")
for i in range(len(plant_names)):
for j in range(len(market_names)):
print(f"Units transported from {plant_names[i]} to {market_names[j]}: {optimal_values[i, j]:.2f}")
print(f"\nTotal Transportation Cost: ${result.fun:.2f}")Conclusion#
Optimizing transportation costs is crucial for businesses looking to improve their efficiency and bottom line. By formulating the transportation problem as a linear programming model and solving it with Python, companies can identify cost-effective strategies for distributing goods from plants to markets.
Python’s flexibility and powerful libraries, such as pulp, make it an excellent choice for tackling optimization problems. The code examples in this post provide a hands-on approach for solving real-world transportation challenges.