## 4 Computational Cost Reduction Method  
To reduce neighborhood solution and computational costs, we investigate the percentage of the Or-opt and the CROSS-exchange executions used in the tabu search part. The feasible neighborhood solutions of the mBSSRP-S include the infeasible neighborhood solutions of the mBSSRP. Therefore, when we solve the mBSSRP-S, it takes more time to determine the next solution than in the case of mBSSRP. To reduce the computational cost of solving mBSSRP-S, we need to remove unnecessary neighborhood solutions. The percentage of the insertion and exchange operations performed by the proposed method was approximately 66% for the Or-opt, which inserts ports in the normal order (Figure 3(b)), and approximately 20% for the CROSS-exchange, which exchanges ports in the normal order (Figure 4(b)), implying that the reverse order of insertion and exchange was rarely executed. Thus, we did not search for less frequently performed reverse order operations to reduce the computational costs. In our previous study, we have shown that once a feasible solution of the mBSSRP is obtained, the proposed method searches for the feasible solutions successively [20]. Next, to find a good feasible solution of the mBSSRP, we examine whether we should change the problem to be solved (mBSSRP or mBSSRP-S) before and after a feasible solution is obtained.  
Table 2 summarizes the search strategy before obtaining a feasible solution of the mBSSRP. We propose two search methods (1B-S and 1C-S) in this case. In Table 2, the first search method 1A-S searches for all neighborhood solutions of the Or-opt and the CROSS-exchange. Thus, this search method is the same as the conventional search method [20]. The second search method 1B-S only explores insertion of the normal order of the Or-opt which is the most executed (Figure 3(b)). The third search method 1C-S searches for the insertion of the normal order of the Or-opt and exchange of the normal order of the CROSS-exchange (Figures 3(b) and 4(b)). The goal of the search methods before obtaining a feasible solution is to find a feasible solution within a short time for all trials.  
In addition, to further reduce the computational costs the search strategy is changed after a feasible solution of mBSSRP is obtained. In this paper, we propose four new search methods (2B-S, 2B-H, 2C-S and 2C-H). Table 3 shows the search strategy after finding a feasible solution of the mBSSRP. In Table 3, the first search method 2A-S involves to searching for all neighborhood solutions of the Or-opt and the CROSS-exchange with soft constraints. The second search method 2A-H involves searching for all neighborhood solutions of the Or-opt and the CROSS-exchange with hard constraints. The difference between the search methods 2A-S and 2A-H is whether the instances are solved with hard or soft constraints. The reason why we introduced both soft and hard constraints is that we found that once a feasible solution of the mBSSRP is obtained, our conventional method [20] searches for the feasible solutions successively. Then, 2A-S and 2A-H are the same as the conventional search method [20]. The third search method 2B-S only searches for insertion in the normal order of the Or-opt with soft constraints. The fourth search method 2B-H only searches for insertion in the normal order of the Or-opt with hard constraints. The fifth search method 2C-S explores the insertion of the normal order of the Or-opt and the exchange of the normal order of the CROSS-exchange with soft constraints. Finally, the sixth search method 2C-H explores the insertion of the normal order of the Or-opt and the exchange of the normal order of the CROSS-exchange with hard constraints.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
\begin{tabular}{c} Reverse \\ \end{tabular} & & & & & \\