A new solution to combinatorial optimization

0

image: In (a), the vehicle can satisfy the given loading constraint because it can embark the three excess bikes at port i. However, in (b), the vehicle violates the loading constraint because it only has room for one of the three excess bicycles at the port. Likewise, in (c), the vehicle violates the supply constraint because it can only supply one bicycle to port i, which needs three. In the proposed strategy, these constraints are treated as flexible constraints in the formulation of the problem. This approach allows an algorithm search for feasible and infeasible solution spaces and accelerates the search for quasi-optimal or optimal solutions.
seen Following

Credit: Tohru Ikeguchi of Tokyo University of Science

Traffic jams have worsened since the 1950s in major cities thanks to the exorbitant number of cars sold each year. Unfortunately, the figurative price attached to excessive trafficking includes higher carbon dioxide emissions, more collective waste of time, and exacerbated health problems. Many municipalities have tackled the traffic problem by setting up self-service bicycle systems, in which people can borrow bikes from strategically placed ports and move wherever they want, provided they eventually hand them over. bicycles in a port, but not necessarily the one from which the bicycle was originally obtained.

As one can notice immediately or not, this last authorization creates in itself a new problem. Each time someone borrows a bicycle and does not go back and forth with it, an additional bicycle occurs at the destination port just as there is a loss of a bicycle at the originating port. Over time, the distribution of bicycles between ports becomes imbalanced, causing both an excessive accumulation of bicycles in some ports and a shortage of bicycles in others. This problem is usually solved by periodically sending a fleet of vehicles capable of carrying multiple bicycles in order to restore ports to their “ideal” number of bicycles.

Much research has been devoted to the problem of rebalancing bicycles using a fleet of vehicles. Finding the optimal routing paths for vehicles is in itself a very complex mathematical problem in the field of combinatorial optimization. It must be ensured that the optimization algorithms used can reach a sufficiently good solution within a reasonable time frame for a realistic number of ports and vehicles. However, many methods fail to find workable solutions when multiple constraints are considered simultaneously, such as time, capacity and loading / unloading constraints for vehicles (Figure 1).

But what if we let the optimization strategy change the strategies a bit to make the most of tough situations? In a recent study published in the MDPI Applied Science, a team of scientists has 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 consisting of doctoral student Honami Tsushima of Tokyo University of Science and Associate Professor Takafumi Matsuura of 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 made it possible to use the optimization algorithm to explore what is called the space of “infeasible solutions”. Professor Ikeguchi explains their reasoning: “In real life, if a job could be completed within minutes of overtime, we would be working beyond the time limit. Likewise, if we only carry four bikes and need to provide five, we will always provide the four we have.

Following this line of thought, the researchers formulated the “soft constraints” variant of the routing problem in rebalancing bikes. Using this approach, instead of outright excluding solutions that violate constraints, these can be viewed as valid paths that result in penalties that are dynamically adjusted and taken into account when evaluating possible routes. This approach allowed the team to design an algorithm that can use the infeasible solution space to accelerate the search for optimal or near-optimal solutions.

The researchers evaluated the performance of their method through numerical experiments with baseline problems comprising up to 50 ports and three vehicles. The results show that their strategy can find optimal or quasi-optimal solutions in all cases, and that the algorithm can efficiently search for feasible and infeasible solution spaces. This foreshadows a better future for the inhabitants of congested cities, in which bicycle-sharing systems could become an attractive solution. As Professor Ikeguchi points out, “It is likely that bike sharing systems will spread around the world in the future, and we believe that the routing problem in rebalancing bikes is an important issue to be addressed in modern societies.. “

Hopefully, further efforts to improve bicycle sharing systems will reduce traffic jams and make the lives of people in big cities healthier and more enjoyable.

***

Reference
DO I: https://doi.org/10.3390/app11167749

About Tokyo University of Science

Tokyo University of Science (TUS) is a well-known and respected university, and the largest private science research university in Japan, with four campuses in central Tokyo and its suburbs and in Hokkaido. Founded in 1881, the university has continuously contributed to the scientific development of Japan by instilling a love of science in researchers, technicians and educators.
With the mission of “To create science and technology for the harmonious development of nature, humans and society”, TUS has undertaken a wide range of research ranging from basic science to applied science. TUS has taken a multidisciplinary approach to research and has undertaken intensive studies in some of today’s most vital fields. TUS is a meritocracy where the best of science is recognized and encouraged. It is the only private university in Japan that has produced a Nobel Laureate and the only private university in Asia to produce Nobel Laureates in the natural sciences.

Website: https://www.tus.ac.jp/en/mediarelations/

About Professor Tohru Ikeguchi of Tokyo University of Science

Tohru Ikeguchi holds a master’s and doctoral degree from Tokyo University of Science, Japan. After working for nearly a decade as a full professor at Saitama University, Japan, he worked at Tokyo University of Science as a full professor at the Department of Management Science from 2014 to 2016. Since then he has been Full Professor in the Department of Public Information. and computer technology at Tokyo University of Science. His research interests include the analysis of nonlinear time series, computational neuroscience, the application of chaotic dynamics to solving combinatorial optimization problems, and complex network theory. He has published over 230 articles and proceedings.

Funding Information

The study was funded by grant numbers JSPS KAKENHI JP19K04907, JP21H03514, JP17K00348, JP20H000596, and JP21H03514.


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of any press releases posted on EurekAlert! by contributing institutions or for the use of any information via the EurekAlert system.


Source link

Leave A Reply

Your email address will not be published.