A heuristic aided Stochastic Beam Search algorithm for solving the transit network design problem

Abstract Designing efficient routes for a transit network is one of the main problems faced by city planners of the world. Due to the largeness and complexity of modern day road networks it is impossible to make a good route design manually. So, at present computer algorithms are used to design the routes. Designing routes for transit network is a multi-criteria decision making problem which has to search a large solution space to find an optimal solution. This paper presents a novel heuristic that can quickly generate good solutions. Also we propose a Stochastic Beam Search algorithm with a heuristic inspired successor operator. We conduct extensive experiments on some benchmark datasets and perform statistical tests on the results. We show that our algorithm can successfully explore the search space. Also we compare our results with previous studies and show that our algorithms produce superior results. In particular, for large datasets, the solutions generated by our heuristic in less than a second turn out to be better than solutions generated in two hours by the state of the art algorithm.