# Joint Location-Allocation Model for Multi-Level Maintenance Service Network in Agriculture
## 4 Benders Decomposition Approach  
### MP and SP in Benders Decomposition  
Considering two integer variables \(\mathbf{w}\) and \(\mathbf{v}\) in the proposed MLFLAPs, a variant Benders decomposition, which is called compound Benders decomposition in this paper, is introduced to decompose the original MLFLAPs into the master problem (**MP**) and two subproblems (**SP\({}_{1}\)** and **SP\({}_{2}\)**). In **MP**, the location of service stations and spare part centres are determined in this paper using the decision variables \(\mathbf{x}\), \(\mathbf{y}\), \(\mathbf{z}\), and \(\mathbf{u}\). As for **SP\({}_{1}\)**, decision variables \(\mathbf{v}\) are introduced to determine the service vehicle allocation, and in **SP\({}_{2}\)**, decision variables \(\mathbf{w}\) are introduced for contiguity evaluation of service units served by one service station.  
\[\begin{array}{ll}\textbf{MP}&Min\underset{k}{\sum}c_{1}\times x_{k}+ \underset{j}{\sum}\underset{i}{\sum}2\times c_{3}\times z_{i}^{j}\times d_{i}^ {j}\times r_{i}+q\\ &\text{Subject to constraints(2)--(4), (7)--(12) and (17)--(18).}\\ &\textbf{SP}_{1}&\min\underset{j}{\sum}c_{2}\times v_{j}\\ &\text{Subject to constraints(5)--(6) and (17)}\\ &\textbf{SP}_{2}&0:\mathbf{w}\\ &\text{Subject to constraints (13)--(16)}\end{array} \tag{19}\]  
### MP and SP in Benders Decomposition  
As for decision variables \(\mathbf{v}\) in **SP\({}_{1}\)**, they are applied to obtain minimal service vehicle usage costs and are subject to constraints (5)-(6) and (17). Thus, the dual **SP\({}_{1}\)** for variable \(\mathbf{v}\) is shown as **DSP\({}_{1}\)**  
\[\textbf{DSP}_{1}\hskip 56.905512 pt\max\ m\times\alpha+\beta_{j}\times\underset{i }{\sum}z_{i}^{j}\times r_{i} \tag{22}\]  
s. t.  
\[C\times\alpha+\beta_{j}\leq c_{2} \tag{23}\]  
\[\alpha\leq 0 \tag{24}\]\[\beta_{j}\geq 0,\forall j \tag{25}\]  
Thus, during the Benders decomposition approach, the obtained facility location results and service assignment plan will be introduced to \(\mathbf{DSP}_{1}\) to solve the \(\mathbf{DSP}_{1}\). If there is no feasible solution for \(\mathbf{DSP}_{1}\), there is no feasible solution for the original MLFLAPs, which means the number of service vehicles cannot meet all maintenance demands in the service network. If the \(\mathbf{DSP}_{1}\) is unbounded, there exist optimal solutions for original MLFLAPs, and the generated Benders feasibility cuts in (26) are added in \(\mathbf{MP}\). If the \(\mathbf{DSP}_{1}\) is feasible and bounded, the generated Benders optimality cuts in (27) are added in \(\mathbf{MP}\).  
\[m\times\alpha+\beta_{j}\times\sum_{i}z_{i}^{j}\times r_{i}\leq 0 \tag{26}\]  
\[m\times\alpha+\beta_{j}\times\sum_{i}z_{i}^{j}\times r_{i}\leq q \tag{27}\]  
As for \(\mathbf{SP}_{2}\), the facility location results and service assignment results obtained in \(\mathbf{MP}\) are introduced for contiguity evaluation. If the \(\mathbf{SP}_{2}\) returns a feasible solution, the service units served by service stations are contiguous. Otherwise, it demonstrates that there exists at least one service unit which is not contiguous with other service units served by one service station. Selected locations of service stations that are not contiguous are denoted as \(J^{*}\). Thus, as for these service units served by these service stations in \(J^{*}\), at least one service unit should be removed or one new service unit should be added, which can be described as shown in constraint (28). Thus, the combinatorial Benders cuts in (28) are generated and added to \(\mathbf{MP}\).  
\[\sum_{i:\overline{y}_{i}^{j}=0}y_{i}^{j}+\sum_{i:\overline{y}_{i}^{j}=1}\left( 1-y_{i}^{j}\right)\geq 1,\forall j\in J^{*} \tag{28}\]