Bicycle sharing systems have emerged as an appealing option for reducing traffic congestion in congested cities. However, rebalancing the number of bikes at each port over time is critical, and determining the optimal routing paths for the vehicles in charge of rebalancing is a combinatorial optimization problem. Scientists have now proposed an innovative algorithm that can find near-optimal solutions faster, even for a large number of ports, paving the way for more efficient bicycle-sharing systems.
Large-city traffic congestion has been worsening since the 1950s, owing to the exorbitant number of cars sold each year. Unfortunately, the figurative cost of excessive traffic includes increased carbon dioxide emissions, more collectively wasted time, and worsened health issues. Many municipalities have addressed traffic issues 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, which may or may not be the one from which the bike was originally obtained.
In real life, if a task can be completed in a few minutes by working overtime, we would work past the time limit. Similarly, if we only have four bikes and need to supply five, we will continue to supply the four we have.
Professor Tohru Ikeguchi
This last permission, as one may or may not immediately notice, creates a new problem on its own. When someone borrows a bike but does not return it, an additional bike appears at the destination port, while one bike is lost at the origin port. As time passes, the distribution of bikes across ports becomes unbalanced, resulting in an overabundance of bikes at some ports and a scarcity of bikes at others. This problem is typically addressed by dispatching a fleet of vehicles capable of transporting multiple bikes on a regular basis in order to restore ports to their ‘ideal’ number of bikes.
Many studies have been conducted on the bicycle rebalancing problem using a fleet of vehicles. Finding the optimal vehicle routing paths is a highly complex mathematical problem in the field of combinatorial optimization. It is necessary to ensure that the optimization algorithms used can reach a good-enough solution in a reasonable amount of time for a realistically large number of ports and vehicles. Many methods, however, fail to find feasible solutions when multiple constraints, such as time, capacity, and vehicle loading/unloading constraints, are considered concurrently.
But what if we let the optimization strategy tweak the strategies a little to make the best of a bad situation? Using this concept, a team of scientists proposed an innovative twist to the routing problem of bicycle sharing systems in a recent study published in MDPI’s Applied Sciences.
The team, led by Professor Tohru Ikeguchi of Tokyo University of Science and including PhD student Honami Tsushima of Tokyo University of Science and Associate Professor Takafumi Matsuura of Nippon Institute of Technology in Japan, proposed a new formulation of the routing problem in which the constraints imposed on routings can be violated. This allowed the optimization algorithm to be used to explore the space of “infeasible solutions.”
Prof. Ikeguchi elaborates on their reasoning “In real life, if a task can be completed in a few minutes by working overtime, we would work past the time limit. Similarly, if we only have four bikes and need to supply five, we will continue to supply the four we have.”
Following this line of thought, the researchers developed the “soft constraints” variant of the bicycle rebalancing routing problem. Using this approach, instead of excluding solutions that violate constraints outright, these can be considered valid paths that incur dynamically adjusted penalties and are taken into account when evaluating possible routings. Using this approach, the team was able to create an algorithm that can use the space of infeasible solutions to accelerate the search for optimal or near-optimal solutions.
The researchers assessed the method’s performance using numerical experiments with benchmark problems involving up to 50 ports and three vehicles. The results show that their strategy was capable of finding optimal or near-optimal solutions in all cases, and that the algorithm was capable of efficiently searching both the feasible and infeasible solution spaces. This paints a more promising future for people living in cities with congested traffic, where bicycle sharing systems could be an appealing solution. “It is likely that bike sharing systems will spread worldwide in the future,” Prof. Ikeguchi says, “and we believe that the routing problem in bicycle rebalancing is an important issue to be solved in modern societies.”
Hopefully, additional efforts to improve bicycle sharing systems will reduce traffic congestion and make people’s lives in big cities healthier and more enjoyable.
