Newly proposed search strategies improve computational cost of the bicycle-sharing problem

There are several existing approaches to BSS rebalancing, however, most solution algorithms are computationally expensive and take a lot of time to find an 'exact' solution in cases where there are a large number of ports. Even finding an approximate solution is computationally expensive. Previously, a research team led by Prof. Tohru Ikeguchi from Tokyo University of Science proposed a 'multiple-vehicle bike sharing system routing problem with soft constraints' (mBSSRP-S) that can find the shortest travel times for multiple bike rebalancing vehicles with the caveat that the optimal solution can sometimes violate the real-world limitations of the problem. Now, in a recent study published in MDPI's Applied Sciences, the team has proposed two strategies to search for approximate solutions to the mBSSRP-S that can reduce computational costs without affecting performance. The research team also featured PhD student Ms. Honami Tsushima of Tokyo University of Science and Prof. Takafumi Matsuura of Nippon Institute of Technology.

Describing their research, Prof. Ikeguchi says, "Earlier, we had proposed the mBSSRP-S and that offered improved performance as compared to our original mBSSRP, which did not allow the violation of constraints. But the mBSSRP-S also increased the overall computational cost of the problem because it had to calculate both the feasible and infeasible solutions of the mBSSRP. Therefore, we have now proposed two consecutive search strategies to address this problem."

The proposed search strategies look for feasible solutions in a much shorter period of time as compared to the one originally proposed with mBSSRP-S. The first strategy focuses on reducing the number of 'neighboring' solutions (solutions that are numerically close to a solution to the optimization problem) before finding a feasible solution. The strategy employs two well-known algorithms called 'Or-opt' and 'CROSS-exchange,' to reduce the overall time taken to compute a solution. The feasible solution here refers to values that satisfy the constraints of mBSSRP.

The second strategy changes the problem to be solved based on the feasible solution to either the mBSSRP problem or the mBSSRP-S problem and then searches for good near-optimal solutions in a short time by either Or-opt or CROSS-exchange.

The research team then performed numerical experiments to evaluate the computational cost and performance of their algorithms. "With the application of these two strategies, we have succeeded in reducing computational time while maintaining performance," reveals Prof. Ikeguchi. "We also found that once we calculated the feasible solution, we could find short travel times for the rebalancing vehicles quickly by solving the hard constraint problem, mBSSRP, instead of mBSSRP-S."

The popularity of BSSs is only expected to grow in the future. The new solution-search strategies proposed here will go a long way towards realizing convenient and comfortable BSSs that benefit users, companies, and the environment.