Transport Planning¶

A firm must transport machines from production plants A, B and C to warehouses X, Y and Z. Five machines are required in X, 4 in Y and 3 in Z, whereas 8 machines are available in A, 5 in B and 3 in C. The transport costs (in euros) between sites are provided in the table below.

Plant/Warehouse	X	Y	Z
A	50	60	30
B	60	40	20
C	40	70	30

a) Formulate an integer linear programming model that minimizes transport costs. This is a simple transportation problem, where the objective is to minimize the transportation costs. Let us note the transportation costs from plant \(i\) to warehouse \(j\) as \(c_{ij}\), our model is:

Indices

\(i\) Production plants, \(i \in [A,B,C]\)
\(j\) warehouses, \(j \in [X,Y,C]\)

Decision variables

\(x_{ij}\) (Integer) Number of machines to transport from production plant \(i\) to warehouse \(j\)

Objective function

\(z = \sum_i{\sum_j{c_{ij}*x_{ij}}}\)

Constraints Demand constraint

\(\sum_i{x_{ij}} \geq d_j \quad \forall j\)

b) Assume that the cost of transporting a machine from plant B increases by €10 for all the machines as of the third one; that is, the 4th, the 5th, etc. Reformulate the model in Section a) by considering this assumption. In this case, we need to define a new decision variable to factor in the extra costs incurred if we source more than three machines from plant B. Let us note these new decision variables as \(x*_{Bj}\) and represents the machines that are sourced from factory B from the third machine. Le us also note as \(c*_{Bj}\) the additional costs incurred from the third machine:

Plant/Warehouse	X	Y	Z
B	70	50	30

Now, our problem model becomes:

Decision variables

\(x_{ij}\) (Integer) Number of machines to transport from production plant \(i\) to warehouse \(j\)
\(x*_{Bj}\) (Integer) Number of machines to transport from production plant B to warehouse \(j\) from the third one
\(Y\) (Binary) Used to determine whether the number of machines sourced from B is greater than 3.

Objective function

\(z = \sum_i{\sum_j{c_{ij}*x_{ij}}} + \sum_j{c*_{Bj}*x*_{Bj}}\)

Constraints Demand constraint

\(\sum_i{x_{ij}} + x*_{Bj} \geq d_j \quad \forall j\)

Logical constraints \(\sum_j{x_{Bj}}\leq 3\)

\(\sum_j{x_{Bj}} - 3 + M*Y \geq 0\)

\(x*_{Bj} + M*Y \geq 0 \quad \forall j\)

\(x*_{Bj} \leq M*(1-Y) \quad \forall j\)

Where M is a very large number. To explain the introduction of the binary decision variables and the set of constraints, note that what we want to accomplish is the following logic:

“if \(\sum_j{x_{Bj}}=3\) then \(x*_{Bj} \geq 0\) else \(x*_{Bj} = 0\)”

This is equivalent to the following:

\(((\sum_j{x_{Bj}}=3) \wedge (x*_{Bj} \geq 0)) \vee ((\sum_j{x_{Bj}} \leq 3) \wedge (x*_{Bj} = 0))\)

where \(\wedge\) is the logical AND operator, and \(\vee\) is the logical or. That is, we want to ensure that \(x*_{Bj}\) is greater than zero when \(\sum_j{x_{Bj}}=3\) or that \(x*_{Bj} = 0\) when \(\sum_j{x_{Bj}} \leq 3\). We introduce the new binary decision variable \(Y\) to decide which of this two (mutually exclusive) conditions is true. Then, we multiply the binary decision variable by a very large number to render the constraints of the other condition irrelevant.

We introduce the constraints:

\(\sum_j{x_{Bj}} - 3 + M*Y \geq 0\)

\(x*_{Bj} + M*Y \geq 0 \quad \forall j\)

These constraints correspond to the left side of the \(\vee\) operator.

Similarly, to account for the right hand side, we introduce the constraints:

\(\sum_j{x_{Bj}} - 3 \leq M*(1-Y)\)

\(x*_{Bj} \leq M*(1-Y) \quad \forall j\)

Note that, if Y = 0, the logical constraints become:

\(\sum_j{x_{Bj}}\leq 3\)

\(\sum_j{x_{Bj}} - 3 \geq 0\) (and as per the previous constraint, the sum can only be equal to 3).

\(x*_{Bj} \geq 0 \quad \forall j\)

\(\sum_j{x_{Bj}} - 3 \leq M\) (irrelevant because M is a really large number)

\(x*_{Bj} \leq M \quad \forall j\) (irrelevant because M is a really large number)

Whereas if Y = 1, the logical constraints become:

\(\sum_j{x_{Bj}}\leq 3\)

\(\sum_j{x_{Bj}} - 3 + M \geq 0\) (irrelevant because M is a really large number)

\(x*_{Bj} + M \geq 0 \quad \forall j\) (irrelevant because M is a really large number)

\(\sum_j{x_{Bj}} - 3 \leq 0\) (this is the same as the previous constraint, so also irrelevant)

\(x*_{Bj} \leq 0 \quad \forall j\) (and since they cannot be negative, they must be equal to zero)

Since the constraint \(\sum_j{x_{Bj}} - 3 \leq M*(1-Y)\) is irrelevant when Y=0 and when Y=1, it is removed, and we get the set of constraints in the solution above.

Solution in Python¶

The following script solves the problem using Python. ### Requirements First, install the requirements:

[ ]:

!pip install pulp
!pip install pandas
!pip install IPython

[ ]:

import pulp
import pandas as pd
#And we will use numpy to perform array operations
import numpy as np
#We will use display and Markdown to format the output of code cells as Markdown
from IPython.display import display, Markdown

# Warehouses and dictionaries
plants = ('A', 'B', 'C')
warehouses = ('X', 'Y', 'Z')
#Transportation costs
transportation_costs = [[50, 60, 30], [60, 40, 20], [40, 70, 30]]

# Instantiate model
model = pulp.LpProblem("Transport Planning", pulp.LpMinimize)

# Demand
demand = [5, 4, 3]

# Capacities
capacities = [8, 5, 3]

variables = pulp.LpVariable.dicts("x",
                                  [(i, j) for i in plants for j in warehouses],
                                  lowBound=0,
                                  cat='Integer')

model += (
             pulp.lpSum([
                 transportation_costs[i][j] * variables[(plants[i], warehouses[j])]
                 for i in range(len(plants)) for j in range(len(warehouses))])
         ), "Transportation Cost"


# Capacity constraints
for i in range(len(plants)):
    model += pulp.lpSum([
        variables[(plants[i], warehouses[j])]
        for j in range(len(warehouses))]) <= capacities[i], plants[i]

# Demand
for j in range(len(warehouses)):
    model += pulp.lpSum([
        variables[(plants[i], warehouses[j])]
        for i in range(len(plants))]) >= demand[j], warehouses[j]

[9]:

import pulp
import pandas as pd
#And we will use numpy to perform array operations
import numpy as np
#We will use display and Markdown to format the output of code cells as Markdown
from IPython.display import display, Markdown

# Warehouses and dictionaries
plants = ('A', 'B', 'C')
warehouses = ('X', 'Y', 'Z')
#Transportation costs
transportation_costs = [[50, 60, 30], [60, 40, 20], [40, 70, 30]]

# Instantiate model
model = pulp.LpProblem("Transport Planning", pulp.LpMinimize)

# Demand
demand = [5, 4, 3]

# Capacities
capacities = [8, 5, 3]

variables = pulp.LpVariable.dicts("x",
                                  [(i, j) for i in plants for j in warehouses],
                                  lowBound=0,
                                  cat='Integer')

model += (
             pulp.lpSum([
                 transportation_costs[i][j] * variables[(plants[i], warehouses[j])]
                 for i in range(len(plants)) for j in range(len(warehouses))])
         ), "Transportation Cost"


# Capacity constraints
for i in range(len(plants)):
    model += pulp.lpSum([
        variables[(plants[i], warehouses[j])]
        for j in range(len(warehouses))]) <= capacities[i], plants[i]

# Demand
for j in range(len(warehouses)):
    model += pulp.lpSum([
        variables[(plants[i], warehouses[j])]
        for i in range(len(plants))]) >= demand[j], warehouses[j]

[10]:

# Solve our problem
model.solve()
print(pulp.LpStatus[model.status])

# Solution
max_z = pulp.value(model.objective)
print(max_z)

Optimal
460.0

[19]:

var_df = pd.DataFrame.from_dict(variables, orient="index",
                                columns = ["Variables"], dtype=object)

var_df["Solution"] = var_df["Variables"].apply(lambda item: item.varValue)
index = pd.MultiIndex.from_product([plants, warehouses], names=['Plants', 'Warehouses'])
var_df2 = pd.DataFrame(var_df["Solution"], index=index, columns = ["Solution"])
display(var_df2.unstack())

	Solution
Warehouses	X	Y	Z
Plants
A	2.0	0.0	2.0
B	0.0	4.0	1.0
C	3.0	0.0	0.0

[ ]: