Problem definition¶

4 Trucks are available to deliver gas to 5 gas stations. Each truck has a different capacity and if the company decides to use it to supply to any gas stations, the cost can be modeled by a constant operating cost. The capacity and daily operating costs of each truck are shown in the table below.

	Capacity (Liters)	Daily Operating Costs
Truck 1	4000	45
Truck 2	5000	50
Truck 3	6000	55
Truck 4	11000	60

Each gas station can be supplied only by one truck, but a track may deliver to more than one gas station. The daily demands of each gas station are shown in the table below.

	Daily Demand (liters)
Station 1	1000
Station 2	2000
Station 3	3000
Station 4	5000
Station 5	8000

Formulate an Integer Program Problem that can be used to minimise the distribution costs of the logistics operations needed to satisfy the demand of the five stations.

Model definition¶

Indexes¶

i: Gas stations
j: Trucks

Decision Variables¶

Yj (Binary): Truck j is used
Xij (Binary): Truck j delivers to gas station i

Objective Function¶

Minimise cost:

\(\min z = \sum{Y_j·Co_j}\)

Where \(Co_j\) is the fixed operational cost of using truck j.

Constraints¶

Single source delivery constraint

First, we need to consider the single source constraint, to make sure that only 1 truck delivers to a gas station:

\(\sum_{j}{X_{ij}}=1 \quad \forall i\)

Demand constraint

However, we also need to into account the demand, to make sure that we satisfy the daily demand in each gas station:

\(\sum_{j}{d_i*X_{ij}}=d_i \quad \forall i\)

Note that these two constraints (single source delivery constraint and demand constraint) are equivalent. We can just use the former in our model.

Capacity constraint

We also need to take into account the capacity constraint to make sure that the amount delivered from any truck is lower than its capacity:

\(\sum_{i}{d_i*X_{ij}} \leq c_j \quad \forall j\)

Logical constraint

We need to introduce a logical constraint as well, to make sure that the binary decision variables are consistent with each other. Basically, we need to ensure that we only use one truck (i.e. \(Y_j=1\)) when it delivers to any gas station (i.e. any \(X_{ij}\) = 1 for the same j):

\(X_{ij} \leq Y_j \quad \forall i, \forall j\)

Another way to express the logical constraint is:

\(\sum_{i}{X_ij} \leq M*Y_j \quad \forall i, \forall j\)

Where M is a very large number. In this form, basically what we say is that if a truck is not used (i.e. \(Y_j=0\)), then the sum of the gas stations it delivers to must be 0. Otherwise, if it is used (i.e. \(Y_j=0\)), the sum has to be lower than a very large number M.

Note that, we can also merge this logical constraint with the capacity constraint to yield:

\(\sum_{i}{d_i*X_ij} \leq c_jY_j \quad \forall j\)

In this form, the right hand side of the logical constraint is modified to take into account the quantity that each truck delivers when it is used, and the right hand side is modified to take into account the maximum capacity of the truck, when it is used.

With this, our model can be written as:

\(\min z = \sum{Y_j·Co_j}\)

\(s.t.\)

\(\sum_{j}{d_i*X_{ij}}=d_i \quad \forall i\)

\(\sum_{i}{d_i*X_ij} \leq c_jY_j \quad \forall j\)

Solution in Python¶

Requirements¶

Run the following script to install the required packages

[ ]:

!pip install pulp
!pip install pandas

[4]:

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

trucks = [1, 2, 3, 4]
stations = [1, 2, 3, 4, 5]

capacities = [4000, 5000, 6000, 11000]

costs = [45, 50, 55, 60]

demands = [1000, 2000, 3000, 5000, 8000]

# Instantiate model
model = pulp.LpProblem("Truck Deliveries", pulp.LpMinimize)

x_vars = pulp.LpVariable.dicts("X",
                                  [(i, j) for i in stations for j in trucks],
                                  lowBound=0,
                                  cat='Binary')

y_vars = pulp.LpVariable.dicts("Y",
                                  [j for j in trucks],
                                  lowBound=0,
                                  cat='Binary')

model += (
             pulp.lpSum([
                 costs[j] * y_vars[trucks[j]]
                 for j in range(len(trucks))])
         ), "Fixed operating costs"

# Demand
for i in range(len(stations)):
    model += pulp.lpSum([
        demands[i]*x_vars[(stations[i], trucks[j])]
        for j in range(len(trucks))]) == demands[i], "station_" + str(stations[i])

# Capacity constraints
for j in range(len(trucks)):
    model += pulp.lpSum([
        demands[i]*x_vars[(stations[i], trucks[j])]
        for i in range(len(stations))]) <= capacities[j]*y_vars[trucks[j]], "truck_" + str(trucks[j])

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

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

Optimal
155.0

[7]:

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

var_Y_df["Solution"] = var_Y_df["Variables"].apply(lambda item: item.varValue)
display(var_Y_df)

var_X_df = pd.DataFrame.from_dict(x_vars, orient="index",
                                 columns = ["Variables"], dtype=object)
var_X_df["Solution"] = var_X_df["Variables"].apply(lambda item: item.varValue)
index = pd.MultiIndex.from_product([stations, trucks], names=['Stations', 'Trucks'])
var_df2 = pd.DataFrame(var_X_df["Solution"], index=index, columns = ["Solution"])
display(var_df2.unstack())

	Variables	Solution
1	Y_1	1.0
2	Y_2	1.0
3	Y_3	0.0
4	Y_4	1.0

	Solution
Trucks	1	2	3	4
Stations
1	1.0	0.0	0.0	0.0
2	0.0	0.0	0.0	1.0
3	1.0	0.0	0.0	0.0
4	0.0	1.0	0.0	0.0
5	0.0	0.0	0.0	1.0

[ ]: