A novel solution to a combinatorial optimization problem in bicycle sharing systems

Traffic congestion has been worsening since the 1950s in large cities thanks to the exorbitant number of cars sold each year. Unfortunately, the figurative price tag attached to excessive traffic includes higher carbon dioxide emissions, more collectively wasted time, and exacerbated health problems. Many municipalities have tackled the problem of traffic by implementing bicycle sharing systems, in which people can borrow bikes from strategically placed ports and ride wherever they want, as long as they eventually return the bikes to a port, although not necessarily the one from where the bike was originally obtained.

As one may or may not immediately notice, this last permission creates a new problem by itself. Whenever someone borrows a bike and does not make a round trip with it, an additional bike crops up at the destination port just as there’s a loss of one bike at the origin port. As time passes, the distribution of bikes across ports becomes unbalanced, causing both an excessive accumulation of bikes at certain ports and a dearth of bikes in others. This issue is generally addressed by periodically sending out a fleet of vehicles capable of transporting multiple bikes in order to restore ports to their ‘ideal’ number of bikes.

Much research has been dedicated to the bicycle rebalancing problem using a fleet of vehicles. Finding the optimal routing paths for the vehicles is in and of itself a highly complex mathematical problem in the field of combinatorial optimization. One must make sure that the optimization algorithms used can reach a good-enough solution in a reasonable time for a realistically large number of ports and vehicles. Many methods, however, fail to find feasible solutions when multiple constrains are considered simultaneously, such as time, capacity, and loading/unloading constraints for the vehicles (Figure 1).

But what if we allowed the optimization strategy to change the strategies a little bit to make the best out of difficult situations? In a recent study published in MDPI’s Applied Sciences, a team of scientists suggested an innovative twist to the routing problem of bicycle sharing systems using this concept. Led by Professor Tohru Ikeguchi of Tokyo University of Science, the team comprising PhD student Honami Tsushima from Tokyo University of Science and Associate Professor Takafumi Matsuura from Nippon Institute of Technology, Japan, proposed a new formulation of the routing problem in which the constraints imposed on the routings can be violated. This enabled using the optimization algorithm for exploring what is known as the space of “infeasible solutions.” Prof. Ikeguchi explains their reasoning, “In real life, if a work can be completed through overtime within a few minutes, we would work beyond the time limit. Similarly, if we are only carrying four bikes and need to supply five, we would still supply the four we have.”

Following this line of thought, the researchers formulated the “soft constraints” variant of the routing problem in bicycle rebalancing. Using this approach, instead of outright excluding solutions that violate constraints, these can be considered valid paths that incur dynamically adjusted penalties and taken into consideration when assessing possible routings. This approach enabled the team to devise an algorithm that can make use of the space of infeasible solutions to speed up the search for optimal or near-optimal solutions. 

The researchers evaluated the performance of their method through numerical experiments with benchmark problems including up to 50 ports and three vehicles. The results show that their strategy could find optimal or near-optimal solutions in all cases, and that the algorithm could search both the feasible and infeasible solution spaces efficiently. This paints a brighter future for people in cities with congested traffic in which bicycle sharing systems could become an attractive solution. As Prof. Ikeguchi remarks, “It is likely that bike sharing systems will spread worldwide in the future, and we believe that the routing problem in bicycle rebalancing is an important issue to be solved in modern societies.”

Hopefully, further efforts to improve bicycle sharing systems will alleviate traffic congestion and make people’s lives in big cities healthier and more enjoyable.

***

Reference
DOI: https://doi.org/10.3390/app11167749

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.

Funding information

The study was supported by JSPS KAKENHI Grant Numbers JP19K04907, JP21H03514, JP17K00348, JP20H000596, and JP21H03514.