Matheuristics for the Design of a Multi-Step, Multi-Product Supply Chain with Multimodal Transport

Abstract

Supply-chain network design is a complex task because there are many decisions involved, and presently, global networks involve many actors and variables, for example, in the automotive, pharmaceutical, and electronics industries. This research addresses a supply-chain network design problem with four levels: suppliers, factories, warehouses, and customers. The problem considered decides on the number, locations, and capacities of factories and warehouses and the transportation between levels in the supply chain. The problem is modeled as a mixed-integer linear program. The main contribution of this work is the proposal of two matheuristic algorithms to solve the problem. Matheuristics are algorithms that combine exact methods and heuristics, attracting interest in the literature because of their fast execution and high-quality solutions. The matheuristics proposed to select the warehouses and their capacities following heuristic rules. Once the warehouses and their capacities are fixed, the algorithms solve reduced models using commercial optimization software. Medium and large instances were generated based on a procedure described in the literature. A comparison is made between the algorithms and the results obtained, solving the model with a time limit. The algorithms proposed are successful in obtaining better results for the largest instances in shorter execution times.

1. Introduction

An optimal supply chain is a fundamental part of any company’s success; a good design and administration represent a competitive advantage or even a requirement for market participation. Supply chains represent a large part of a company’s assets. Additionally, costs or savings are dependent on their design. Among the advantages obtained by a good design of the supply chain are reduced purchase costs, reduced production costs, increased company profits, reduced investment in fixed costs, and increased cash flow, among others.

In the end, the main objective of a supply chain is to provide an efficient way to supply the products to the client at the lowest possible cost (Council of Supply-Chain Management Professionals (CSCMP), 2019). However, within a supply chain, a large number of costs are incurred. Additionally, within large companies, supply chains are becoming increasingly complex. Knowing which is the best option among all the possible combinations becomes quite a complex task. The global production and distribution networks involve many actors and variables, exploding the combinatorial nature of the decisions involved, especially when more characteristics are considered, such as location, transportation, inventory, product architecture, or sustainability considerations. These networks exist in industries such as pharmaceutical, automotive, and electronic products, with suppliers, plants, and customers in different continents.

One way to address the decision-making problem in the design of supply chains has been to propose optimization models based on mathematical programming. As long as computers increase power, it has been possible to solve more complex models involving more elements. However, the mixed-integer linear programming models that have been widely used in the optimization of the supply chain are mostly NP-hard [1], making it impossible to obtain optimal solutions in reasonable times for instances of size similar to those found in real problems. Fortunately, the ability of computers to calculate results for different scenarios brought the opportunity to use heuristics and randomness to help in the construction of solutions for NP-hard combinatorial problems. The first results showed that although these solutions had variable and worse quality than those obtained with exact methods, the computational effort required shorter times. With the goal of improving the quality of these solutions, the research on metaheuristic algorithms was born. Many advances were achieved with algorithms such as simulated annealing, tabu search, ant colony optimization, genetic algorithms, and others. Recently, new algorithms are being proposed, combining heuristics and exact mathematical programming methods, known as matheuristics. The research in this field is new, and the goal is to combine the speed of processing using heuristic components with the quality obtained with exact methods. Thus, the main contribution of the work presented in this paper is to advance in the research of matheuritics, proposing two algorithms to solve a complex problem efficiently for supply-chain network design with good quality solutions in a reasonable time.

In this work, a supply-chain network design (SCND) problem will be presented, where a literature review of both the problem and the methods of solution are shown first; then, the problem is described in detail. A mixed-integer linear programming model is presented, and the matheuristics are used to solve the same problem. The instances presented range from 100 to 200 clients, and the results of the mixed-integer linear programming model will be analyzed and compared with those of the matheuristic algorithms proposed. Finally, the conclusions will be presented in the last section.

2. Literature Review

This section will describe some of the literature, first related to the problem of supply-chain network design, and later, related to matheuristics, commenting about the gap covered by the research presented in this paper.

Pirkul and Jayaraman [2] created a model called PLANWAR, which focused on optimizing the supply chain through a heuristic to decide on the opening of plants and warehouses and the flow between them. However, the model does not handle different levels of capacity between facilities nor multimodal transportation.

Wu et al. [3] solved the supply-chain planning problem where the same product can be produced in multiple facilities, but their work focuses more on analyzing different algorithms and the complexity of each one of them. In their problem of supply-chain design, Eskigun et al. [4] consider delivery times and transportation modes, but their work focuses mainly on outbound logistics and is not multi-tier.

Sadjady and Davoudpour [5] solved a multi-product supply-chain problem using a mixed-integer linear programming model in which the opening of facilities is decided, as well as the level of capacity and the mode of transport of flows between levels of the supply-chain. However, the work takes into account only finished products. Olivares-Benitez et al. [6] focus on optimizing the transportation of a two-tier supply chain, calculating the flow and time between facilities using bi-objective optimization. The problem addressed in this work is for a single product. Rahmaniani and Ghaderi [7] developed a mixed-integer linear programming model and a heuristic based on the evolutionary algorithm of the firefly, where transport and construction costs are taken into account, but their solution method focuses on problems in telecommunications or power distribution companies.

Bertazzi et al. [8] developed min-max methods and a heuristic to solve the multi-tier inventory problem taking into account purchasing, manufacturing, and transportation costs, but they do not address the issue of opening of facilities. Additionally, they do not take into account the bill of materials.

Many more recent models address the problem of supply-chain network design with different considerations, for example, ref. [9] describe a problem with environmental and financial considerations, or [10] analyze a model considering inventory decisions besides the classic decisions for location and transportation. However, the research in the literature is far from a general model for supply-chain network design that includes all the situations, variables, and decisions. Our purpose was to analyze a problem with a high level of complexity to be a challenge for new methods of solution. In particular, very few models consider the product architecture represented in the bill of materials. One of the reasons is that introducing this element creates an explosion in the number of variables and interactions, making it very hard to solve even small instances. As can be observed in the literature presented, the most used solution methods are based on metaheuristics because of the computational complexity of the models used. We are proposing new methods of solution into the field of matheuristics, which rarely has been used in SCND.

The term matheuristic is relatively new; the term began to be used between 2008 and 2009. Maniezzo et al. [11] talk about the hybridization that can exist between mathematical programming and metaheuristics. Fischetti and Fischetti [12] explain that matheuristics exploit heuristics and metaheuristics to improve and facilitate the mixed-integer programming (MIP) model. They show three applications: optimization of layout, packaging, and routing. Moreover, there is a rising interest in these hybrid methods, demonstrated by a growing literature and specialized tutorials in operations research [13]. Matheuristics have been applied to different decision-making problems, for example in routing [14], production planning [15], lot sizing [16], and risk management [17], among others. However, we found in the literature few applications of matheuristics to supply-chain network design.

Boschetti et al. [18] solve a Single-Source Capacitated Facility Location problem (SCFLP) using different matheuristics. Raa et al. [19] use a matheuristic to solve their aggregate production-distribution problem, but the work is focused on mould-sharing between factories. Tautenhain et al. [20] use the combination of a heuristic called MathFix and a matheuristic called AugMathFix to solve a bi-objective model for sustainable supply-chain design. However, the model has only two tiers: suppliers-plant and plant-clients. Cantú et al. [21] propose a matheuristic for the design of sustainable hydrogen supply chains using a multi-objective perspective, but the model is focused on a single product and transportation mode. Souto et al. [22] propose a matheuristic algorithm to solve the problem of supply-chain network design only with two levels, a single transportation mode, and a single product.

Table 1. Description the features for the literature presented.

	Facilities Opening	Transportation Cost	Multi-Mode Transportation	Multi-Product	BOM	4-Levels	Facility Capacity Levels	Matheuristics
[2]	X	X
[3]	X	X		X
[4]		X	X
[5]	X	X	X	X			X
[6]	X	X	X
[7]	X	X	X			X
[18]	X	X						X
[19]		X						X
[20]	X	X	X				X	X
[21]	X	X	X			X	X	X
[22]	X	X						X
Our proposal, based on [23]	X	X	X	X	X	X	X	X

describe the features for the literature presented in this section. It can be noted that the problem we are solving in this work has a higher level of complexity than other problems solved in the literature using matheuristics. The elements that add this complexity beyond the classic decisions on location and transportation are: a hierarchical product architecture as described by a bill of materials, different capacities in the facilities, and different available transportation modes. The complexity of the problem represents a challenge for any solution method, and is a good choice to demonstrate the efficiency of the matheuristic algorithms proposed.

3. Problem Description

This paper addresses the problem of designing a four-tier multi-product supply-chain network (SCND): suppliers, factories, warehouses, and customers (Figure 1). The number and locations of plants and warehouses must be chosen from a set of potential plants and warehouses, respectively, and the capacity level of each factory and each warehouse must be chosen from a set of predetermined capacity levels for each location. Each location with each of its capacity levels has a fixed opening cost.

Each of the materials can be supplied by a set of suppliers that have this material. Each material has a different purchase price for each supplier. Materials are shipped to factories, where they are converted into finished products. Each finished product has its bill of materials (BOM), which states what materials are needed for each finished product and how many units, so all the materials needed to produce a finished product will have to be taken to the factory where it is produced. Figure 2, shows the representation of the BOM; it exemplifies that to produce product $p_1$, 4 units of material $r_1$ and 3 units of material $r_2$ are needed. The generic description is for any product p the necessary units of material r are given by the parameter $A^{rp}$.

Each product can be manufactured in a pre-established set of factories. Each of the products has a manufacturing cost in each plant. Once the products are manufactured, they can be taken to a set of pre-established warehouses. Finished products must be supplied to each customer in a single delivery; that is, products cannot be shipped to the customer from two different warehouses.

All materials and finished products can be transported by different transport methods for each destination-origin pair, which can be the following: supplier-factory, factory-warehouse, warehouse-customer. Each product or material has a transport cost for each means of transport for each possible pair. Each means of transportation for each origin-destination pair has a minimum quantity to be transported and a maximum transport capacity.

Each supplier has a maximum capacity to supply each material. Each product occupies a different manufacturing or storage capacity. Each factory has a maximum production capacity for each product, a total maximum production capacity, and a minimum production capacity so that the factory can be opened for each of its capacity levels. Each warehouse has a maximum storage capacity and a minimum of storage to be opened.

The objective of the supply-chain design is to minimize the sum of the fixed cost by opening factories and warehouses, the total purchasing costs, the total manufacturing costs, and the total transportation costs.

This supply-chain design can be applied to global networks of manufacturing and distribution in industries such as pharmaceutics, automotive, and electronics. For example, in the production of drugs, many ingredients can be blended, purchased from suppliers in different countries, and distributed to customers in other continents using alternative transportation modes. A potential example is to have suppliers in Asia, shipping materials to plants in Europe to manufacture products, to be transported to markets in the US, Canada, and Brazil. Similar cases can be devised to manufacture vehicles, tablets, cell phones, computers, or vaccines.

Some assumptions of the model that may represent limitations to its applicability are:

• It is a single-period problem that usually is applied to long-term planning.
• The model is deterministic and is not considering variability, although being fast to solve is useful for what-if analysis.
• The model is not incorporating other operational and strategic elements such as routing, sustainability, inventory, service level, etc.

4. MILP Model and Matheuristics

4.1. Mixed-Integer Linear Programming Model (MILP)

Following is the notation used for the MILP, based on the model of [23].

4.1.1. Decision Variables

Binary Variables

$$z_{fq}=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{it}\mathrm{is}\mathrm{decided}\mathrm{to}\mathrm{open}\mathrm{a}\mathrm{factory}w\mathrm{with}\mathrm{a}\mathrm{capacity}\mathrm{level}q,\left(f\in F;q\in Q\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\end{array}\right.$$

$$z_{wq}=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{it}\mathrm{is}\mathrm{decided}\mathrm{to}\mathrm{open}\mathrm{a}\mathrm{warehouse}w\mathrm{with}\mathrm{a}\mathrm{capacity}\mathrm{level}q,\left(w\in W;q\in Q\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\end{array}\right.$$

$$v_{sf}^r=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{material}r\mathrm{is}\mathrm{supplied}\mathrm{to}\mathrm{factory}f\mathrm{by}\mathrm{a}\mathrm{supplier}s,\left(s\in S;f\in F;r\in R\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\end{array}\right.$$

$$u_{od}^t=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{origin}o\mathrm{destination}d\mathrm{by}\mathrm{mode}\mathrm{of}\mathrm{transport}t,\\ & \left((o,d)\in \{(S,F)\cup (F,W)\cup (W,C)\};t\in T\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\end{array}\right.$$

Real Variables

$x_{sf}^{rt}$: Amount of material r that is supplied by supplier s to factory f by mode of transport t,

$\left(s\in S;f\in F;r\in R;t\in T\right)$

$x_{fw}^{pt}$: Amount of product p that is sent from factory f to warehouse w by mode of transport t,

$\left(f\in F;w\in W;p\in P;t\in T\right)$

4.1.2. Objective Function

The objective function (1) is to minimize the sum of all the costs that we are taking into account in the model. The first term adds the fixed costs of opening a factory, the second, the fixed costs of opening a warehouse, the third the purchase and transportation costs from the supplier to the factories of the materials, the fourth, the cost of manufacturing and transportation from the factories to the warehouses and the fifth the transportation from the warehouses to the customers.

$$\begin{array}{c}\hfill Min\sum _{f\in F}^{}\sum _{q\in Q}^{}F{C}_{fq}{z}_{fq}+\sum _{w\in W}^{}\sum _{q\in Q}^{}F{C}_{wq}{z}_{wq}+\sum _{r\in R}^{}\sum _{s\in S^r}^{}\sum _{f\in F}^{}\sum _{t\in T_{sf}}^{}(P{C}_s^r+T{C}_{sf}^{rt})x_{sf}^{rt}+\\ \hfill \sum _{p\in P}^{}\sum _{f\in F^p}^{}\sum _{w\in W^p}^{}\sum _{t\in T_{fw}}^{}(M{C}_f^p+T{C}_{fw}^{pt})x_{fw}^{pt}+\\ \hfill \sum _{p\in P}^{}\sum _{c\in C^p}^{}\sum _{w\in W^p}^{}\sum _{t\in T_{wc}}^{}DE{M}_c^{p}T{C}_{wc}^{pt}{u}_{wc}^t\end{array}$$

(1)

4.1.3. Constraints

Supplier constraints

Constraint (2) limits the order quantity to a material supplier’s maximum capacity, constraint (3) prevents a factory ordering a specific material from more than one supplier and constraint (4) ensures that not only can the material be transported from a supplier to a factory if we select that supplier.

$$\begin{array}{cc}\hfill \sum _{f\in F}^{}\sum _{t\in T_{sf}}^{}{x}_{sf}^{rt}\le SQ{R}_s^r& \mathbf{r}\in \mathbf{R},\mathbf{s}\in {\mathbf{S}}^{\mathbf{r}}\end{array}$$

(2)

$$\begin{array}{cc}\hfill \sum _{s\in S^r}^{}{v}_{sf}^r\le 1& \mathbf{r}\in \mathbf{R},\mathbf{f}\in \mathbf{F}\end{array}$$

(3)

$$\begin{array}{cc}\hfill \sum _{t\in T_{sf}}^{}{x}_{sf}^{rt}\le SQ{R}_s^r{v}_{sf}^r& \mathbf{r}\in \mathbf{R},\mathbf{s}\in {\mathbf{S}}^{\mathbf{r}},\mathbf{f}\in \mathbf{F}\end{array}$$

(4)

Factory and warehouse constraints

Constraint (5) ensures that each potential location can only be opened with one level of capacity. Constraint (6) ensures that the amount of material ordered from the supplier is exactly what is needed to produce the finished products. Constraints (7) and (8) limit production to the minimum and maximum quantities in general of each factory and also limit the maximum capacity per product, respectively. Finally, constraint (9) imposes the lower and upper limits of storage in each warehouse.

$$\begin{array}{cc}\hfill \sum _{q\in Q}^{}{z}_{lq}\le 1& l\in F\cup W\end{array}$$

(5)

$$\begin{array}{cc}\hfill \sum _{s\in S^r}^{}\sum _{t\in T_{sf}}^{}{x}_{sf}^{rt}=\sum _{p\in P^r}^{}\sum _{w\in W^p}^{}\sum _{t\in T_{fw}}^{}{A}^{rp}{x}_{fw}^{pt}& \end{array}$$

(6)

$$\begin{array}{cc}\hfill \sum _{q\in Q}^{}{\underline{MQ}}_{fq}{z}_{fq}\le \sum _{p\in P}^{}\sum _{w\in W^p}^{}\sum _{t\in T_{fw}}^{}MQ{U}^p{x}_{fw}^{pt}\le \sum _{q\in Q}^{}{\overline{MQ}}_{fq}{z}_{fq}& f\in F\end{array}$$

(7)

$$\begin{array}{cc}\hfill \sum _{w\in W^p}^{}\sum _{t\in T_{fw}}^{}MQ{U}^p{x}_{fw}^{pt}\le \sum _{q\in Q}^{}MQ{P}_{fq}^p{z}_{fq}& p\in P,f\in F\end{array}$$

(8)

$$\begin{array}{cc}\hfill \sum _{q\in Q}^{}{\underline{SQ}}_{wq}{z}_{wq}\le \sum _{p\in P}^{}\sum _{c\in C^p}^{}\sum _{t\in T_{wc}}^{}SQ{U}^{p}DE{M}_c^p{u}_{wc}^t\le \sum _{q\in Q}^{}{\overline{SQ}}_{wq}{z}_{wq}& w\in W\end{array}$$

(9)

Customer and flow retention constraints

Constraint (10) ensures that a customer is only dispatched from a warehouse and constraint (11) ensures that the quantity of product that reaches customers is the same as that which reaches the warehouses.

$$\begin{array}{cc}\hfill \sum _{w\in W}^{}\sum _{t\in T_{wc}}^{}{u}_{wc}^t=1& c\in C\end{array}$$

(10)

$$\begin{array}{cc}\hfill \sum _{c\in C^p}^{}\sum _{t\in T_{wc}}^{}DE{M}_c^p{u}_{wc}^t=\sum _{f\in F^p}^{}\sum _{t\in T_{fw}}^{}{x}_{fw}^{pt}& p\in P,w\in W\end{array}$$

(11)

Transport related constraints

Constraints (12)–(14) limit the minimum and maximum quantities to transport between origins and destinations.

$$\begin{array}{cc}\hfill {\underline{TQ}}_{sf}^t{u}_{sf}^t\le \sum _{r\in R}^{}TQ{U}^{rt}{x}_{sf}^{rt}\le {\overline{TQ}}_{sf}^t{u}_{sf}^t& s\in S,f\in F,t\in T_{sf}\end{array}$$

(12)

$$\begin{array}{cc}\hfill {\underline{TQ}}_{fw}^t{u}_{fw}^t\le \sum _{p\in P}^{}TQ{U}^{pt}{x}_{fw}^{pt}\le {\overline{TQ}}_{fw}^t{u}_{fw}^t& f\in F,w\in W,t\in T_{fw}\end{array}$$

(13)

$$\begin{array}{cc}\hfill {\underline{TQ}}_{wc}^t{u}_{wc}^t\le \sum _{p\in P}^{}TQ{U}^{pt}DE{M}_c^p{u}_{wc}^t\le {\overline{TQ}}_{wc}^t{u}_{wc}^t& w\in W,c\in C,t\in T_{wc}\end{array}$$

(14)

Binary and non-negativity constraints

$$\begin{array}{cc}\hfill z_{fq}\in \{0,1\}& f\in F,q\in Q\end{array}$$

(15)

$$\begin{array}{cc}\hfill z_{wq}\in \{0,1\}& w\in W,q\in Q\end{array}$$

(16)

$$\begin{array}{cc}\hfill v_{sf}^r\in \{0,1\}& s\in S,f\in F,r\in R\end{array}$$

(17)

$$\begin{array}{cc}\hfill x_{fw}^{pt}\in {\mathbb{R}}_{\ge 0}& f\in F,w\in W,p\in P,t\in T\end{array}$$

(18)

$$\begin{array}{cc}\hfill x_{sf}^{rt}\in {\mathbb{R}}_{\ge 0}& s\in S,f\in F,r\in R,t\in T\end{array}$$

(19)

$$\begin{array}{cc}\hfill u_{od}^t\in \{0,1\}& (o,d)\in \{(S,F)\cup (F,W)\cup (W,C)\},t\in T\end{array}$$

(20)

4.2. 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 opened following 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].

Algorithm 1 General algorithm.

1: Perform one of the two heuristics to decide the opening of warehouses w.

2: Solve the allocation model with the parameter $z_{wk}$ obtained in step 1.

3: Solve the reduced SCND model with the parameters $z_{wk}$ and $x_{wc}^{pt}$ obtained in the previous steps.

Algorithm 2 Simple Constructive Heuristics.

1: All the closed warehouses zw,q = {{0, 0, 0}, {0, 0, 0}, …, {0, 0, 0}}

2: Demanded storage capacity = ${\sum }_{p\in P}{\sum }_{c\in C^p}{\sum }_{t\in T_{wc}}SQ{U}^{p}DE{M}_c^p{u}_{wc}^t$

3: Available capacity = 0

4: Openw = {0, 0, 0,…, 0}

5: repeat

6:  repeat

7:   Generate random ws

8:   Generate random qs

9:  while Openws = 1

10:  Openws = 1

11:  $z_{wk,qs}$ = 1

12:  Available capacity = Available capacity + ${\overline{SQ}}_{ws,qs}$

13: while Available capacity < Demanded storage capacity

Algorithm 3 Constructive Heuristics with Probability.

1: All the closed warehouses zw,q = {{0, 0, 0}, {0, 0, 0}, …, {0, 0, 0}}

2: Demanded storage capacity = ${\sum }_{p\in P}{\sum }_{c\in C^p}{\sum }_{t\in T_{wc}}SQ{U}^{p}DE{M}_c^p{u}_{wc}^t$

3: Total warehouse unit costwq = Unit fixed costwq + Unit transportation costwq

4: Unit fixed costwq = $\frac{F{C}_{wq}}{{\overline{SQ}}_{wq}{\sum }_{p\in P}SQ{U}_p}$

5: Unit transportation costwq = $\frac{{\sum }_{w\in W}{\sum }_{p\in P}{\sum }_{c\in C^p}DE{M}_c^p}{|T_{wc}|·{\sum }_{w\in W}{\sum }_{p\in P}{\sum }_{c\in C^p}{\sum }_{t\in w_c}T{C}_{wc}^{pt}DE{M}_c^p}$

6: Probabilitywq = $\frac{1000}{{(\mathrm{Total}\mathrm{warehouse}\mathrm{unit}{\mathrm{cost}}_{wq})}^4}$

7: A probability distribution is made with Probabilitywq, ∀ w ∈ W, q ∈ Q

8: Available capacity = 0

9: Openw = {0, 0, 0, …, 0}

10: {ns: random number}

11:repeat

12:  repeat

13:   Generate random ns

14:   Select w and q corresponding to the random number ns

15:  while Openws = 1

16:  Openws = 1

17:  $z_{wq}$ = 1

18:  Available capacity = Available capacity + ${\overline{SQ}}_{wq}$

19: while Available capacity < Demanded storage capacity

4.2.1. Allocation Model

Allocation model 2.1 defines the decision variables $u_{wc}^{pt}$ which due to the nature of the problem is the largest set of variables since the number of these variables is defined by the expression $\left|W\right|·\left|C\right|·\left|P\right|·\left|T\right|$ assuming that you always have more customers than warehouses or factories.

In the case of the instances used for this work, the smallest number of variables $u_{wc}^{pt}$ used in one instance was 6000, so defining those variables alternately greatly reduces the number of branches explored by the branching and cutting algorithm. This is used in its default configuration in the IBM ILOG program CPLEX to solve mixed-integer linear programming models. The allocation model is presented below.

Variables

$$u_{od}^t=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{origin}o\mathrm{supplies}\mathrm{destination}d\mathrm{by}\mathrm{mode}\mathrm{of}\mathrm{transport}t,\\ & \left((o,d)\in \{(S,F)\cup (F,W)\cup (W,C)\};t\in T\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\end{array}\right.$$

The constraints used in the original model are constraints (9), (10), (14) and (21)

$$\begin{array}{cc}\hfill u_{wc}^t\in \{0,1\}& w\in W,c\in C,t\in T\end{array}$$

(21)

And the objective function is the following (22):

$$Min\sum _{p\in P}^{}\sum _{c\in C^p}^{}\sum _{w\in W^p}^{}\sum _{t\in T_{wc}}^{}DE{M}_c^{p}T{C}_{wc}^{pt}{u}_{wc}^t$$

(22)

4.2.2. Model of Reduced SCND

The variables of the model that become parameters are the following:

$$\begin{array}{cc}\hfill \mathit{Parameters}& \\ \hfill z_{wq}=& \left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{it}\mathrm{is}\mathrm{decided}\mathrm{to}\mathrm{open}\mathrm{a}\mathrm{warehouse}w\mathrm{with}\mathrm{a}\mathrm{capacity}\mathrm{level}q,\\ & \left(w\in W;q\in Q\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\\ \hfill \end{array}\right.\\ \hfill u_{wc}^t=& \left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{it}\mathrm{is}\mathrm{decided}\mathrm{to}\mathrm{open}\mathrm{a}\mathrm{warehouse}w\mathrm{with}\mathrm{a}\mathrm{client}c\mathrm{by}\mathrm{mode}\mathrm{of}\mathrm{transport}t,\\ & \left(w\in W;c\in C;t\in T\right)\\ 0\hfill & \mathrm{other}\mathrm{case}\\ \hfill \end{array}\right.\end{array}$$

The parameters that will no longer be used in model 2.2 with respect to the original are the following:

Parameters not used
$SQ{U}^p$	Storage capacity required to store a unit of p, $\left(p\in P\right)$
${\overline{SQ}}_{wq}$	Maximum storage capacity of warehouse f with level of capacity q, $\left(w\in W;q\in Q\right)$
${\underline{SQ}}_{wq}$	Minimu production capacity used by factory f with level of capacity q, $\left(w\in W;q\in Q\right)$

The SCND model defines the remaining decision variables of the original model, taking as parameters, the decision variables resolved by both the heuristic and the 2.1 allocation model, removing the constraints that are not necessary.

The model uses constraints (2) to (4), (6) to (8), (11) to (13), (15) to (19), and (23) to (24).

$$\begin{array}{cc}\hfill \sum _{q\in Q}^{}{z}_{fq}\le 1& f\in F\end{array}$$

(23)

$$\begin{array}{cc}\hfill u_{od}^t\in 0,1& (o,d)\in \{(S,F)\cup (F,W)\},t\in T\end{array}$$

(24)

The objective function is used the same as the original model, although some terms do not contain decision variables but parameters, with the aim of comparing the matheuristic solutions with those of the MILP.

5. Instances

The instances are generated by means of a methodology described by [25] that simulate reality. The size of the generated instances is shown in

Table 2. Size of the sets in each instance.

$\left|\mathit{C}\right|$	$\left|\mathit{S}\right|$	$\left|\mathit{F}\right|$	$\left|\mathit{W}\right|$	$\left|\mathit{Q}\right|$	$\left|\mathit{T}\right|$	$\left|\mathit{R}\right|$	$\left|\mathit{P}\right|$
100	10	10	20	3	3	20	20
125	13	13	25	3	3	25	25
150	15	15	30	3	3	30	30
175	18	18	35	3	3	35	35
200	20	20	40	3	3	40	40

and the size of the corresponding model is shown in

Table 3. Statistics of the instances and their values for MILP.

Name of the Instance	$\left|\mathit{C}\right|$	Number of Continuous Variables	Number of Binary Variables	Number of Constraints
*-100	100	18,000	8990	17,190
*-125	125	37,050	15,196	28,103
*-150	150	60,750	22,410	40,785
*-175	175	100,170	32,736	57,893
*-200	200	144,000	43,780	76,380

.

Transport mode 1 represents the train, which is not available for all locations and the minimum amount of transport is very high. Modes 2 and 3 represent land vehicles, mode 2 represents a small vehicle such as delivery vans, and mode 3 represents a larger cargo vehicle; these two are assumed to be hired through an external logistics provider so they do not have a maximum amount of transport. For mode 3 there is a minimum quantity to transport to justify the use of the larger vehicle. For each product-customer pair a random demand $DE{M}_{pc}=X\sim UNIFD[1,10]$, is generated, where X is a random number that follows a discrete uniform distribution $UNIFD[min,max]$ that goes from min to max. The fixed cost of opening a factory and a warehouse are defined by the following expression:

$$\begin{array}{c}\hfill F{C}_{fq}=1000\sqrt{\frac{{\overline{MQ}}_{fq}}{\frac{{\sum }_{p\in P}^{}MQ{U}_p}{\left|P\right|}}}\end{array}$$

(25)

$$\begin{array}{c}\hfill F{C}_{wq}=1000\sqrt{\frac{{\overline{SQ}}_{wq}}{\frac{{\sum }_{p\in P}^{}SQ{U}_p}{\left|P\right|}}}\end{array}$$

(26)

The acquisition cost of a material is generated by the following expression $P{C}_s^r=X\sim UNIFC[0.075,0.625]$ where $UNIFC\left[min,max\right]$ represents a continuous uniform distribution The manufacturing cost of a product is generated by the following expression $M{C}_f^p=X\sim UNIFC[0.375,1.25]$.

The other parameters are calculated using a more sophisticated methodology explained in Appendix A of the work by [25]. A Windows console program developed in $C++$ was carried out to generate an instance automatically to generate these instances.

6. Results

The generated instances were resolved with the mixed-integer linear programming model programmed in OPL in the IBM ILOG CPLEX 12.8.0 IDE, and the case of the matheuristics, an application in $C++$ Concert Technology was programmed with the use of CPLEX. Both were run on a Lenovo ThinkPad T580 computer with an Intel Core i7-8550U @ 1.80GHz processor and 16 GB of RAM.

The results obtained are shown in

Table 4. Table of results.

Instance	MILP *	Matheuristic ** Simple Heuristic	Matheuristic ** Heuristic with Probability	No. of Clients
1-100	$457,969	$533,871	$494,606	100
2-100	$396,124	$469,641	$437,017	100
3-100	$454,499	$528,758	$484,789	100
4-100	$454,535	$499,858	$451,079	100
5-100	$421,027	$438,128	$464,642	100
1-125	$603,112	$692,654	$643,217	125
2-125	$524,209	$624,083	$565,659	125
3-125	$569,020	$602,907	$617,547	125
4-125	$566,296	$646,428	$604,259	125
5-125	$521,739	$622,127	$577,284	125
1-150	$713,102	$796,459	$753,579	150
2-150	$709,303	$861,745	$770,492	150
3-150	$695,731	$789,834	$668,408	150
4-150	$713,282	$816,635	$717,607	150
5-150	$679,902	$768,746	$713,473	150
1-175	$912,030	$945,357	$904,579	175
2-175	$1,100,417	$970,647	$898,271	175
3-175	***	$930,802	$857,758	175
4-175	$1,099,033	$994,140	$939,693	175
5-175	$915,431	$865,468	$929,748	175
6-175	$882,227	$925,900	$798,514	175
7-175	$856,623	$912,108	$881,164	175
8-175	$940,480	$955,951	$912,570	175
9-175	***	$970,484	$854,358	175
10-175	$977,692	$965,596	$919,445	175
1-200	***	$1,153,589	$1,115,358	200
2-200	$1,061,059	$1,019,363	$963,204	200
3-200	***	$1,138,016	$1,015,605	200
4-200	***	$1,129,623	$1,019,119	200
5-200	***	$1,130,032	$994,430	200

* Target function values of incumbent solution running the solver with a 4-h limit; ** Target function values of incumbent solution running executable with a 2-h limit; *** No integer solution found.

, indicating the total cost obtained for each instance with the different methods compared.

The results show that as the instances increase in size, the computation time to obtain optimal solutions increases exponentially. In all the cases, the MILP reached the time limit of 4 h. Only for instances with 100 clients, the matheuristic algorithms achieved times below 25 min. However, for instances larger than 100 clients, the matheuristic algorithms reached the time limit of 2 h. Hence, obtaining results through the use of mathematical modeling becomes impractical for large instances.

It can be observed in Table 4 that when the size of the instance grows, i.e., it has a higher number of clients, the total cost increases also. Likewise, it can be seen that as the instance size increase, the difference between the quality of solutions provided by CPLEX and those provided by the matheuristics decreases. For instances of 100, 125 and 150 clients, the results of the matheuristic algorithm with the “simple heuristic” were just 14.20% on average above those obtained with CPLEX, and the results with the matheuristic algorithm with the “heuristics with probability” were only 6.06% on average above those obtained with CPLEX.

In the instances of both 175 and 200 clients, at least one of the two implemented matheuristics obtained a better solution than that of CPLEX in most of the cases. For the instances with 175 customers, the average improvement was 1.41% comparing the result of CPLEX and the result of the matheuristic algorithm with the “simple heuristic”. For the same instances, the average improvement was 5.96% comparing the result of CPLEX and the result of the matheuristic algorithm with the “heuristics with probability”. For the instance 2–200, the improvement was 3.93% comparing the result of CPLEX and the result of the matheuristic algorithm with the “simple heuristic”. For the same instance, the improvement was 9.22% comparing the result of CPLEX and the result of the matheuristic algorithm with the “heuristics with probability”. In six cases out of 15, with 175 and 200 clients, the matheuristic algorithms were able to find a feasible solution while CPLEX could not.

Comparing the two matheuristics, it can be observed that the heuristic method used to decide the opening of warehouses has a great impact on the objective functions for the type of instances used because the fixed cost of opening a warehouse is the cost with the greatest impact. Both the first and second heuristics diversify the results at each iteration so that in small instances, the algorithms may be used on more than one occasion to increase the quality of the solutions. Regarding the use of the probability distribution used for constructive heuristics with probability, although some randomness is applied, the selected warehouses will tend to be those with the lowest cost of opening divided by their capacity, so the quality of the solutions tends to be better. In average, for all the instances tested, the matheuristic algorithm with the “heuristics with probability” was 7.15% better than the algorithm with the “simple heuristic”.

For the interested reader, a further discussion about the SCND configurations obtained and the distribution of costs, according to the design of instances proposed in [25], can be found at [23].

7. Conclusions

In this work, a problem for supply-chain network design is addressed. This problem was presented in the literature by Corthinal et al. [23]. We selected this complex NP-Hard problem to prove the efficiency of novel matheuristic algorithms. Matheuristics are algorithms that combine heuristic rules with exact optimization methods based on mathematical programming. There is a growing interest in these methods in the search for improving the quality of solutions with a fast computation. Solving hard combinatorial optimization problems, Although heuristics and metaheuristics demonstrated efficiency in obtaining feasible but poor-quality solutions in short computation times, exact methods implemented in commercial and open-source software deliver optimal solutions at the cost of long execution times. In this way, the research in matheuristics looks for the benefits of hybridization.

The problem addressed has characteristics that increase the level of complexity compared to other problems of supply-chain network design solved with matheuristics. In addition to the classic decisions on the location of facilities and transportation, the problem involves determining capacities for the facilities, choosing between different transportation modes, and considering a hierachical product architecture as described by a bill of materials. Hence, this problem is a good challenge to demonstrate the efficiency of the methods proposed. The structure of the network and decisions presented can be used for the design of global manufacturing and distribution networks in high technology industries such as pharmaceutics, automotive, or electronics.

The main contribution of this paper is the proposal of novel matheuristic algorithms to solve a challenging combinatorial optimization problem for supply chain network design. The algorithms proposed were efficient in obtaining solutions of high quality in reasonable computation times for large instances.

To study larger instances or longer supply chains, the problem can be divided into more sub-problems with heuristic decisions in between. As we observed, it is possible to obtain better solutions with a well-thought heuristic in less time as data sets grow. Additionally, more complex decisions can be added to the model to integrate routing, inventory management, sustainability issues, and variability through stochastic modeling. The key to designing efficient matheuristics is the adequate decomposition of the problem to take advantage of the quality of exact methods using heuristics and randomness to boost the execution speed.