An Ant System application to the Bus Network Design Problem: an algorithm and a case study

Bus system design is a difficult problem, and hence is usually decomposed into a series of sub-problems solved sequentially. Bus network design is foremost in this series of problems. The bus network design problem in this study is the problem of choosing a subset of interconnected bus routes from among a given set of such routes, which minimizes the total travel time of the users of the network, while being feasible in fleet requirements. The Ant System concept has been exploited to solve this problem. The algorithm has been applied to the problem and calibrated based on the network of Sioux Falls. For this purpose, several fleet assignment routines have been tested, some sensitivity analyses are made to estimate suitable parameter values, and alternative ways of laying pheromone on bus routes have been examined. Experiments are conducted to investigate the performance of the solution algorithm when the number of routes, or bus fleet size, increases. Moreover, other experiments help to determine the number of algorithmic iterations. These experiments prepared the algorithm to be applied to design the bus network of the City of Mashhad, with a population of over 2 million. The results have been compared with those of another solution to the same problem, obtained by another meta-heuristic, namely a Genetic Algorithm.