Solving public transportation routing problems through a metaheuristic algorithm inspired by slime mold behaviors
TUBITAK Research Projects Competition for High School Students
The many-headed slime mushroom (Physarum polycephalum) is creature that has inspired computational algorithms with its behaviors of solving mazes and optimizing food without a central command base that can be described as a "brain".
Studies that mathematically model the network fan and food transport strategy and use the behavioral algorithm to solve theoretical and practical problems in engineering and robotics are widespread. However, these algorithms are not used for problems that require searching in a discrete solution space, such as the urban transit routing problem.
In our study, we developed an algorithm that solves routing problems with a method inspired by the widely used Chunky Mushroom Algorithm. This program was tested both on the Mandl public transportation system, which is used in the literature to compare different methods, and on a system we created from bus lines in Istanbul.
It is planned that this algorithm, which finds the optimal routes for a given map and the number of passengers who want to go between any two stops, will be developed to prevent public transportation problems in Istanbul and contribute to actions such as rerouting in case of accidents and natural disasters.
Scientific Poster
Main Objective
This research focuses on the most appropriate layout "from the plasmodium's point of view" when planning the most frequently used bus lines in Istanbul, the most densely populated city in Turkey with the most active public transportation use.
Bio-inspired algorithms have reached, and in some cases even surpassed, the problem-solving capacity of traditional computational methods thanks to their ability to produce optimal results under unfavorable conditions, reduce energy consumption, and lower costs.
Shortest path problems dealing with the optimization of transportation networks and public transportation systems are among the most discussed topics in computational intelligence [1]. In this context, many metaheuristic approaches, such as Ant Colony Optimization, Artificial Bee Colony Algorithm, Smart Water Drops Algorithm, and Fish Swarm Algorithm, have been used to solve classical NP-hard problems such as the Vehicle Routing Problem, Traveling Salesman Problem, and Public Transport Routing Problem.
Therefore, in this project, an algorithm inspired by the plasmodium form of the acellular slime fungus Physarum polycephalum (Slime Mold Algorithm, SMA), which is one of the prominent models in this context, was studied. The pathfinding mechanisms of P. polycephalum have been experimentally demonstrated to create networks with efficiency, fault tolerance, and cost comparable to daily life infrastructure networks such as the Tokyo Subway system.
In addition, SMA has been widely and effectively used in engineering designs, motion modules of intelligent robots, computer-based photo and sonar analysis, classification of genetic data, signal-to-noise separation, workshop scheduling problems, and other optimization studies.
However, there is no study in the literature on how effective SMA, a next-generation metaheuristic algorithm, is in solving these public transportation problems. Therefore, our aim is to test how adequate an SMA-derived algorithm is in route optimization, both in "standard" public transport models found in the literature and in a model we have created for Istanbul's bus lines, and to compare the obtained results in route generation, energy minimization, and optimal route selection with other algorithms.