# Matheuristics for the Design of a Multi-Step, Multi-Product Supply Chain with Multimodal Transport
## 4 MILP Model and Matheuristics
### Matheuristics  
The model described above can be reduced to the single-source capacitated facility location problem [23] and therefore it belongs to the class of NP-hard problems. Thus, a heuristic method is justified, especially to solve large instances.The matheuristics consist of the steps described in Algorithms 1-3.The algorithm described in Algorithm 1 is the general one. The problem is divided in two parts. In the first part the warehouses are openedfollowing one of two methods: simple or selective (with probability). Once the decision for the warehouses was fixed, an allocation sub-problem is solved using commercial optimization software. The sub-problem is described in Section 4.2.1. This sub-problem helps to determine the flows between the warehouses and the customers. Finally, a second sub-problem is solved considering the decisions fixed previously. This sub-problem is described in Section 4.2.2 as a reduced supply-chain network design (SCND) problem. Here, the remaining non-fixed variables are solved.  
The algorithm described in Algorithm 2 helps to open warehouses with a certain capacity using a simple, random selection. The process finishes when the aggregated capacity is greater than the total demand. This method is reported as \"Simple Heuristic\".  
The other method for warehouse selection is described in Algorithm 3. In this algorithm, an estimated cost is calculated for each warehouse. This cost is a combination of the fixed cost divided by the capacity of the facility, and an estimation of a potential transportation cost per unit. A probability is calculated such that the more expensive facility has a lower probability, and the cheapest facility has a higher probability. These probabilities are used with a random number to select warehouses with a certain capacity. The process finishes when the aggregated capacity is greater than the total demand. This selective method is reported as \"Heuristic with Probability\".  
The complexity of both matheuristics is dominated by the complexity of the solution of the Allocation Model which can be reduced to the Linear Assignment Problem, which can be solved in \(O(n^{3})\) time [24].  
```
1: Perform one of the two heuristics to decide the opening of warehouses \(w\).
2: Solve the allocation model with the parameter \(z_{uk}\) obtained in step 1.
3: Solve the reduced SCND model with the parameters \(z_{uk}\) and \(x_{uc}^{pt}\) obtained in the previous steps.
```  
**Algorithm 1** General algorithm.  
```
1: All the closed warehouses \(z_{w,q}=\{\{0,0,0\},\{0,0,0\},\ldots,\{0,0,0\}\}\)
2: Demanded storage capacity\(=\sum_{p\in P}\sum_{c\in C^{p}}\sum_{l\in T_{uc}}\mathit{SQUP}\mathit{ DEM}_{c}^{p}\ u_{uc}^{l}\)
3: Available capacity\(=0\)
4:\(\mathit{Open}_{w}=\{0,0,0,\ldots,0\}\)
5:repeat
6:repeat
7: Generate random \(ws\)
8: Generate random \(qs\)
9:while\(\mathit{Open}_{\mathit{us}}=1\)
10:\(\mathit{Open}_{\mathit{us}}=1\)
11:\(z_{\mathit{us},qs}=1\)
12: Available capacity \(=\) Available capacity \(+\)\(\overline{SQ}_{\mathit{us},qs}\)
13:while Available capacity \(<\) Demanded storage capacity
```  
**Algorithm 2** Simple Constructive Heuristics.