A comparison of meta-heuristic and hyper-heuristic algorithms in solving an urban transit routing problems

Abstract

Public transport is a serious problem that is difficult to solve in many countries. Public transport routing optimization problem also known as urban transit routing problem (UTRP) is time-consuming process, therefore effective approches are urgently needed. UTRP aims to minimize cost passenger and operator from a combination of route set. UTRP can be optimize with heuristics, meta-heuristics, and hyper-heuristics methods. In several previous studies, UTRP can be optimized with any meta-heuristics and hyper-heuristics methods. In this study we compare the performance of meta-heuristic methods, i.e. ill-climbing, simulated annealing, and hyper-heuristics method based on modified particle swarm optimization algorithm. The experimental results showed that the proposed methods could solve UTRP effectively. Regarding their performance, the results show that despite the generality of hyper-heuristics, their performance are competitive. More specifically, hyper-heuristics method is the best method compared to the other two methods in each dataset. In addition, compared to prior studies results, he proposed hyper-heuristics could outperform them in term of cost passenger of small dataset Mandl. The main contribution of this paper is that to best of our knowledge, it is the first study comparing the performance of meta-heuristics and hyper-heuristics approaches over UTRP.