Solving public transportation routing problems through a metaheuristic algorithm inspired by slime mold behaviors
TÜBİTAK 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
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 inTurkey with the most active public transportation use.
Bio-inspired algorithms have reached, and in some cases even surpassed, the problem-solvingcapacity of traditional computational methods thanks to their ability to produce optimal resultsunder unfavorable conditions, reduce energy consumption and lower costs. Shortest path problemsdealing with the optimization of transportation networks and public transportation systems areamong the most discussed topics in computational intelligence [1]. In this context, manymetaheuristic approaches such as Ant Colony Optimization, Artificial Bee Colony Algorithm,Smart Water Drops Algorithm, Fish Swarm Algorithm have been used to solve classical NP-hardproblems such as Vehicle Routing Problem, Traveling Salesman Problem and Public TransportRouting Problem .
Therefore, in this project, an algorithm inspired by the plasmodium form ofthe acellular slime fungus Physarum polycephalum (Slime Mold Algorithm, SMA), which is oneof the prominent models in this context, was studied.The pathfinding mechanisms of P. polycephalum have been experimentally demonstrated tocreate networks with efficiency, fault tolerance and cost comparable to daily life infrastructurenetworks such as the Tokyo Subway system .
In addition, SMA has been widely andeffectively used in engineering designs, motion modules of intelligent robots, computer-basedphoto and sonar analysis, classification of genetic data, signal-to-noise separation, workshopscheduling problems and other optimization studies .
However, there is no study in theliterature on how effective SMA, a next generation metaheuristic algorithm, is in solving thesepublic transportation problems. Therefore, our aim is to test how adequate an SMA-derivedalgorithm is in route optimization, both in "standard" public transport models found in theliterature and in a model we have created for Istanbul's bus lines, and to compare obtained in routegeneration, energy minimization and optimal route selection with other algorithms.
Method
