Recently proposed search strategies improve the computational cost of the bicycle sharing problem
Bike-sharing systems (BSS) are transport solutions in which users can rent a bike from a depot or “port”, travel, and then return the bike to the same port or a different port. BSSs are gaining popularity around the world as they are environmentally friendly, reduce traffic congestion and provide additional health benefits to users. But eventually a port becomes full or empty in a BSS. This means users can no longer rent a bike (when empty) or return one (when full). To fix this, bikes need to be rebalanced between ports on a BSS so users can still ride them. This rebalancing must also be done in a way that benefits BSS companies so that they can reduce labor costs, as well as carbon emissions from rebalancing vehicles.
There are several existing approaches for BSS rebalancing, however, most of the solution algorithms are computationally expensive and time consuming 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 Professor Tohru Ikeguchi of Tokyo University of Science proposed a “multi-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 boundaries of the problem. Now, in a recent study published in the MDPI’s Applied Science, the team proposed two strategies to find approximate solutions to mBSSRP-S that can reduce computational costs without affecting performance. The research team also included PhD student Ms. Honami Tsushima from Tokyo University of Science and Professor Takafumi Matsuura from the Nippon Institute of Technology.
Describing their research, Professor Ikeguchi says: “We previously offered mBSSRP-S and it offered improved performance over our original mBSSRP, which did not allow constraint violation. But mBSSRP-S also increased overall computational capacity. cost of the problem as it had to compute both the feasible and infeasible solutions of the mBSSRP. Therefore, we have now proposed two consecutive search strategies to solve this problem.
The proposed search strategies search for feasible solutions in a much shorter time frame compared to that initially proposed with mBSSRP-S. The first strategy focuses on reducing the number of “neighbor” solutions (solutions that are numerically close to a solution to the optimization problem) before finding a feasible solution. The strategy uses two well-known algorithms called “Or-opt” and “CROSS-exchange”, to reduce the overall time needed to calculate a solution. The feasible solution here refers to values that satisfy the constraints of mBSSRP.
The second strategy modifies the problem to be solved according to the feasible solution to the mBSSRP problem or the mBSSRP-S problem, and then finds good near-optimal solutions in a short time by Or-opt or CROSS-exchange.
The research team then performed numerical experiments to assess the computational cost and performance of their algorithms. “Through the application of these two strategies, we were able to reduce computation time while maintaining performance,” reveals Professor Ikeguchi. “We also found that once we calculated the feasible solution, we could quickly find short travel times for rebalancing vehicles by solving the hard constraint problem, mBSSRP, instead of mBSSRP-S.”
The popularity of BSS is only expected to grow in the future. The novel solution-finding strategies proposed here will go a long way toward achieving practical and comfortable BSS that benefits users, businesses, and the environment.
Source of the story:
Materials provided by Tokyo University of Science. Note: Content may be edited for style and length.