Arcadia deliveries

Try me

Open In ColabBinder

Problem definition

Arcadia Deliveries wants to determine the best location for their warehouses to supply the different retail regions of their best customer. There are 5 possible warehouse locations and 10 different retail regions. The following table shows the capacity and operation costs of the possible warehouse locations:

Data

warehouse 1

warehouse 2

warehouse 3

warehouse 4

warehouse 5

capacity

1000

2000

3000

4000

5000

Operation costs

50

60

70

80

90

The following table contains the demand at each region:

Region

Demand

Region 1

100

Region 2

200

Region 3

300

Region 4

400

Region 5

500

Region 6

600

Region 7

700

Region 8

800

Region 9

900

Region 10

1000

And the following cost contains the transportation costs from warehouses to regions:

Region

Warehouse 1

Warehouse 2

Warehouse 3

Warehouse 4

Warehouse 5

1

42

36

58

47

32

2

73

56

73

78

38

3

38

41

80

88

69

4

59

70

77

94

51

5

51

92

79

88

80

6

38

98

57

64

96

7

86

53

86

58

44

8

48

92

40

100

71

9

62

60

30

31

63

10

43

43

48

63

55

Find the optimal location for warehouses and determine which warehouses are going to deliver to every retail location, knowing that the customer requires that a region is supplied from only one source

Problem model

This is a transportation problem with a single-source facility constraint, where the sources are the sourcing warehouses and the destination the retail regions.

The objective is to minimize the transportation costs, taking into account transportation costs and the operation costs.

Indices Let us define the following indices:

  • \(i\): warehouse location (\(i \in [1, ..., 5]\))

  • \(j\): retail region (\(j \in [1, ..., 10]\))

Data Looking at the data, we can define the following vector containing the operation costs:

\(f = [f_1, f_2, ..., f_5] = [50, 60, 70, 80, 90]\)

and the following matrix containing the transportation costs from every warehouse to every retail region:

\(C = \begin{bmatrix} c_{11} & c_{12} & ... & c_{15}\\ c_{21} & c_{22} & ... & c_{25}\\ ... \\ c_{101} & c_{102} & ... & c_{105}\\ \end{bmatrix}\)

Or, using the values given in the table above:

\(C^T = \begin{bmatrix} 42 & 36 & 58 & 47 & 32\\ 73 & 56 & 73 & 78 & 38\\ 38 & 41 & 80 & 88 & 69\\ 59 & 70 & 77 & 94 & 51\\ 51 & 92 & 79 & 88 & 80\\ 38 & 98 & 57 & 64 & 96\\ 86 & 53 & 86 & 58 & 44\\ 48 & 92 & 40 & 100 & 71\\ 62 & 60 & 30 & 31 & 63\\ 43 & 43 & 48 & 63 & 55\\ \end{bmatrix}\)

Besides the costs, each warehouse has a limited sourcing capacity, which can be identified as a vector:

\(s = [s_1, s_2, ..., s_5] = [1000, 2000, 3000, 4000, 5000]\)

And the following vector contains the demand for every region:

\(d = [d_1, d_2, ..., d_{10}] = [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]\)

Let us define the following decision variables:

  • \(X_{ij}\): (Binary) determines if warehouse \(i\) delivers all demand to retail region \(j\) {1 if yes, 0 otherwise}

  • \(Y_{i}\): (Binary) determines if warehouse \(i\) delivers to any retail region {1 if yes, 0 otherwise}

Objective function The objective function is:

\(\min z = \sum_{i=1}^5{\sum_{j=1}^{10}{c_{ij}*d_j*X_{ij}}} + \sum_{i=1}^5{Y_i*f_i}\)

Constraints The constraints are:

Sourcing capacity:

\(\sum_{j=1}^m{d_j*X_{ij}} \leq s_i*Y_i \quad \forall i\)

These five constraints represent the limited capacity of the warehouses, we multiply the capacity with the corresponding \(Y_{i}\) variable to make sure the solution is logical and that the right-hand-side is zero if \(Y_{i}\) is zero.

Demand

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

Since we source all the demand from a single source, we only need to make sure that the demand is supplied from 1 location for every warehouse.

Implementation in Python

Requirements

Install the following requirements to run this cell:

[ ]:

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

Implementation

[6]:

# Import libraries
import pandas as pd
import pulp
import numpy as np
from IPython.display import display, Markdown

# Instantiate our problem class


model = pulp.LpProblem("Minimise_transportation_costs", pulp.LpMinimize)

# Define decision variables

# Construct our decision variable lists
warehouse = [1, 2, 3, 4, 5]
region = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


X = pulp.LpVariable.dicts("X_",
                                     ((i, j) for i in warehouse for j in region),
                                     lowBound=0,
                                     cat='Binary')

Y = pulp.LpVariable.dicts("Y_", (i for i in warehouse),
                                     lowBound=0,
                                     cat='Binary')

# Data
transportation_costs = np.array([[42, 73, 38, 59, 51, 38, 86, 48, 62, 43], [36, 56, 41, 70, 92, 98, 53, 92, 60, 43], [58, 73, 80, 77, 79, 57, 86, 40, 30, 48], [47, 78, 88, 94, 88, 64, 58, 100, 31, 63], [32, 38, 69, 51, 80, 96, 44, 71, 63, 55]])

operation_costs = np.array([50, 60, 70, 80, 90])

capacity = np.array([1000, 2000, 3000, 4000, 5000])

demand = np.array([100, 200, 300, 400, 500, 600, 700, 800, 900, 1000])

model += pulp.lpSum([demand[j]*transportation_costs[i,j]*X[(warehouse[i],region[j])] for i in range(len(warehouse)) for j in range(len(region))]) + pulp.lpSum([operation_costs[i]*Y[warehouse[i]] for i in range(len(warehouse))])

# Capacity constraints
for i in range(len(warehouse)):
  model += pulp.lpSum([demand[j]*X[(warehouse[i],region[j])] for j in range(len(region))]) <= capacity[i]*Y[warehouse[i]], "source_capacity_" + str(i)

# Demand constraints
for j in range(len(region)):
  model += pulp.lpSum([demand[j]*X[(warehouse[i],region[j])] for i in range(len(warehouse))]) >= demand[j], "demand_region_" + str(j)

model.solve()
print(pulp.LpStatus[model.status])

total_cost = pulp.value(model.objective)
display(Markdown("Total cost is **%0.2f €**"%total_cost))

#Let us now show the solution as pandas dataframes
x_df = pd.DataFrame(columns=warehouse)

display(Markdown("##Decision Variables##"))
display(Markdown("The following table displays the values of the decision variables $X_{ij}$. The orientation is the same as in the table that provided the data in the first place"))
for j in range(len(region)):
  row_name = region[j]
  row_values = {}
  for i in range(len(warehouse)):
    row_values[warehouse[i]]=int(X[(warehouse[i],region[j])].value())

  row_series = pd.Series(row_values, name=row_name)
  x_df = x_df.append(row_series)

display(x_df)

y_df = pd.DataFrame(columns=warehouse)
y_values = {}
for i in range(len(warehouse)):
  y_values[warehouse[i]]=int(Y[(warehouse[i])].value())

y_df = y_df.append(pd.Series(y_values, name="Y"))

display(Markdown("And the following table displays the values of the decision variables $Y_i$"))
display(y_df)
display(Markdown("Note that $Y_i$ is only 1 if the warehouse is used to deliver to any region"))

Optimal

Total cost is 235370.00 €

##Decision Variables##

The following table displays the values of the decision variables \(X_{ij}\). The orientation is the same as in the table that provided the data in the first place

1 2 3 4 5
1 0 0 0 0 1
2 0 0 0 0 1
3 1 0 0 0 0
4 0 0 0 0 1
5 1 0 0 0 0
6 0 0 1 0 0
7 0 0 0 0 1
8 0 0 1 0 0
9 0 0 1 0 0
10 0 1 0 0 0

And the following table displays the values of the decision variables \(Y_i\)

1 2 3 4 5
Y 1 1 1 0 1

Note that \(Y_i\) is only 1 if the warehouse is used to deliver to any region