New Search Strategies improve Computational Cost of the Bicycle-Sharing Problem
Bicycle sharing is an attractive zero-carbon transportation option for a world that is being increasingly disrupted by climate change.
But bikes need to be restored at bike ports every now and then. Calculating the optimal way to restore bicycles is time consuming and computationally expensive. Recently, researchers from Tokyo University of Science have built upon their previous optimization algorithm to propose two strategies to reduce computational costs while maintaining the performance of the algorithm.
Bicycle sharing systems (BSSs) are transport solutions wherein users can rent a bicycle from a depot or ‘port,’ travel, and then return the bike to the same port or different port. BSSs are growing in popularity around the world because they are eco-friendly, reduce traffic congestion, and offer added health benefits to users. But eventually, a port becomes either full or empty in a BSS. This means that users are no longer able to rent a bike (when empty) or return one (when full).
To address this issue, bikes need to be rebalanced among the ports in a BSS so that users are always able to use them. This rebalancing must also be carried out in a way that is beneficial to BSS companies so that they can reduce labor costs, as well as carbon emissions from rebalancing vehicles.
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 ‘neighbouring’ 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.
