Finding Transit Routes Configuration Using a Local Search Algorithm for Urban Grid Network

Transit Routes Design (TRD), in this paper, deals with finding the configuration of public transportation routes so as to achieve the maximum demand coverage over the network while holding the budget constraint. To tackle the TRD problem, many heuristic methods have been presented which are capable of finding solutions close to the global optimum in a reasonable amount of run-time. Though, little has been done to deal with specific network topologies. This paper aims at introducing and evaluating the performance of a local search “hill-climbing” algorithm to deal with the TRD problem in urban “grid” networks. In each run, the algorithm performs 20 replications each with a random initial solution, and improves the available solutions through slight changes in the routes configuration and moving to neighbor solutions. The comparison of the coverage obtained by the presented algorithm against the global optimal solutions in a 6×10 grid network with 30 random demand matrices, indicates that the presented algorithm is capable to find solutions with an average of 4% coverage less than the optimum in less than 20 minutes run-time.