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 '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.
***
Reference
DOI: https://doi.org/10.3390/app12052675
About The Tokyo University of Science
Tokyo University of Science (TUS) is a well-known and respected university, and the largest science-specialized private research university in Japan, with four campuses in central Tokyo and its suburbs and in Hokkaido. Established in 1881, the university has continually contributed to Japan's development in science through inculcating the love for science in researchers, technicians, and educators.
With a mission of "Creating science and technology for the harmonious development of nature, human beings, and society", TUS has undertaken a wide range of research from basic to applied science. TUS has embraced a multidisciplinary approach to research and undertaken intensive study in some of today's most vital fields. TUS is a meritocracy where the best in science is recognized and nurtured. It is the only private university in Japan that has produced a Nobel Prize winner and the only private university in Asia to produce Nobel Prize winners within the natural sciences field.
Website: https://www.tus.ac.jp/en/mediarelations/
About Professor Tohru Ikeguchi from Tokyo University of Science
Tohru Ikeguchi received M.E. and Ph.D. degrees from Tokyo University of Science, Japan. After working for nearly a decade as Full Professor at Saitama University, Japan, he worked at Tokyo University of Science as Full Professor at the Department of Management Science from 2014 to 2016. Since then, he has been a Full Professor at the Department of Information and Computer Technology in Tokyo University of Science. His research interests include nonlinear time series analysis, computational neuroscience, application of chaotic dynamics to solving combinatorial optimization problems, and complex network theory. He has published over 230 papers and proceedings.
Websites:
https://www.tus.ac.jp/en/fac/p/index.php?1174
http://www.hisenkei.net/~tohru/en/
Funding information
The research of Takafumi Matsuura was supported by JSPS KAKENHI Grant Numbers JP19K04907 and JP21H03514. The research of Tohru Ikeguchi was supported by JSPS KAKENHI Grant Numbers 20H00596 and JP21H03514.
