## 3 The Proposed EATS-MOBFS Method for the 2L-VRPSC
### Framework of the Solution Mechanism
#### 3.1.2 Neighborhood Operators  
It is widely believed that the performance of the tabu search (TS) algorithm is greatly dependent on the neighborhood operators. To overcome the dependence of the algorithm on a single neighborhood, six neighborhood operators derived from the segment exchange (SE) [9] and move combination (MC) [9] are adopted. It is noteworthy that the loading feasibility of each route must be checked by invoking the proposed MOBFS heuristic in each iteration. During each search for candidate solutions, infeasible operations, which violate the two-dimensional loading constraints or vehicle capacity, are not allowed.  
**Segment exchange (SE):** This operator first selects two segments of customers (i.e., a sequence of customers) from different randomly chosen routes and then exchanges the positions of two segments of customers. Note that if the resulting solution is infeasible, the exchange is canceled. Moreover, considering the weights of items and loading constraints, a longer segment leads to a lower probability with, which this segment can have a successful exchange. To increase the probability of obtaining a feasible solution, the exchange is only executed between segments of the same length. Based on these considerations, the segment length is limited to two and three customers, and the corresponding neighborhood operators are denoted as **SE2** and **SE3**, respectively.  
**Move combination (MC):** This operator randomly selects two types from the six move types presented in Figure 2, which is marked as **MC2**. For each selected type, it repeatedly tries to execute a random move until the new resulting solution obtained by this move is feasible. The detailed move types are described as follows, which correspond to Figure 2a-f, respectively. More details about the move types can be found in [9; 12; 35].  
Intra-swap [35]: This operator tries to swap the positions of two customers selected from the same route.  
Inter-swap [9]: This neighborhood operator swaps the positions of two customers selected from different routes.  
Intra-shift [35]: For this operator, one customer is selected and removed from the current route and then inserted into another position of this route.  
Inter-shift [35]: For this operator, one customer is selected and removed from the current route and then inserted into another route.  
Intra-2 opt [9]: For a given route, two non-adjacent segments of customers are deleted, the middle segment of the route is reversed, and then two new segments of customers are generated and added to re-connect the route.  
Inter-2 opt [9]: Two segments of customers from two different routes are eliminated so that each route is divided into two parts; then, the first part of each route is concatenated with the second part of the other route to generate two new routes. If a route is empty, the other route is split into two new routes.  
Specifically, under the 2|UO|L and 2|UR|L settings, switching the service order of customers within the same route will not result in loading-infeasible solutions since the FILO constraints are not considered, and thus intra-route moves do not need to examine the loading feasibility. While the sequential constraints are imposed, the feasibility of the resulting solutions constructed by the intra-route and inter-route moves have to be examined, and only the solution satisfying the loading constraints can be accepted during the process.  
In order to balance the computation burden and quality of solutions, the EATS algorithm performs each individual operator one or two times. As a result, six neighborhood operators, **SE21** (perform **SE2** once), **SE22** (perform **SE2** twice), **SE31**, **SE32**, **MC21** and **MC22**, are derived.