## 1 Introduction
(2009) [29] used two different candidate lists, that is, the nearest neighbors and quadrant neighbors to solve a large scale TSP. Finally, [PERSON] et al. (2019) [30] showed that the computational costs of heuristic methods can be significantly reduced by constructing a set of edges that are considered to be included in the optimal solution at first. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Paper** & **Static or Dynamic** & **Maximum Number of Port Size** \\ \hline [PERSON] et al. (2013) & static & 90 \\ [PERSON] et al. (2013) & static & 90 \\ [PERSON] et al. (2013) & static & 700 \\ [PERSON] et al. (2014) & dynamic & 90 \\ [PERSON] et al. (2014) & static & 116 \\ [PERSON] et al. (2016) & static & 564 \\ [PERSON] et al. (2018) & dynamic & 280 \\ This study & static & 100 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of the related literatures. Regarding the BSS, [PERSON] et al. (2016) [31] used a candidate list based on nearest neighbors to efficiently solve the static complete rebalancing problem. Then, [PERSON] et al. (2016) [12] used some formulations to determine whether constraints are satisfied or not to speed up the computation of bike sharing rebalancing problem. Thus, it is important to reduce the computational costs for finding a good rebalancing tour of the BSS, because a BSS has hundreds of ports and it is not practical to wait for hours to find a rebalancing tour of the BSS. Then, the goal of this study is to propose efficient search strategies with low computational costs while maintaining the performance of the mBSSRP. To reduce computational costs in this study, we focused on the search process and investigated the rate of the Or-opt and the CROSS-exchange executions. The execution rate of the Or-opt that inserts ports in the normal order was 66%, that of the CROSS-exchange that exchanges ports in the normal order was 20%, and the reverse orders of insertion of the Or-opt and exchange of the CROSS-exchange were rarely executed. In addition, we found that once a feasible solution of the mBSSRP is obtained, our conventional method [20] searches for the feasible solutions successively. From these results of the investigation, in this paper, we propose two search strategies: the first one is to reduce neighborhood solutions to obtain a feasible solution in a short time before finding a feasible solution of the mBSSRP from the mBSSRP-S, and the second one is to change the problem to be solved (mBSSRP or mBSSRP-S) after a feasible solution is obtained and to search good near-optimal solutions in a short time. As the first search strategy, we propose two search methods for reducing the number of neighborhood solutions in the Or-opt and the CROSS-exchange, and compare their performance with our previous results. The results of the numerical experiments indicate that by limiting the neighborhood solutions to the normal order insertion of the Or-opt and the normal order exchange of the CROSS-exchange, we obtained feasible solutions within a short time while maintaining the performance. Next, as the second search strategy after obtaining a feasible solution, we proposed four methods in which the searching space is further reduced. The problem to be solved is changed from mBSSRP-S to mBSSRP to explore only feasible solutions. The results of the numerical experiments show that by reducing the number of the neighborhood solution, only searching for the normal order insertion of the Or-opt and the normal order exchange of the CROSS-exchange with hard constraints after obtaining a feasible solution can obtain short tours within a short time. From these numerical experiments, we have succeeded in reducing the computational time while maintaining the performances. Furthermore, we found that after finding a feasible solution, we could find short tours within a short time by solving the hard constraint problem instead of the soft constraint problem. This paper is structured as follows. In Section 2, we describe the mBSSRP and mBSSRP-S. In Section 3, we present the heuristic method.